PostgreSQL Source Code  git master
analyzejoins.c File Reference
Include dependency graph for analyzejoins.c:

Go to the source code of this file.

Data Structures

struct  ReplaceVarnoContext
 
struct  SelfJoinCandidate
 

Functions

static bool join_is_removable (PlannerInfo *root, SpecialJoinInfo *sjinfo)
 
static void remove_leftjoinrel_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 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, List **extra_clauses)
 
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 **extra_clauses)
 
static Bitmapsetreplace_relid (Relids relids, int oldId, int newId)
 
static void replace_varno (Node *node, int from, int to)
 
static bool replace_varno_walker (Node *node, ReplaceVarnoContext *ctx)
 
static int self_join_candidates_cmp (const void *a, const void *b)
 
Listremove_useless_joins (PlannerInfo *root, List *joinlist)
 
static bool clause_sides_match_join (RestrictInfo *rinfo, Relids outerrelids, Relids innerrelids)
 
static void remove_rel_from_query (PlannerInfo *root, RelOptInfo *rel, int subst, SpecialJoinInfo *sjinfo, Relids joinrelids)
 
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)
 
bool innerrel_is_unique_ext (PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache, List **extra_clauses)
 
static void update_eclasses (EquivalenceClass *ec, int from, int to)
 
static bool restrict_infos_logically_equal (RestrictInfo *a, RestrictInfo *b)
 
static void remove_self_join_rel (PlannerInfo *root, PlanRowMark *kmark, PlanRowMark *rmark, RelOptInfo *toKeep, RelOptInfo *toRemove, List *restrictlist)
 
static void split_selfjoin_quals (PlannerInfo *root, List *joinquals, List **selfjoinquals, List **otherjoinquals, int from, int to)
 
static bool match_unique_clauses (PlannerInfo *root, RelOptInfo *outer, List *uclauses, Index relid)
 
static Relids remove_self_joins_one_group (PlannerInfo *root, Relids relids)
 
static Relids remove_self_joins_recurse (PlannerInfo *root, List *joinlist, Relids toRemove)
 
Listremove_useless_self_joins (PlannerInfo *root, List *joinlist)
 

Variables

bool enable_self_join_removal
 

Function Documentation

◆ clause_sides_match_join()

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

Definition at line 158 of file analyzejoins.c.

160 {
161  if (bms_is_subset(rinfo->left_relids, outerrelids) &&
162  bms_is_subset(rinfo->right_relids, innerrelids))
163  {
164  /* lefthand side is outer */
165  rinfo->outer_is_left = true;
166  return true;
167  }
168  else if (bms_is_subset(rinfo->left_relids, innerrelids) &&
169  bms_is_subset(rinfo->right_relids, outerrelids))
170  {
171  /* righthand side is outer */
172  rinfo->outer_is_left = false;
173  return true;
174  }
175  return false; /* no good for these input relations */
176 }
bool bms_is_subset(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:425

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 1223 of file analyzejoins.c.

1224 {
1225  ListCell *lc1,
1226  *lc2;
1227 
1228  forboth(lc1, colnos, lc2, opids)
1229  {
1230  if (colno == lfirst_int(lc1))
1231  return lfirst_oid(lc2);
1232  }
1233  return InvalidOid;
1234 }
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:518
#define lfirst_int(lc)
Definition: pg_list.h:173
#define lfirst_oid(lc)
Definition: pg_list.h:174
#define InvalidOid
Definition: postgres_ext.h:36

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 1263 of file analyzejoins.c.

1270 {
1271  return innerrel_is_unique_ext(root, joinrelids, outerrelids, innerrel,
1272  jointype, restrictlist, force_cache, NULL);
1273 }
bool innerrel_is_unique_ext(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache, List **extra_clauses)

References innerrel_is_unique_ext().

Referenced by add_paths_to_joinrel(), and reduce_unique_semijoins().

◆ innerrel_is_unique_ext()

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

Definition at line 1283 of file analyzejoins.c.

1291 {
1292  MemoryContext old_context;
1293  ListCell *lc;
1294  UniqueRelInfo *uniqueRelInfo;
1295  List *outer_exprs = NIL;
1296  bool self_join = (extra_clauses != NULL);
1297 
1298  /* Certainly can't prove uniqueness when there are no joinclauses */
1299  if (restrictlist == NIL)
1300  return false;
1301 
1302  /*
1303  * Make a quick check to eliminate cases in which we will surely be unable
1304  * to prove uniqueness of the innerrel.
1305  */
1306  if (!rel_supports_distinctness(root, innerrel))
1307  return false;
1308 
1309  /*
1310  * Query the cache to see if we've managed to prove that innerrel is
1311  * unique for any subset of this outerrel. For non self-join search, we
1312  * don't need an exact match, as extra outerrels can't make the innerrel
1313  * any less unique (or more formally, the restrictlist for a join to a
1314  * superset outerrel must be a superset of the conditions we successfully
1315  * used before). For self-join search, we require an exact match of
1316  * outerrels, because we need extra clauses to be valid for our case.
1317  * Also, for self-join checking we've filtered the clauses list. Thus,
1318  * for a self-join search, we can match only the result cached for another
1319  * self-join check.
1320  */
1321  foreach(lc, innerrel->unique_for_rels)
1322  {
1323  uniqueRelInfo = (UniqueRelInfo *) lfirst(lc);
1324 
1325  if ((!self_join && bms_is_subset(uniqueRelInfo->outerrelids, outerrelids)) ||
1326  (self_join && bms_equal(uniqueRelInfo->outerrelids, outerrelids) &&
1327  uniqueRelInfo->self_join))
1328  {
1329  if (extra_clauses)
1330  *extra_clauses = uniqueRelInfo->extra_clauses;
1331  return true; /* Success! */
1332  }
1333  }
1334 
1335  /*
1336  * Conversely, we may have already determined that this outerrel, or some
1337  * superset thereof, cannot prove this innerrel to be unique.
1338  */
1339  foreach(lc, innerrel->non_unique_for_rels)
1340  {
1341  Relids unique_for_rels = (Relids) lfirst(lc);
1342 
1343  if (bms_is_subset(outerrelids, unique_for_rels))
1344  return false;
1345  }
1346 
1347  /* No cached information, so try to make the proof. */
1348  if (is_innerrel_unique_for(root, joinrelids, outerrelids, innerrel,
1349  jointype, restrictlist,
1350  self_join ? &outer_exprs : NULL))
1351  {
1352  /*
1353  * Cache the positive result for future probes, being sure to keep it
1354  * in the planner_cxt even if we are working in GEQO.
1355  *
1356  * Note: one might consider trying to isolate the minimal subset of
1357  * the outerrels that proved the innerrel unique. But it's not worth
1358  * the trouble, because the planner builds up joinrels incrementally
1359  * and so we'll see the minimally sufficient outerrels before any
1360  * supersets of them anyway.
1361  */
1362  old_context = MemoryContextSwitchTo(root->planner_cxt);
1363  uniqueRelInfo = makeNode(UniqueRelInfo);
1364  uniqueRelInfo->outerrelids = bms_copy(outerrelids);
1365  uniqueRelInfo->self_join = self_join;
1366  uniqueRelInfo->extra_clauses = outer_exprs;
1367  innerrel->unique_for_rels = lappend(innerrel->unique_for_rels,
1368  uniqueRelInfo);
1369  MemoryContextSwitchTo(old_context);
1370 
1371  if (extra_clauses)
1372  *extra_clauses = outer_exprs;
1373  return true; /* Success! */
1374  }
1375  else
1376  {
1377  /*
1378  * None of the join conditions for outerrel proved innerrel unique, so
1379  * we can safely reject this outerrel or any subset of it in future
1380  * checks.
1381  *
1382  * However, in normal planning mode, caching this knowledge is totally
1383  * pointless; it won't be queried again, because we build up joinrels
1384  * from smaller to larger. It is useful in GEQO mode, where the
1385  * knowledge can be carried across successive planning attempts; and
1386  * it's likely to be useful when using join-search plugins, too. Hence
1387  * cache when join_search_private is non-NULL. (Yeah, that's a hack,
1388  * but it seems reasonable.)
1389  *
1390  * Also, allow callers to override that heuristic and force caching;
1391  * that's useful for reduce_unique_semijoins, which calls here before
1392  * the normal join search starts.
1393  */
1394  if (force_cache || root->join_search_private)
1395  {
1396  old_context = MemoryContextSwitchTo(root->planner_cxt);
1397  innerrel->non_unique_for_rels =
1398  lappend(innerrel->non_unique_for_rels,
1399  bms_copy(outerrelids));
1400  MemoryContextSwitchTo(old_context);
1401  }
1402 
1403  return false;
1404  }
1405 }
static bool is_innerrel_unique_for(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, List **extra_clauses)
static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
Definition: analyzejoins.c:879
bool bms_equal(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:155
Bitmapset * bms_copy(const Bitmapset *a)
Definition: bitmapset.c:135
List * lappend(List *list, void *datum)
Definition: list.c:339
#define makeNode(_type_)
Definition: nodes.h:155
static MemoryContext MemoryContextSwitchTo(MemoryContext context)
Definition: palloc.h:124
Bitmapset * Relids
Definition: pathnodes.h:30
#define lfirst(lc)
Definition: pg_list.h:172
#define NIL
Definition: pg_list.h:68
Definition: pg_list.h:54
List * unique_for_rels
Definition: pathnodes.h:958
List * non_unique_for_rels
Definition: pathnodes.h:960
Relids outerrelids
Definition: pathnodes.h:3423
List * extra_clauses
Definition: pathnodes.h:3437

References bms_copy(), bms_equal(), bms_is_subset(), UniqueRelInfo::extra_clauses, is_innerrel_unique_for(), lappend(), lfirst, makeNode, MemoryContextSwitchTo(), NIL, RelOptInfo::non_unique_for_rels, UniqueRelInfo::outerrelids, rel_supports_distinctness(), UniqueRelInfo::self_join, and RelOptInfo::unique_for_rels.

Referenced by innerrel_is_unique(), and remove_self_joins_one_group().

◆ is_innerrel_unique_for()

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

Definition at line 1413 of file analyzejoins.c.

1420 {
1421  List *clause_list = NIL;
1422  ListCell *lc;
1423 
1424  /*
1425  * Search for mergejoinable clauses that constrain the inner rel against
1426  * the outer rel. If an operator is mergejoinable then it behaves like
1427  * equality for some btree opclass, so it's what we want. The
1428  * mergejoinability test also eliminates clauses containing volatile
1429  * functions, which we couldn't depend on.
1430  */
1431  foreach(lc, restrictlist)
1432  {
1433  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
1434 
1435  /*
1436  * As noted above, if it's a pushed-down clause and we're at an outer
1437  * join, we can't use it.
1438  */
1439  if (IS_OUTER_JOIN(jointype) &&
1440  RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
1441  continue;
1442 
1443  /* Ignore if it's not a mergejoinable clause */
1444  if (!restrictinfo->can_join ||
1445  restrictinfo->mergeopfamilies == NIL)
1446  continue; /* not mergejoinable */
1447 
1448  /*
1449  * Check if the clause has the form "outer op inner" or "inner op
1450  * outer", and if so mark which side is inner.
1451  */
1452  if (!clause_sides_match_join(restrictinfo, outerrelids,
1453  innerrel->relids))
1454  continue; /* no good for these input relations */
1455 
1456  /* OK, add to the list */
1457  clause_list = lappend(clause_list, restrictinfo);
1458  }
1459 
1460  /* Let rel_is_distinct_for() do the hard work */
1461  return rel_is_distinct_for(root, innerrel, clause_list, extra_clauses);
1462 }
static bool clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids, Relids innerrelids)
Definition: analyzejoins.c:158
static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list, List **extra_clauses)
Definition: analyzejoins.c:938
#define IS_OUTER_JOIN(jointype)
Definition: nodes.h:327
#define RINFO_IS_PUSHED_DOWN(rinfo, joinrelids)
Definition: pathnodes.h:2698
Relids relids
Definition: pathnodes.h:856

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_ext().

◆ join_is_removable()

static bool join_is_removable ( PlannerInfo root,
SpecialJoinInfo sjinfo 
)
static

Definition at line 190 of file analyzejoins.c.

191 {
192  int innerrelid;
193  RelOptInfo *innerrel;
194  Relids inputrelids;
195  Relids joinrelids;
196  List *clause_list = NIL;
197  ListCell *l;
198  int attroff;
199 
200  /*
201  * Must be a left join to a single baserel, else we aren't going to be
202  * able to do anything with it.
203  */
204  if (sjinfo->jointype != JOIN_LEFT)
205  return false;
206 
207  if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
208  return false;
209 
210  /*
211  * Never try to eliminate a left join to the query result rel. Although
212  * the case is syntactically impossible in standard SQL, MERGE will build
213  * a join tree that looks exactly like that.
214  */
215  if (innerrelid == root->parse->resultRelation)
216  return false;
217 
218  innerrel = find_base_rel(root, innerrelid);
219 
220  /*
221  * Before we go to the effort of checking whether any innerrel variables
222  * are needed above the join, make a quick check to eliminate cases in
223  * which we will surely be unable to prove uniqueness of the innerrel.
224  */
225  if (!rel_supports_distinctness(root, innerrel))
226  return false;
227 
228  /* Compute the relid set for the join we are considering */
229  inputrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
230  Assert(sjinfo->ojrelid != 0);
231  joinrelids = bms_copy(inputrelids);
232  joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid);
233 
234  /*
235  * We can't remove the join if any inner-rel attributes are used above the
236  * join. Here, "above" the join includes pushed-down conditions, so we
237  * should reject if attr_needed includes the OJ's own relid; therefore,
238  * compare to inputrelids not joinrelids.
239  *
240  * As a micro-optimization, it seems better to start with max_attr and
241  * count down rather than starting with min_attr and counting up, on the
242  * theory that the system attributes are somewhat less likely to be wanted
243  * and should be tested last.
244  */
245  for (attroff = innerrel->max_attr - innerrel->min_attr;
246  attroff >= 0;
247  attroff--)
248  {
249  if (!bms_is_subset(innerrel->attr_needed[attroff], inputrelids))
250  return false;
251  }
252 
253  /*
254  * Similarly check that the inner rel isn't needed by any PlaceHolderVars
255  * that will be used above the join. The PHV case is a little bit more
256  * complicated, because PHVs may have been assigned a ph_eval_at location
257  * that includes the innerrel, yet their contained expression might not
258  * actually reference the innerrel (it could be just a constant, for
259  * instance). If such a PHV is due to be evaluated above the join then it
260  * needn't prevent join removal.
261  */
262  foreach(l, root->placeholder_list)
263  {
264  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
265 
266  if (bms_overlap(phinfo->ph_lateral, innerrel->relids))
267  return false; /* it references innerrel laterally */
268  if (!bms_overlap(phinfo->ph_eval_at, innerrel->relids))
269  continue; /* it definitely doesn't reference innerrel */
270  if (bms_is_subset(phinfo->ph_needed, inputrelids))
271  continue; /* PHV is not used above the join */
272  if (!bms_is_member(sjinfo->ojrelid, phinfo->ph_eval_at))
273  return false; /* it has to be evaluated below the join */
274 
275  /*
276  * We need to be sure there will still be a place to evaluate the PHV
277  * if we remove the join, ie that ph_eval_at wouldn't become empty.
278  */
279  if (!bms_overlap(sjinfo->min_lefthand, phinfo->ph_eval_at))
280  return false; /* there isn't any other place to eval PHV */
281  /* Check contained expression last, since this is a bit expensive */
282  if (bms_overlap(pull_varnos(root, (Node *) phinfo->ph_var->phexpr),
283  innerrel->relids))
284  return false; /* contained expression references innerrel */
285  }
286 
287  /*
288  * Search for mergejoinable clauses that constrain the inner rel against
289  * either the outer rel or a pseudoconstant. If an operator is
290  * mergejoinable then it behaves like equality for some btree opclass, so
291  * it's what we want. The mergejoinability test also eliminates clauses
292  * containing volatile functions, which we couldn't depend on.
293  */
294  foreach(l, innerrel->joininfo)
295  {
296  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
297 
298  /*
299  * If the current join commutes with some other outer join(s) via
300  * outer join identity 3, there will be multiple clones of its join
301  * clauses in the joininfo list. We want to consider only the
302  * has_clone form of such clauses. Processing more than one form
303  * would be wasteful, and also some of the others would confuse the
304  * RINFO_IS_PUSHED_DOWN test below.
305  */
306  if (restrictinfo->is_clone)
307  continue; /* ignore it */
308 
309  /*
310  * If it's not a join clause for this outer join, we can't use it.
311  * Note that if the clause is pushed-down, then it is logically from
312  * above the outer join, even if it references no other rels (it might
313  * be from WHERE, for example).
314  */
315  if (RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
316  continue; /* ignore; not useful here */
317 
318  /* Ignore if it's not a mergejoinable clause */
319  if (!restrictinfo->can_join ||
320  restrictinfo->mergeopfamilies == NIL)
321  continue; /* not mergejoinable */
322 
323  /*
324  * Check if clause has the form "outer op inner" or "inner op outer",
325  * and if so mark which side is inner.
326  */
327  if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand,
328  innerrel->relids))
329  continue; /* no good for these input relations */
330 
331  /* OK, add to list */
332  clause_list = lappend(clause_list, restrictinfo);
333  }
334 
335  /*
336  * Now that we have the relevant equality join clauses, try to prove the
337  * innerrel distinct.
338  */
339  if (rel_is_distinct_for(root, innerrel, clause_list, NULL))
340  return true;
341 
342  /*
343  * Some day it would be nice to check for other methods of establishing
344  * distinctness.
345  */
346  return false;
347 }
bool bms_is_member(int x, const Bitmapset *a)
Definition: bitmapset.c:523
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:828
Bitmapset * bms_union(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:264
bool bms_overlap(const Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:595
bool bms_get_singleton_member(const Bitmapset *a, int *member)
Definition: bitmapset.c:728
Assert(fmt[strlen(fmt) - 1] !='\n')
@ JOIN_LEFT
Definition: nodes.h:284
RelOptInfo * find_base_rel(PlannerInfo *root, int relid)
Definition: relnode.c:407
Definition: nodes.h:129
Relids ph_lateral
Definition: pathnodes.h:3065
Relids ph_needed
Definition: pathnodes.h:3068
Relids ph_eval_at
Definition: pathnodes.h:3062
PlaceHolderVar * ph_var
Definition: pathnodes.h:3059
List * placeholder_list
Definition: pathnodes.h:371
Query * parse
Definition: pathnodes.h:199
List * joininfo
Definition: pathnodes.h:972
AttrNumber max_attr
Definition: pathnodes.h:911
AttrNumber min_attr
Definition: pathnodes.h:909
Relids min_righthand
Definition: pathnodes.h:2869
JoinType jointype
Definition: pathnodes.h:2872
Relids min_lefthand
Definition: pathnodes.h:2868
Relids pull_varnos(PlannerInfo *root, Node *node)
Definition: var.c:108

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().

◆ match_unique_clauses()

static bool match_unique_clauses ( PlannerInfo root,
RelOptInfo outer,
List uclauses,
Index  relid 
)
static

Definition at line 2038 of file analyzejoins.c.

2040 {
2041  ListCell *lc;
2042 
2043  foreach(lc, uclauses)
2044  {
2045  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
2046  Expr *clause;
2047  Node *iclause;
2048  Node *c1;
2049  bool matched = false;
2050  ListCell *olc;
2051 
2052  Assert(outer->relid > 0 && relid > 0);
2053 
2054  /* Only filters like f(R.x1,...,R.xN) == expr we should consider. */
2055  Assert(bms_is_empty(rinfo->left_relids) ^
2056  bms_is_empty(rinfo->right_relids));
2057 
2058  clause = (Expr *) copyObject(rinfo->clause);
2059  replace_varno((Node *) clause, relid, outer->relid);
2060 
2061  iclause = bms_is_empty(rinfo->left_relids) ? get_rightop(clause) :
2062  get_leftop(clause);
2063  c1 = bms_is_empty(rinfo->left_relids) ? get_leftop(clause) :
2064  get_rightop(clause);
2065 
2066  /*
2067  * Compare these left and right sides with the corresponding sides of
2068  * the outer's filters. If no one is detected - return immediately.
2069  */
2070  foreach(olc, outer->baserestrictinfo)
2071  {
2072  RestrictInfo *orinfo = lfirst_node(RestrictInfo, olc);
2073  Node *oclause;
2074  Node *c2;
2075 
2076  if (orinfo->mergeopfamilies == NIL)
2077  /* Don't consider clauses which aren't similar to 'F(X)=G(Y)' */
2078  continue;
2079 
2080  Assert(is_opclause(orinfo->clause));
2081 
2082  oclause = bms_is_empty(orinfo->left_relids) ?
2083  get_rightop(orinfo->clause) : get_leftop(orinfo->clause);
2084  c2 = (bms_is_empty(orinfo->left_relids) ?
2085  get_leftop(orinfo->clause) : get_rightop(orinfo->clause));
2086 
2087  if (equal(iclause, oclause) && equal(c1, c2))
2088  {
2089  matched = true;
2090  break;
2091  }
2092  }
2093 
2094  if (!matched)
2095  return false;
2096  }
2097 
2098  return true;
2099 }
static void replace_varno(Node *node, int from, int to)
#define bms_is_empty(a)
Definition: bitmapset.h:105
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:223
static bool is_opclause(const void *clause)
Definition: nodeFuncs.h:74
static Node * get_rightop(const void *clause)
Definition: nodeFuncs.h:93
static Node * get_leftop(const void *clause)
Definition: nodeFuncs.h:81
#define copyObject(obj)
Definition: nodes.h:223
#define lfirst_node(type, lc)
Definition: pg_list.h:176
List * baserestrictinfo
Definition: pathnodes.h:966
Index relid
Definition: pathnodes.h:903
Expr * clause
Definition: pathnodes.h:2541

References Assert(), RelOptInfo::baserestrictinfo, bms_is_empty, RestrictInfo::clause, copyObject, equal(), get_leftop(), get_rightop(), is_opclause(), lfirst_node, NIL, RelOptInfo::relid, and replace_varno().

Referenced by remove_self_joins_one_group().

◆ query_is_distinct_for()

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

Definition at line 1074 of file analyzejoins.c.

1075 {
1076  ListCell *l;
1077  Oid opid;
1078 
1079  Assert(list_length(colnos) == list_length(opids));
1080 
1081  /*
1082  * DISTINCT (including DISTINCT ON) guarantees uniqueness if all the
1083  * columns in the DISTINCT clause appear in colnos and operator semantics
1084  * match. This is true even if there are SRFs in the DISTINCT columns or
1085  * elsewhere in the tlist.
1086  */
1087  if (query->distinctClause)
1088  {
1089  foreach(l, query->distinctClause)
1090  {
1091  SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
1093  query->targetList);
1094 
1095  opid = distinct_col_search(tle->resno, colnos, opids);
1096  if (!OidIsValid(opid) ||
1097  !equality_ops_are_compatible(opid, sgc->eqop))
1098  break; /* exit early if no match */
1099  }
1100  if (l == NULL) /* had matches for all? */
1101  return true;
1102  }
1103 
1104  /*
1105  * Otherwise, a set-returning function in the query's targetlist can
1106  * result in returning duplicate rows, despite any grouping that might
1107  * occur before tlist evaluation. (If all tlist SRFs are within GROUP BY
1108  * columns, it would be safe because they'd be expanded before grouping.
1109  * But it doesn't currently seem worth the effort to check for that.)
1110  */
1111  if (query->hasTargetSRFs)
1112  return false;
1113 
1114  /*
1115  * Similarly, GROUP BY without GROUPING SETS guarantees uniqueness if all
1116  * the grouped columns appear in colnos and operator semantics match.
1117  */
1118  if (query->groupClause && !query->groupingSets)
1119  {
1120  foreach(l, query->groupClause)
1121  {
1122  SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
1124  query->targetList);
1125 
1126  opid = distinct_col_search(tle->resno, colnos, opids);
1127  if (!OidIsValid(opid) ||
1128  !equality_ops_are_compatible(opid, sgc->eqop))
1129  break; /* exit early if no match */
1130  }
1131  if (l == NULL) /* had matches for all? */
1132  return true;
1133  }
1134  else if (query->groupingSets)
1135  {
1136  /*
1137  * If we have grouping sets with expressions, we probably don't have
1138  * uniqueness and analysis would be hard. Punt.
1139  */
1140  if (query->groupClause)
1141  return false;
1142 
1143  /*
1144  * If we have no groupClause (therefore no grouping expressions), we
1145  * might have one or many empty grouping sets. If there's just one,
1146  * then we're returning only one row and are certainly unique. But
1147  * otherwise, we know we're certainly not unique.
1148  */
1149  if (list_length(query->groupingSets) == 1 &&
1150  ((GroupingSet *) linitial(query->groupingSets))->kind == GROUPING_SET_EMPTY)
1151  return true;
1152  else
1153  return false;
1154  }
1155  else
1156  {
1157  /*
1158  * If we have no GROUP BY, but do have aggregates or HAVING, then the
1159  * result is at most one row so it's surely unique, for any operators.
1160  */
1161  if (query->hasAggs || query->havingQual)
1162  return true;
1163  }
1164 
1165  /*
1166  * UNION, INTERSECT, EXCEPT guarantee uniqueness of the whole output row,
1167  * except with ALL.
1168  */
1169  if (query->setOperations)
1170  {
1172 
1173  Assert(topop->op != SETOP_NONE);
1174 
1175  if (!topop->all)
1176  {
1177  ListCell *lg;
1178 
1179  /* We're good if all the nonjunk output columns are in colnos */
1180  lg = list_head(topop->groupClauses);
1181  foreach(l, query->targetList)
1182  {
1183  TargetEntry *tle = (TargetEntry *) lfirst(l);
1184  SortGroupClause *sgc;
1185 
1186  if (tle->resjunk)
1187  continue; /* ignore resjunk columns */
1188 
1189  /* non-resjunk columns should have grouping clauses */
1190  Assert(lg != NULL);
1191  sgc = (SortGroupClause *) lfirst(lg);
1192  lg = lnext(topop->groupClauses, lg);
1193 
1194  opid = distinct_col_search(tle->resno, colnos, opids);
1195  if (!OidIsValid(opid) ||
1196  !equality_ops_are_compatible(opid, sgc->eqop))
1197  break; /* exit early if no match */
1198  }
1199  if (l == NULL) /* had matches for all? */
1200  return true;
1201  }
1202  }
1203 
1204  /*
1205  * XXX Are there any other cases in which we can easily see the result
1206  * must be distinct?
1207  *
1208  * If you do add more smarts to this function, be sure to update
1209  * query_supports_distinctness() to match.
1210  */
1211 
1212  return false;
1213 }
static Oid distinct_col_search(int colno, List *colnos, List *opids)
#define OidIsValid(objectId)
Definition: c.h:764
bool equality_ops_are_compatible(Oid opno1, Oid opno2)
Definition: lsyscache.c:697
#define castNode(_type_, nodeptr)
Definition: nodes.h:176
@ GROUPING_SET_EMPTY
Definition: parsenodes.h:1445
@ SETOP_NONE
Definition: parsenodes.h:1948
static int list_length(const List *l)
Definition: pg_list.h:152
static ListCell * list_head(const List *l)
Definition: pg_list.h:128
#define linitial(l)
Definition: pg_list.h:178
static ListCell * lnext(const List *l, const ListCell *c)
Definition: pg_list.h:343
unsigned int Oid
Definition: postgres_ext.h:31
Node * setOperations
Definition: parsenodes.h:209
List * groupClause
Definition: parsenodes.h:190
Node * havingQual
Definition: parsenodes.h:195
List * targetList
Definition: parsenodes.h:181
List * groupingSets
Definition: parsenodes.h:193
List * distinctClause
Definition: parsenodes.h:199
SetOperation op
Definition: parsenodes.h:2026
AttrNumber resno
Definition: primnodes.h:1924
TargetEntry * get_sortgroupclause_tle(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:367

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 1037 of file analyzejoins.c.

1038 {
1039  /* SRFs break distinctness except with DISTINCT, see below */
1040  if (query->hasTargetSRFs && query->distinctClause == NIL)
1041  return false;
1042 
1043  /* check for features we can prove distinctness with */
1044  if (query->distinctClause != NIL ||
1045  query->groupClause != NIL ||
1046  query->groupingSets != NIL ||
1047  query->hasAggs ||
1048  query->havingQual ||
1049  query->setOperations)
1050  return true;
1051 
1052  return false;
1053 }

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 803 of file analyzejoins.c.

804 {
805  ListCell *lc;
806 
807  /*
808  * Scan the join_info_list to find semijoins.
809  */
810  foreach(lc, root->join_info_list)
811  {
812  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
813  int innerrelid;
814  RelOptInfo *innerrel;
815  Relids joinrelids;
816  List *restrictlist;
817 
818  /*
819  * Must be a semijoin to a single baserel, else we aren't going to be
820  * able to do anything with it.
821  */
822  if (sjinfo->jointype != JOIN_SEMI)
823  continue;
824 
825  if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
826  continue;
827 
828  innerrel = find_base_rel(root, innerrelid);
829 
830  /*
831  * Before we trouble to run generate_join_implied_equalities, make a
832  * quick check to eliminate cases in which we will surely be unable to
833  * prove uniqueness of the innerrel.
834  */
835  if (!rel_supports_distinctness(root, innerrel))
836  continue;
837 
838  /* Compute the relid set for the join we are considering */
839  joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
840  Assert(sjinfo->ojrelid == 0); /* SEMI joins don't have RT indexes */
841 
842  /*
843  * Since we're only considering a single-rel RHS, any join clauses it
844  * has must be clauses linking it to the semijoin's min_lefthand. We
845  * can also consider EC-derived join clauses.
846  */
847  restrictlist =
849  joinrelids,
850  sjinfo->min_lefthand,
851  innerrel,
852  NULL),
853  innerrel->joininfo);
854 
855  /* Test whether the innerrel is unique for those clauses. */
856  if (!innerrel_is_unique(root,
857  joinrelids, sjinfo->min_lefthand, innerrel,
858  JOIN_SEMI, restrictlist, true))
859  continue;
860 
861  /* OK, remove the SpecialJoinInfo from the list. */
863  }
864 }
bool innerrel_is_unique(PlannerInfo *root, Relids joinrelids, Relids outerrelids, RelOptInfo *innerrel, JoinType jointype, List *restrictlist, bool force_cache)
List * generate_join_implied_equalities(PlannerInfo *root, Relids join_relids, Relids outer_relids, RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo)
Definition: equivclass.c:1392
List * list_concat(List *list1, const List *list2)
Definition: list.c:561
@ JOIN_SEMI
Definition: nodes.h:297
#define foreach_delete_current(lst, var_or_cell)
Definition: pg_list.h:391
List * join_info_list
Definition: pathnodes.h:337

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,
List **  extra_clauses 
)
static

Definition at line 938 of file analyzejoins.c.

940 {
941  /*
942  * We could skip a couple of tests here if we assume all callers checked
943  * rel_supports_distinctness first, but it doesn't seem worth taking any
944  * risk for.
945  */
946  if (rel->reloptkind != RELOPT_BASEREL)
947  return false;
948  if (rel->rtekind == RTE_RELATION)
949  {
950  /*
951  * Examine the indexes to see if we have a matching unique index.
952  * relation_has_unique_index_ext automatically adds any usable
953  * restriction clauses for the rel, so we needn't do that here.
954  */
955  if (relation_has_unique_index_ext(root, rel, clause_list, NIL, NIL,
956  extra_clauses))
957  return true;
958  }
959  else if (rel->rtekind == RTE_SUBQUERY)
960  {
961  Index relid = rel->relid;
962  Query *subquery = root->simple_rte_array[relid]->subquery;
963  List *colnos = NIL;
964  List *opids = NIL;
965  ListCell *l;
966 
967  /*
968  * Build the argument lists for query_is_distinct_for: a list of
969  * output column numbers that the query needs to be distinct over, and
970  * a list of equality operators that the output columns need to be
971  * distinct according to.
972  *
973  * (XXX we are not considering restriction clauses attached to the
974  * subquery; is that worth doing?)
975  */
976  foreach(l, clause_list)
977  {
979  Oid op;
980  Var *var;
981 
982  /*
983  * Get the equality operator we need uniqueness according to.
984  * (This might be a cross-type operator and thus not exactly the
985  * same operator the subquery would consider; that's all right
986  * since query_is_distinct_for can resolve such cases.) The
987  * caller's mergejoinability test should have selected only
988  * OpExprs.
989  */
990  op = castNode(OpExpr, rinfo->clause)->opno;
991 
992  /* caller identified the inner side for us */
993  if (rinfo->outer_is_left)
994  var = (Var *) get_rightop(rinfo->clause);
995  else
996  var = (Var *) get_leftop(rinfo->clause);
997 
998  /*
999  * We may ignore any RelabelType node above the operand. (There
1000  * won't be more than one, since eval_const_expressions() has been
1001  * applied already.)
1002  */
1003  if (var && IsA(var, RelabelType))
1004  var = (Var *) ((RelabelType *) var)->arg;
1005 
1006  /*
1007  * If inner side isn't a Var referencing a subquery output column,
1008  * this clause doesn't help us.
1009  */
1010  if (!var || !IsA(var, Var) ||
1011  var->varno != relid || var->varlevelsup != 0)
1012  continue;
1013 
1014  colnos = lappend_int(colnos, var->varattno);
1015  opids = lappend_oid(opids, op);
1016  }
1017 
1018  if (query_is_distinct_for(subquery, colnos, opids))
1019  return true;
1020  }
1021  return false;
1022 }
bool query_is_distinct_for(Query *query, List *colnos, List *opids)
unsigned int Index
Definition: c.h:603
bool relation_has_unique_index_ext(PlannerInfo *root, RelOptInfo *rel, List *restrictlist, List *exprlist, List *oprlist, List **extra_clauses)
Definition: indxpath.c:3509
List * lappend_int(List *list, int datum)
Definition: list.c:357
List * lappend_oid(List *list, Oid datum)
Definition: list.c:375
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
@ RTE_SUBQUERY
Definition: parsenodes.h:1007
@ RTE_RELATION
Definition: parsenodes.h:1006
@ RELOPT_BASEREL
Definition: pathnodes.h:812
RelOptKind reloptkind
Definition: pathnodes.h:850
RTEKind rtekind
Definition: pathnodes.h:907
Definition: primnodes.h:234
AttrNumber varattno
Definition: primnodes.h:246
int varno
Definition: primnodes.h:241
Index varlevelsup
Definition: primnodes.h:266

References castNode, RestrictInfo::clause, get_leftop(), get_rightop(), IsA, lappend_int(), lappend_oid(), lfirst_node, NIL, query_is_distinct_for(), relation_has_unique_index_ext(), 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 879 of file analyzejoins.c.

880 {
881  /* We only know about baserels ... */
882  if (rel->reloptkind != RELOPT_BASEREL)
883  return false;
884  if (rel->rtekind == RTE_RELATION)
885  {
886  /*
887  * For a plain relation, we only know how to prove uniqueness by
888  * reference to unique indexes. Make sure there's at least one
889  * suitable unique index. It must be immediately enforced, and not a
890  * partial index. (Keep these conditions in sync with
891  * relation_has_unique_index_for!)
892  */
893  ListCell *lc;
894 
895  foreach(lc, rel->indexlist)
896  {
897  IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);
898 
899  if (ind->unique && ind->immediate && ind->indpred == NIL)
900  return true;
901  }
902  }
903  else if (rel->rtekind == RTE_SUBQUERY)
904  {
905  Query *subquery = root->simple_rte_array[rel->relid]->subquery;
906 
907  /* Check if the subquery has any qualities that support distinctness */
908  if (query_supports_distinctness(subquery))
909  return true;
910  }
911  /* We have no proof rules for any other rtekinds. */
912  return false;
913 }
bool query_supports_distinctness(Query *query)
List * indexlist
Definition: pathnodes.h:925

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_ext(), join_is_removable(), and reduce_unique_semijoins().

◆ remove_leftjoinrel_from_query()

static void remove_leftjoinrel_from_query ( PlannerInfo root,
int  relid,
SpecialJoinInfo sjinfo 
)
static

Definition at line 522 of file analyzejoins.c.

524 {
525  List *joininfos;
526  int ojrelid = sjinfo->ojrelid;
527  RelOptInfo *rel = find_base_rel(root, relid);
528  Relids join_plus_commute;
529  Relids joinrelids;
530  ListCell *l;
531 
532  /* Compute the relid set for the join we are considering */
533  joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
534  Assert(ojrelid != 0);
535  joinrelids = bms_add_member(joinrelids, ojrelid);
536 
537  remove_rel_from_query(root, rel, -1, sjinfo, joinrelids);
538 
539  /*
540  * Remove any joinquals referencing the rel from the joininfo lists.
541  *
542  * In some cases, a joinqual has to be put back after deleting its
543  * reference to the target rel. This can occur for pseudoconstant and
544  * outerjoin-delayed quals, which can get marked as requiring the rel in
545  * order to force them to be evaluated at or above the join. We can't
546  * just discard them, though. Only quals that logically belonged to the
547  * outer join being discarded should be removed from the query.
548  *
549  * We might encounter a qual that is a clone of a deletable qual with some
550  * outer-join relids added (see deconstruct_distribute_oj_quals). To
551  * ensure we get rid of such clones as well, add the relids of all OJs
552  * commutable with this one to the set we test against for
553  * pushed-down-ness.
554  */
555  join_plus_commute = bms_union(joinrelids,
556  sjinfo->commute_above_r);
557  join_plus_commute = bms_add_members(join_plus_commute,
558  sjinfo->commute_below_l);
559 
560  /*
561  * We must make a copy of the rel's old joininfo list before starting the
562  * loop, because otherwise remove_join_clause_from_rels would destroy the
563  * list while we're scanning it.
564  */
565  joininfos = list_copy(rel->joininfo);
566  foreach(l, joininfos)
567  {
568  RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
569 
570  remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);
571 
572  if (RINFO_IS_PUSHED_DOWN(rinfo, join_plus_commute))
573  {
574  /*
575  * There might be references to relid or ojrelid in the
576  * RestrictInfo's relid sets, as a consequence of PHVs having had
577  * ph_eval_at sets that include those. We already checked above
578  * that any such PHV is safe (and updated its ph_eval_at), so we
579  * can just drop those references.
580  */
581  remove_rel_from_restrictinfo(rinfo, relid, ojrelid);
582 
583  /*
584  * Cross-check that the clause itself does not reference the
585  * target rel or join.
586  */
587 #ifdef USE_ASSERT_CHECKING
588  {
589  Relids clause_varnos = pull_varnos(root,
590  (Node *) rinfo->clause);
591 
592  Assert(!bms_is_member(relid, clause_varnos));
593  Assert(!bms_is_member(ojrelid, clause_varnos));
594  }
595 #endif
596  /* Now throw it back into the joininfo lists */
597  distribute_restrictinfo_to_rels(root, rinfo);
598  }
599  }
600 
601  /*
602  * Likewise remove references from EquivalenceClasses.
603  */
604  foreach(l, root->eq_classes)
605  {
607 
608  if (bms_is_member(relid, ec->ec_relids) ||
609  bms_is_member(ojrelid, ec->ec_relids))
610  remove_rel_from_eclass(ec, relid, ojrelid);
611  }
612 
613  /*
614  * There may be references to the rel in root->fkey_list, but if so,
615  * match_foreign_keys_to_quals() will get rid of them.
616  */
617 
618  /*
619  * Finally, remove the rel from the baserel array to prevent it from being
620  * referenced again. (We can't do this earlier because
621  * remove_join_clause_from_rels will touch it.)
622  */
623  root->simple_rel_array[relid] = NULL;
624 
625  /* And nuke the RelOptInfo, just in case there's another access path */
626  pfree(rel);
627 }
static void remove_rel_from_query(PlannerInfo *root, RelOptInfo *rel, int subst, SpecialJoinInfo *sjinfo, Relids joinrelids)
Definition: analyzejoins.c:360
static void remove_rel_from_restrictinfo(RestrictInfo *rinfo, int relid, int ojrelid)
Definition: analyzejoins.c:638
static void remove_rel_from_eclass(EquivalenceClass *ec, int relid, int ojrelid)
Definition: analyzejoins.c:695
Bitmapset * bms_add_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:930
void distribute_restrictinfo_to_rels(PlannerInfo *root, RestrictInfo *restrictinfo)
Definition: initsplan.c:2818
void remove_join_clause_from_rels(PlannerInfo *root, RestrictInfo *restrictinfo, Relids join_relids)
Definition: joininfo.c:153
List * list_copy(const List *oldlist)
Definition: list.c:1573
void pfree(void *pointer)
Definition: mcxt.c:1431
List * eq_classes
Definition: pathnodes.h:311
Relids required_relids
Definition: pathnodes.h:2572
Relids commute_above_r
Definition: pathnodes.h:2875
Relids commute_below_l
Definition: pathnodes.h:2876

References Assert(), bms_add_member(), bms_add_members(), bms_is_member(), bms_union(), RestrictInfo::clause, SpecialJoinInfo::commute_above_r, SpecialJoinInfo::commute_below_l, distribute_restrictinfo_to_rels(), EquivalenceClass::ec_relids, PlannerInfo::eq_classes, find_base_rel(), RelOptInfo::joininfo, lfirst, list_copy(), SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, SpecialJoinInfo::ojrelid, pfree(), pull_varnos(), remove_join_clause_from_rels(), remove_rel_from_eclass(), remove_rel_from_query(), remove_rel_from_restrictinfo(), RestrictInfo::required_relids, and RINFO_IS_PUSHED_DOWN.

Referenced by remove_useless_joins().

◆ remove_rel_from_eclass()

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

Definition at line 695 of file analyzejoins.c.

696 {
697  ListCell *lc;
698 
699  /* Fix up the EC's overall relids */
700  ec->ec_relids = bms_del_member(ec->ec_relids, relid);
701  ec->ec_relids = bms_del_member(ec->ec_relids, ojrelid);
702 
703  /*
704  * Fix up the member expressions. Any non-const member that ends with
705  * empty em_relids must be a Var or PHV of the removed relation. We don't
706  * need it anymore, so we can drop it.
707  */
708  foreach(lc, ec->ec_members)
709  {
710  EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
711 
712  if (bms_is_member(relid, cur_em->em_relids) ||
713  bms_is_member(ojrelid, cur_em->em_relids))
714  {
715  Assert(!cur_em->em_is_const);
716  cur_em->em_relids = bms_del_member(cur_em->em_relids, relid);
717  cur_em->em_relids = bms_del_member(cur_em->em_relids, ojrelid);
718  if (bms_is_empty(cur_em->em_relids))
720  }
721  }
722 
723  /* Fix up the source clauses, in case we can re-use them later */
724  foreach(lc, ec->ec_sources)
725  {
726  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
727 
728  remove_rel_from_restrictinfo(rinfo, relid, ojrelid);
729  }
730 
731  /*
732  * Rather than expend code on fixing up any already-derived clauses, just
733  * drop them. (At this point, any such clauses would be base restriction
734  * clauses, which we'd not need anymore anyway.)
735  */
736  ec->ec_derives = NIL;
737 }
Bitmapset * bms_del_member(Bitmapset *a, int x)
Definition: bitmapset.c:881

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_leftjoinrel_from_query().

◆ remove_rel_from_joinlist()

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

Definition at line 749 of file analyzejoins.c.

750 {
751  List *result = NIL;
752  ListCell *jl;
753 
754  foreach(jl, joinlist)
755  {
756  Node *jlnode = (Node *) lfirst(jl);
757 
758  if (IsA(jlnode, RangeTblRef))
759  {
760  int varno = ((RangeTblRef *) jlnode)->rtindex;
761 
762  if (varno == relid)
763  (*nremoved)++;
764  else
765  result = lappend(result, jlnode);
766  }
767  else if (IsA(jlnode, List))
768  {
769  /* Recurse to handle subproblem */
770  List *sublist;
771 
772  sublist = remove_rel_from_joinlist((List *) jlnode,
773  relid, nremoved);
774  /* Avoid including empty sub-lists in the result */
775  if (sublist)
776  result = lappend(result, sublist);
777  }
778  else
779  {
780  elog(ERROR, "unrecognized joinlist node type: %d",
781  (int) nodeTag(jlnode));
782  }
783  }
784 
785  return result;
786 }
static List * remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
Definition: analyzejoins.c:749
#define ERROR
Definition: elog.h:39
#define nodeTag(nodeptr)
Definition: nodes.h:133

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

Referenced by remove_useless_joins(), and remove_useless_self_joins().

◆ remove_rel_from_query()

static void remove_rel_from_query ( PlannerInfo root,
RelOptInfo rel,
int  subst,
SpecialJoinInfo sjinfo,
Relids  joinrelids 
)
static

Definition at line 360 of file analyzejoins.c.

363 {
364  int relid = rel->relid;
365  int ojrelid = (sjinfo != NULL) ? sjinfo->ojrelid : -1;
366  Index rti;
367  ListCell *l;
368 
369  /*
370  * Remove references to the rel from other baserels' attr_needed arrays.
371  */
372  for (rti = 1; rti < root->simple_rel_array_size; rti++)
373  {
374  RelOptInfo *otherrel = root->simple_rel_array[rti];
375  int attroff;
376 
377  /* there may be empty slots corresponding to non-baserel RTEs */
378  if (otherrel == NULL)
379  continue;
380 
381  Assert(otherrel->relid == rti); /* sanity check on array */
382 
383  /* no point in processing target rel itself */
384  if (otherrel == rel)
385  continue;
386 
387  for (attroff = otherrel->max_attr - otherrel->min_attr;
388  attroff >= 0;
389  attroff--)
390  {
391  otherrel->attr_needed[attroff] =
392  replace_relid(otherrel->attr_needed[attroff], relid, subst);
393  otherrel->attr_needed[attroff] =
394  replace_relid(otherrel->attr_needed[attroff], ojrelid, subst);
395  }
396 
397  /* Update lateral references. */
398  if (root->hasLateralRTEs)
399  {
400  RangeTblEntry *rte = root->simple_rte_array[rti];
401  ReplaceVarnoContext ctx = {.from = relid,.to = subst};
402 
403  if (rte->lateral)
404  {
405  replace_varno((Node *) otherrel->lateral_vars, relid, subst);
406 
407  /*
408  * Although we pass root->parse through cleanup procedure,
409  * but parse->rtable and rte contains refs to different copies
410  * of the subquery.
411  */
412  if (otherrel->rtekind == RTE_SUBQUERY)
415 #ifdef USE_ASSERT_CHECKING
416  /* Just check possibly hidden non-replaced relids */
417  Assert(!bms_is_member(relid, pull_varnos(root, (Node *) rte->tablesample)));
418  Assert(!bms_is_member(relid, pull_varnos(root, (Node *) rte->functions)));
419  Assert(!bms_is_member(relid, pull_varnos(root, (Node *) rte->tablefunc)));
420  Assert(!bms_is_member(relid, pull_varnos(root, (Node *) rte->values_lists)));
421 #endif
422  }
423  }
424 
425 
426  }
427 
428  /*
429  * Update all_baserels and related relid sets.
430  */
431  root->all_baserels = replace_relid(root->all_baserels, relid, subst);
432  root->outer_join_rels = replace_relid(root->outer_join_rels, ojrelid, subst);
433  root->all_query_rels = replace_relid(root->all_query_rels, relid, subst);
434  root->all_query_rels = replace_relid(root->all_query_rels, ojrelid, subst);
435 
436  /*
437  * Likewise remove references from SpecialJoinInfo data structures.
438  *
439  * This is relevant in case the outer join we're deleting is nested inside
440  * other outer joins: the upper joins' relid sets have to be adjusted. The
441  * RHS of the target outer join will be made empty here, but that's OK
442  * since caller will delete that SpecialJoinInfo entirely.
443  */
444  foreach(l, root->join_info_list)
445  {
446  SpecialJoinInfo *sjinf = (SpecialJoinInfo *) lfirst(l);
447 
448  sjinf->min_lefthand = replace_relid(sjinf->min_lefthand, relid, subst);
449  sjinf->min_righthand = replace_relid(sjinf->min_righthand, relid, subst);
450  sjinf->syn_lefthand = replace_relid(sjinf->syn_lefthand, relid, subst);
451  sjinf->syn_righthand = replace_relid(sjinf->syn_righthand, relid, subst);
452  sjinf->min_lefthand = replace_relid(sjinf->min_lefthand, ojrelid, subst);
453  sjinf->min_righthand = replace_relid(sjinf->min_righthand, ojrelid, subst);
454  sjinf->syn_lefthand = replace_relid(sjinf->syn_lefthand, ojrelid, subst);
455  sjinf->syn_righthand = replace_relid(sjinf->syn_righthand, ojrelid, subst);
456  /* relid cannot appear in these fields, but ojrelid can: */
457  sjinf->commute_above_l = replace_relid(sjinf->commute_above_l, ojrelid, subst);
458  sjinf->commute_above_r = replace_relid(sjinf->commute_above_r, ojrelid, subst);
459  sjinf->commute_below_l = replace_relid(sjinf->commute_below_l, ojrelid, subst);
460  sjinf->commute_below_r = replace_relid(sjinf->commute_below_r, ojrelid, subst);
461 
462  replace_varno((Node *) sjinf->semi_rhs_exprs, relid, subst);
463  }
464 
465  /*
466  * Likewise remove references from PlaceHolderVar data structures,
467  * removing any no-longer-needed placeholders entirely.
468  *
469  * Removal is a bit trickier than it might seem: we can remove PHVs that
470  * are used at the target rel and/or in the join qual, but not those that
471  * are used at join partner rels or above the join. It's not that easy to
472  * distinguish PHVs used at partner rels from those used in the join qual,
473  * since they will both have ph_needed sets that are subsets of
474  * joinrelids. However, a PHV used at a partner rel could not have the
475  * target rel in ph_eval_at, so we check that while deciding whether to
476  * remove or just update the PHV. There is no corresponding test in
477  * join_is_removable because it doesn't need to distinguish those cases.
478  */
479  foreach(l, root->placeholder_list)
480  {
481  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
482 
483  Assert(sjinfo == NULL || !bms_is_member(relid, phinfo->ph_lateral));
484  if (bms_is_subset(phinfo->ph_needed, joinrelids) &&
485  bms_is_member(relid, phinfo->ph_eval_at) &&
486  (sjinfo == NULL || !bms_is_member(ojrelid, phinfo->ph_eval_at)))
487  {
489  l);
490  root->placeholder_array[phinfo->phid] = NULL;
491  }
492  else
493  {
494  PlaceHolderVar *phv = phinfo->ph_var;
495 
496  phinfo->ph_eval_at = replace_relid(phinfo->ph_eval_at, relid, subst);
497  phinfo->ph_eval_at = replace_relid(phinfo->ph_eval_at, ojrelid, subst);
498  Assert(!bms_is_empty(phinfo->ph_eval_at)); /* checked previously */
499  phinfo->ph_needed = replace_relid(phinfo->ph_needed, relid, subst);
500  phinfo->ph_needed = replace_relid(phinfo->ph_needed, ojrelid, subst);
501  /* ph_needed might or might not become empty */
502  phinfo->ph_lateral = replace_relid(phinfo->ph_lateral, relid, subst);
503  /* ph_lateral might or might not be empty */
504  phv->phrels = replace_relid(phv->phrels, relid, subst);
505  phv->phrels = replace_relid(phv->phrels, ojrelid, subst);
506  Assert(!bms_is_empty(phv->phrels));
507  replace_varno((Node *) phv->phexpr, relid, subst);
508  Assert(phv->phnullingrels == NULL); /* no need to adjust */
509  }
510  }
511 }
static bool replace_varno_walker(Node *node, ReplaceVarnoContext *ctx)
static Bitmapset * replace_relid(Relids relids, int oldId, int newId)
#define query_tree_walker(q, w, c, f)
Definition: nodeFuncs.h:156
#define QTW_EXAMINE_SORTGROUP
Definition: nodeFuncs.h:30
Relids phnullingrels
Definition: pathnodes.h:2768
int simple_rel_array_size
Definition: pathnodes.h:229
Relids all_query_rels
Definition: pathnodes.h:266
Relids outer_join_rels
Definition: pathnodes.h:258
bool hasLateralRTEs
Definition: pathnodes.h:491
Relids all_baserels
Definition: pathnodes.h:252
TableFunc * tablefunc
Definition: parsenodes.h:1146
struct TableSampleClause * tablesample
Definition: parsenodes.h:1067
Query * subquery
Definition: parsenodes.h:1073
List * values_lists
Definition: parsenodes.h:1151
List * functions
Definition: parsenodes.h:1140
List * lateral_vars
Definition: pathnodes.h:921
Relids syn_lefthand
Definition: pathnodes.h:2870
List * semi_rhs_exprs
Definition: pathnodes.h:2883
Relids commute_above_l
Definition: pathnodes.h:2874
Relids syn_righthand
Definition: pathnodes.h:2871
Relids commute_below_r
Definition: pathnodes.h:2877

References PlannerInfo::all_baserels, PlannerInfo::all_query_rels, Assert(), bms_is_empty, bms_is_member(), bms_is_subset(), SpecialJoinInfo::commute_above_l, SpecialJoinInfo::commute_above_r, SpecialJoinInfo::commute_below_l, SpecialJoinInfo::commute_below_r, foreach_delete_current, ReplaceVarnoContext::from, RangeTblEntry::functions, PlannerInfo::hasLateralRTEs, PlannerInfo::join_info_list, RangeTblEntry::lateral, RelOptInfo::lateral_vars, lfirst, RelOptInfo::max_attr, RelOptInfo::min_attr, SpecialJoinInfo::min_lefthand, SpecialJoinInfo::min_righthand, SpecialJoinInfo::ojrelid, PlannerInfo::outer_join_rels, PlaceHolderInfo::ph_eval_at, PlaceHolderInfo::ph_lateral, PlaceHolderInfo::ph_needed, PlaceHolderInfo::ph_var, PlaceHolderInfo::phid, PlaceHolderVar::phnullingrels, PlannerInfo::placeholder_list, pull_varnos(), QTW_EXAMINE_SORTGROUP, query_tree_walker, RelOptInfo::relid, replace_relid(), replace_varno(), replace_varno_walker(), RTE_SUBQUERY, RelOptInfo::rtekind, SpecialJoinInfo::semi_rhs_exprs, PlannerInfo::simple_rel_array_size, RangeTblEntry::subquery, SpecialJoinInfo::syn_lefthand, SpecialJoinInfo::syn_righthand, RangeTblEntry::tablefunc, RangeTblEntry::tablesample, and RangeTblEntry::values_lists.

Referenced by remove_leftjoinrel_from_query(), and remove_self_join_rel().

◆ remove_rel_from_restrictinfo()

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

Definition at line 638 of file analyzejoins.c.

639 {
640  /*
641  * The clause_relids probably aren't shared with anything else, but let's
642  * copy them just to be sure.
643  */
644  rinfo->clause_relids = bms_copy(rinfo->clause_relids);
645  rinfo->clause_relids = bms_del_member(rinfo->clause_relids, relid);
646  rinfo->clause_relids = bms_del_member(rinfo->clause_relids, ojrelid);
647  /* Likewise for required_relids */
648  rinfo->required_relids = bms_copy(rinfo->required_relids);
649  rinfo->required_relids = bms_del_member(rinfo->required_relids, relid);
650  rinfo->required_relids = bms_del_member(rinfo->required_relids, ojrelid);
651 
652  /* If it's an OR, recurse to clean up sub-clauses */
653  if (restriction_is_or_clause(rinfo))
654  {
655  ListCell *lc;
656 
657  Assert(is_orclause(rinfo->orclause));
658  foreach(lc, ((BoolExpr *) rinfo->orclause)->args)
659  {
660  Node *orarg = (Node *) lfirst(lc);
661 
662  /* OR arguments should be ANDs or sub-RestrictInfos */
663  if (is_andclause(orarg))
664  {
665  List *andargs = ((BoolExpr *) orarg)->args;
666  ListCell *lc2;
667 
668  foreach(lc2, andargs)
669  {
670  RestrictInfo *rinfo2 = lfirst_node(RestrictInfo, lc2);
671 
672  remove_rel_from_restrictinfo(rinfo2, relid, ojrelid);
673  }
674  }
675  else
676  {
677  RestrictInfo *rinfo2 = castNode(RestrictInfo, orarg);
678 
679  remove_rel_from_restrictinfo(rinfo2, relid, ojrelid);
680  }
681  }
682  }
683 }
static bool is_andclause(const void *clause)
Definition: nodeFuncs.h:105
static bool is_orclause(const void *clause)
Definition: nodeFuncs.h:114
bool restriction_is_or_clause(RestrictInfo *restrictinfo)
Definition: restrictinfo.c:416

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_leftjoinrel_from_query(), and remove_rel_from_eclass().

◆ remove_self_join_rel()

static void remove_self_join_rel ( PlannerInfo root,
PlanRowMark kmark,
PlanRowMark rmark,
RelOptInfo toKeep,
RelOptInfo toRemove,
List restrictlist 
)
static

Definition at line 1742 of file analyzejoins.c.

1745 {
1746  List *joininfos;
1747  ListCell *lc;
1748  int i;
1749  List *jinfo_candidates = NIL;
1750  List *binfo_candidates = NIL;
1751  ReplaceVarnoContext ctx = {.from = toRemove->relid,.to = toKeep->relid};
1752 
1753  Assert(toKeep->relid != -1);
1754 
1755  /*
1756  * Replace the index of the removing table with the keeping one. The
1757  * technique of removing/distributing restrictinfo is used here to attach
1758  * just appeared (for keeping relation) join clauses and avoid adding
1759  * duplicates of those that already exist in the joininfo list.
1760  */
1761  joininfos = list_copy(toRemove->joininfo);
1762  foreach(lc, joininfos)
1763  {
1764  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1765 
1766  remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);
1767  replace_varno((Node *) rinfo, toRemove->relid, toKeep->relid);
1768 
1770  jinfo_candidates = lappend(jinfo_candidates, rinfo);
1771  else
1772  binfo_candidates = lappend(binfo_candidates, rinfo);
1773  }
1774 
1775  /*
1776  * Concatenate restrictlist to the list of base restrictions of the
1777  * removing table just to simplify the replacement procedure: all of them
1778  * weren't connected to any keeping relations and need to be added to some
1779  * rels.
1780  */
1781  toRemove->baserestrictinfo = list_concat(toRemove->baserestrictinfo,
1782  restrictlist);
1783  foreach(lc, toRemove->baserestrictinfo)
1784  {
1785  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1786 
1787  replace_varno((Node *) rinfo, toRemove->relid, toKeep->relid);
1788 
1790  jinfo_candidates = lappend(jinfo_candidates, rinfo);
1791  else
1792  binfo_candidates = lappend(binfo_candidates, rinfo);
1793  }
1794 
1795  /*
1796  * Now, add all non-redundant clauses to the keeping relation.
1797  * Contradictory operation. On the one side, we reduce the length of
1798  * restrict lists that can impact planning or executing time.
1799  * Additionally, we improve the accuracy of cardinality estimation. On the
1800  * other side, it is one more place that can make planning time much
1801  * longer in specific cases. It would have been better to avoid calling
1802  * the equal() function here, but it's the only way to detect duplicated
1803  * inequality expressions.
1804  */
1805  foreach(lc, binfo_candidates)
1806  {
1807  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1808  ListCell *olc = NULL;
1809  bool is_redundant = false;
1810 
1811  Assert(!bms_is_member(toRemove->relid, rinfo->required_relids));
1812 
1813  foreach(olc, toKeep->baserestrictinfo)
1814  {
1815  RestrictInfo *src = lfirst_node(RestrictInfo, olc);
1816 
1817  if (!bms_equal(src->clause_relids, rinfo->clause_relids))
1818  /* Const and non-const expressions can't be equal */
1819  continue;
1820 
1821  if (src == rinfo ||
1822  (rinfo->parent_ec != NULL
1823  && src->parent_ec == rinfo->parent_ec)
1824  || restrict_infos_logically_equal(rinfo, src))
1825  {
1826  is_redundant = true;
1827  break;
1828  }
1829  }
1830  if (!is_redundant)
1831  distribute_restrictinfo_to_rels(root, rinfo);
1832  }
1833  foreach(lc, jinfo_candidates)
1834  {
1835  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1836  ListCell *olc = NULL;
1837  bool is_redundant = false;
1838 
1839  Assert(!bms_is_member(toRemove->relid, rinfo->required_relids));
1840 
1841  foreach(olc, toKeep->joininfo)
1842  {
1843  RestrictInfo *src = lfirst_node(RestrictInfo, olc);
1844 
1845  if (!bms_equal(src->clause_relids, rinfo->clause_relids))
1846  /* Can't compare trivially different clauses */
1847  continue;
1848 
1849  if (src == rinfo ||
1850  (rinfo->parent_ec != NULL
1851  && src->parent_ec == rinfo->parent_ec)
1852  || restrict_infos_logically_equal(rinfo, src))
1853  {
1854  is_redundant = true;
1855  break;
1856  }
1857  }
1858  if (!is_redundant)
1859  distribute_restrictinfo_to_rels(root, rinfo);
1860  }
1861  list_free(binfo_candidates);
1862  list_free(jinfo_candidates);
1863 
1864  /*
1865  * Arrange equivalence classes, mentioned removing a table, with the
1866  * keeping one: varno of removing table should be replaced in members and
1867  * sources lists. Also, remove duplicated elements if this replacement
1868  * procedure created them.
1869  */
1870  i = -1;
1871  while ((i = bms_next_member(toRemove->eclass_indexes, i)) >= 0)
1872  {
1874 
1875  update_eclasses(ec, toRemove->relid, toKeep->relid);
1876  toKeep->eclass_indexes = bms_add_member(toKeep->eclass_indexes, i);
1877  }
1878 
1879  /*
1880  * Transfer the targetlist and attr_needed flags.
1881  */
1882 
1883  foreach(lc, toRemove->reltarget->exprs)
1884  {
1885  Node *node = lfirst(lc);
1886 
1887  replace_varno(node, toRemove->relid, toKeep->relid);
1888  if (!list_member(toKeep->reltarget->exprs, node))
1889  toKeep->reltarget->exprs = lappend(toKeep->reltarget->exprs, node);
1890  }
1891 
1892  for (i = toKeep->min_attr; i <= toKeep->max_attr; i++)
1893  {
1894  int attno = i - toKeep->min_attr;
1895 
1896  toRemove->attr_needed[attno] = replace_relid(toRemove->attr_needed[attno],
1897  toRemove->relid, toKeep->relid);
1898  toKeep->attr_needed[attno] = bms_add_members(toKeep->attr_needed[attno],
1899  toRemove->attr_needed[attno]);
1900  }
1901 
1902  /*
1903  * If the removed relation has a row mark, transfer it to the remaining
1904  * one.
1905  *
1906  * If both rels have row marks, just keep the one corresponding to the
1907  * remaining relation, because we verified earlier that they have the same
1908  * strength.
1909  */
1910  if (rmark)
1911  {
1912  if (kmark)
1913  {
1914  Assert(kmark->markType == rmark->markType);
1915 
1916  root->rowMarks = list_delete_ptr(root->rowMarks, rmark);
1917  }
1918  else
1919  {
1920  /* Shouldn't have inheritance children here. */
1921  Assert(rmark->rti == rmark->prti);
1922 
1923  rmark->rti = rmark->prti = toKeep->relid;
1924  }
1925  }
1926 
1927  /* Replace varno in all the query structures */
1930 
1931  /* See remove_self_joins_one_group() */
1932  Assert(root->parse->resultRelation != toRemove->relid);
1933  Assert(root->parse->resultRelation != toKeep->relid);
1934 
1935  /* Replace links in the planner info */
1936  remove_rel_from_query(root, toRemove, toKeep->relid, NULL, NULL);
1937 
1938  /* At last, replace varno in root targetlist and HAVING clause */
1940  toRemove->relid, toKeep->relid);
1942  toRemove->relid, toKeep->relid);
1943  replace_relid(root->all_result_relids, toRemove->relid, toKeep->relid);
1944  replace_relid(root->leaf_result_relids, toRemove->relid, toKeep->relid);
1945 
1946 
1947  /*
1948  * There may be references to the rel in root->fkey_list, but if so,
1949  * match_foreign_keys_to_quals() will get rid of them.
1950  */
1951 
1952  /*
1953  * Finally, remove the rel from the baserel array to prevent it from being
1954  * referenced again. (We can't do this earlier because
1955  * remove_join_clause_from_rels will touch it.)
1956  */
1957  root->simple_rel_array[toRemove->relid] = NULL;
1958 
1959  /* And nuke the RelOptInfo, just in case there's another access path */
1960  pfree(toRemove);
1961 }
static void update_eclasses(EquivalenceClass *ec, int from, int to)
static bool restrict_infos_logically_equal(RestrictInfo *a, RestrictInfo *b)
int bms_next_member(const Bitmapset *a, int prevbit)
Definition: bitmapset.c:1319
BMS_Membership bms_membership(const Bitmapset *a)
Definition: bitmapset.c:794
@ BMS_MULTIPLE
Definition: bitmapset.h:73
int i
Definition: isn.c:73
List * list_delete_ptr(List *list, void *datum)
Definition: list.c:872
void list_free(List *list)
Definition: list.c:1546
bool list_member(const List *list, const void *datum)
Definition: list.c:661
static void * list_nth(const List *list, int n)
Definition: pg_list.h:299
List * exprs
Definition: pathnodes.h:1513
Index prti
Definition: plannodes.h:1381
RowMarkType markType
Definition: plannodes.h:1383
List * processed_tlist
Definition: pathnodes.h:453
List * processed_groupClause
Definition: pathnodes.h:430
List * rowMarks
Definition: pathnodes.h:368
Relids all_result_relids
Definition: pathnodes.h:351
Relids leaf_result_relids
Definition: pathnodes.h:353
struct PathTarget * reltarget
Definition: pathnodes.h:878
Bitmapset * eclass_indexes
Definition: pathnodes.h:933

References PlannerInfo::all_result_relids, Assert(), RelOptInfo::baserestrictinfo, bms_add_member(), bms_add_members(), bms_equal(), bms_is_member(), bms_membership(), BMS_MULTIPLE, bms_next_member(), distribute_restrictinfo_to_rels(), RelOptInfo::eclass_indexes, PlannerInfo::eq_classes, PathTarget::exprs, ReplaceVarnoContext::from, i, RelOptInfo::joininfo, lappend(), PlannerInfo::leaf_result_relids, lfirst, lfirst_node, list_concat(), list_copy(), list_delete_ptr(), list_free(), list_member(), list_nth(), PlanRowMark::markType, RelOptInfo::min_attr, NIL, PlannerInfo::parse, pfree(), PlannerInfo::processed_groupClause, PlannerInfo::processed_tlist, PlanRowMark::prti, QTW_EXAMINE_SORTGROUP, query_tree_walker, RelOptInfo::relid, RelOptInfo::reltarget, remove_join_clause_from_rels(), remove_rel_from_query(), replace_relid(), replace_varno(), replace_varno_walker(), RestrictInfo::required_relids, restrict_infos_logically_equal(), PlannerInfo::rowMarks, PlanRowMark::rti, and update_eclasses().

Referenced by remove_self_joins_one_group().

◆ remove_self_joins_one_group()

static Relids remove_self_joins_one_group ( PlannerInfo root,
Relids  relids 
)
static

Definition at line 2108 of file analyzejoins.c.

2109 {
2110  Relids result = NULL;
2111  int k; /* Index of kept relation */
2112  int r = -1; /* Index of removed relation */
2113 
2114  while ((r = bms_next_member(relids, r)) > 0)
2115  {
2116  RelOptInfo *inner = root->simple_rel_array[r];
2117 
2118  /*
2119  * We don't accept result relation as either source or target relation
2120  * of SJE, because result relation has different behavior in
2121  * EvalPlanQual() and RETURNING clause.
2122  */
2123  if (root->parse->resultRelation == r)
2124  continue;
2125 
2126  k = r;
2127 
2128  while ((k = bms_next_member(relids, k)) > 0)
2129  {
2130  Relids joinrelids = NULL;
2131  RelOptInfo *outer = root->simple_rel_array[k];
2132  List *restrictlist;
2133  List *selfjoinquals;
2134  List *otherjoinquals;
2135  ListCell *lc;
2136  bool jinfo_check = true;
2137  PlanRowMark *omark = NULL;
2138  PlanRowMark *imark = NULL;
2139  List *uclauses = NIL;
2140 
2141  if (root->parse->resultRelation == k)
2142  continue;
2143 
2144  /* A sanity check: the relations have the same Oid. */
2145  Assert(root->simple_rte_array[k]->relid ==
2146  root->simple_rte_array[r]->relid);
2147 
2148  /*
2149  * It is impossible to eliminate join of two relations if they
2150  * belong to different rules of order. Otherwise planner can't be
2151  * able to find any variants of correct query plan.
2152  */
2153  foreach(lc, root->join_info_list)
2154  {
2155  SpecialJoinInfo *info = (SpecialJoinInfo *) lfirst(lc);
2156 
2157  if ((bms_is_member(k, info->syn_lefthand) ^
2158  bms_is_member(r, info->syn_lefthand)) ||
2159  (bms_is_member(k, info->syn_righthand) ^
2160  bms_is_member(r, info->syn_righthand)))
2161  {
2162  jinfo_check = false;
2163  break;
2164  }
2165  }
2166  if (!jinfo_check)
2167  continue;
2168 
2169  /*
2170  * Check Row Marks equivalence. We can't remove the join if the
2171  * relations have row marks of different strength (e.g. one is
2172  * locked FOR UPDATE and another just has ROW_MARK_REFERENCE for
2173  * EvalPlanQual rechecking).
2174  */
2175  foreach(lc, root->rowMarks)
2176  {
2177  PlanRowMark *rowMark = (PlanRowMark *) lfirst(lc);
2178 
2179  if (rowMark->rti == k)
2180  {
2181  Assert(imark == NULL);
2182  imark = rowMark;
2183  }
2184  else if (rowMark->rti == r)
2185  {
2186  Assert(omark == NULL);
2187  omark = rowMark;
2188  }
2189 
2190  if (omark && imark)
2191  break;
2192  }
2193  if (omark && imark && omark->markType != imark->markType)
2194  continue;
2195 
2196  /*
2197  * We only deal with base rels here, so their relids bitset
2198  * contains only one member -- their relid.
2199  */
2200  joinrelids = bms_add_member(joinrelids, r);
2201  joinrelids = bms_add_member(joinrelids, k);
2202 
2203  /*
2204  * PHVs should not impose any constraints on removing self joins.
2205  */
2206 
2207  /*
2208  * At this stage, joininfo lists of inner and outer can contain
2209  * only clauses, required for a superior outer join that can't
2210  * influence this optimization. So, we can avoid to call the
2211  * build_joinrel_restrictlist() routine.
2212  */
2213  restrictlist = generate_join_implied_equalities(root, joinrelids,
2214  inner->relids,
2215  outer, NULL);
2216 
2217  /*
2218  * Process restrictlist to separate the self join quals out of the
2219  * other quals. e.g x = x goes to selfjoinquals and a = b to
2220  * otherjoinquals.
2221  */
2222  split_selfjoin_quals(root, restrictlist, &selfjoinquals,
2223  &otherjoinquals, inner->relid, outer->relid);
2224 
2225  /*
2226  * To enable SJE for the only degenerate case without any self
2227  * join clauses at all, add baserestrictinfo to this list. The
2228  * degenerate case works only if both sides have the same clause.
2229  * So doesn't matter which side to add.
2230  */
2231  selfjoinquals = list_concat(selfjoinquals, outer->baserestrictinfo);
2232 
2233  /*
2234  * Determine if the inner table can duplicate outer rows. We must
2235  * bypass the unique rel cache here since we're possibly using a
2236  * subset of join quals. We can use 'force_cache' == true when all
2237  * join quals are self-join quals. Otherwise, we could end up
2238  * putting false negatives in the cache.
2239  */
2240  if (!innerrel_is_unique_ext(root, joinrelids, inner->relids,
2241  outer, JOIN_INNER, selfjoinquals,
2242  list_length(otherjoinquals) == 0,
2243  &uclauses))
2244  continue;
2245 
2246  /*
2247  * We have proven that for both relations, the same unique index
2248  * guarantees that there is at most one row where columns equal
2249  * given values. These values must be the same for both relations,
2250  * or else we won't match the same row on each side of the join.
2251  */
2252  if (!match_unique_clauses(root, inner, uclauses, outer->relid))
2253  continue;
2254 
2255  /*
2256  * We can remove either relation, so remove the inner one in order
2257  * to simplify this loop.
2258  */
2259  remove_self_join_rel(root, omark, imark, outer, inner, restrictlist);
2260 
2261  result = bms_add_member(result, r);
2262 
2263  /* We have removed the outer relation, try the next one. */
2264  break;
2265  }
2266  }
2267 
2268  return result;
2269 }
static bool match_unique_clauses(PlannerInfo *root, RelOptInfo *outer, List *uclauses, Index relid)
static void split_selfjoin_quals(PlannerInfo *root, List *joinquals, List **selfjoinquals, List **otherjoinquals, int from, int to)
static void remove_self_join_rel(PlannerInfo *root, PlanRowMark *kmark, PlanRowMark *rmark, RelOptInfo *toKeep, RelOptInfo *toRemove, List *restrictlist)
@ JOIN_INNER
Definition: nodes.h:283

References Assert(), RelOptInfo::baserestrictinfo, bms_add_member(), bms_is_member(), bms_next_member(), generate_join_implied_equalities(), innerrel_is_unique_ext(), PlannerInfo::join_info_list, JOIN_INNER, lfirst, list_concat(), list_length(), PlanRowMark::markType, match_unique_clauses(), NIL, PlannerInfo::parse, RelOptInfo::relid, RelOptInfo::relids, remove_self_join_rel(), PlannerInfo::rowMarks, PlanRowMark::rti, split_selfjoin_quals(), SpecialJoinInfo::syn_lefthand, and SpecialJoinInfo::syn_righthand.

Referenced by remove_self_joins_recurse().

◆ remove_self_joins_recurse()

static Relids remove_self_joins_recurse ( PlannerInfo root,
List joinlist,
Relids  toRemove 
)
static

Definition at line 2276 of file analyzejoins.c.

2277 {
2278  ListCell *jl;
2279  Relids relids = NULL;
2280  SelfJoinCandidate *candidates = NULL;
2281  int i;
2282  int j;
2283  int numRels;
2284 
2285  /* Collect indexes of base relations of the join tree */
2286  foreach(jl, joinlist)
2287  {
2288  Node *jlnode = (Node *) lfirst(jl);
2289 
2290  if (IsA(jlnode, RangeTblRef))
2291  {
2292  RangeTblRef *ref = (RangeTblRef *) jlnode;
2293  RangeTblEntry *rte = root->simple_rte_array[ref->rtindex];
2294 
2295  /*
2296  * We only care about base relations from which we select
2297  * something.
2298  */
2299  if (rte->rtekind == RTE_RELATION &&
2300  rte->relkind == RELKIND_RELATION &&
2301  root->simple_rel_array[ref->rtindex] != NULL)
2302  {
2303  Assert(!bms_is_member(ref->rtindex, relids));
2304  relids = bms_add_member(relids, ref->rtindex);
2305  }
2306  }
2307  else if (IsA(jlnode, List))
2308  /* Recursively go inside the sub-joinlist */
2309  toRemove = remove_self_joins_recurse(root, (List *) jlnode,
2310  toRemove);
2311  else
2312  elog(ERROR, "unrecognized joinlist node type: %d",
2313  (int) nodeTag(jlnode));
2314  }
2315 
2316  numRels = bms_num_members(relids);
2317 
2318  /* Need at least two relations for the join */
2319  if (numRels < 2)
2320  return toRemove;
2321 
2322  /*
2323  * In order to find relations with the same oid we first build an array of
2324  * candidates and then sort it by oid.
2325  */
2326  candidates = (SelfJoinCandidate *) palloc(sizeof(SelfJoinCandidate) *
2327  numRels);
2328  i = -1;
2329  j = 0;
2330  while ((i = bms_next_member(relids, i)) >= 0)
2331  {
2332  candidates[j].relid = i;
2333  candidates[j].reloid = root->simple_rte_array[i]->relid;
2334  j++;
2335  }
2336 
2337  qsort(candidates, numRels, sizeof(SelfJoinCandidate),
2339 
2340  /*
2341  * Iteratively form a group of relation indexes with the same oid and
2342  * launch the routine that detects self-joins in this group and removes
2343  * excessive range table entries.
2344  *
2345  * At the end of the iteration, exclude the group from the overall relids
2346  * list. So each next iteration of the cycle will involve less and less
2347  * value of relids.
2348  */
2349  i = 0;
2350  for (j = 1; j < numRels + 1; j++)
2351  {
2352  if (j == numRels || candidates[j].reloid != candidates[i].reloid)
2353  {
2354  if (j - i >= 2)
2355  {
2356  /* Create a group of relation indexes with the same oid */
2357  Relids group = NULL;
2358  Relids removed;
2359 
2360  while (i < j)
2361  {
2362  group = bms_add_member(group, candidates[i].relid);
2363  i++;
2364  }
2365 
2366  relids = bms_del_members(relids, group);
2367 
2368  /*
2369  * Try to remove self-joins from a group of identical entries.
2370  * Make the next attempt iteratively - if something is deleted
2371  * from a group, changes in clauses and equivalence classes
2372  * can give us a chance to find more candidates.
2373  */
2374  do
2375  {
2376  Assert(!bms_overlap(group, toRemove));
2377  removed = remove_self_joins_one_group(root, group);
2378  toRemove = bms_add_members(toRemove, removed);
2379  group = bms_del_members(group, removed);
2380  } while (!bms_is_empty(removed) &&
2381  bms_membership(group) == BMS_MULTIPLE);
2382  bms_free(removed);
2383  bms_free(group);
2384  }
2385  else
2386  {
2387  /* Single relation, just remove it from the set */
2388  relids = bms_del_member(relids, candidates[i].relid);
2389  i = j;
2390  }
2391  }
2392  }
2393 
2394  Assert(bms_is_empty(relids));
2395 
2396  return toRemove;
2397 }
static int self_join_candidates_cmp(const void *a, const void *b)
static Relids remove_self_joins_one_group(PlannerInfo *root, Relids relids)
static Relids remove_self_joins_recurse(PlannerInfo *root, List *joinlist, Relids toRemove)
void bms_free(Bitmapset *a)
Definition: bitmapset.c:252
int bms_num_members(const Bitmapset *a)
Definition: bitmapset.c:764
Bitmapset * bms_del_members(Bitmapset *a, const Bitmapset *b)
Definition: bitmapset.c:1174
int j
Definition: isn.c:74
void * palloc(Size size)
Definition: mcxt.c:1201
#define qsort(a, b, c, d)
Definition: port.h:449
RTEKind rtekind
Definition: parsenodes.h:1025

References Assert(), bms_add_member(), bms_add_members(), bms_del_member(), bms_del_members(), bms_free(), bms_is_empty, bms_is_member(), bms_membership(), BMS_MULTIPLE, bms_next_member(), bms_num_members(), bms_overlap(), elog(), ERROR, i, IsA, j, lfirst, nodeTag, palloc(), qsort, SelfJoinCandidate::relid, RangeTblEntry::relkind, SelfJoinCandidate::reloid, remove_self_joins_one_group(), RTE_RELATION, RangeTblEntry::rtekind, RangeTblRef::rtindex, and self_join_candidates_cmp().

Referenced by remove_useless_self_joins().

◆ remove_useless_joins()

List* remove_useless_joins ( PlannerInfo root,
List joinlist 
)

Definition at line 94 of file analyzejoins.c.

95 {
96  ListCell *lc;
97 
98  /*
99  * We are only interested in relations that are left-joined to, so we can
100  * scan the join_info_list to find them easily.
101  */
102 restart:
103  foreach(lc, root->join_info_list)
104  {
105  SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
106  int innerrelid;
107  int nremoved;
108 
109  /* Skip if not removable */
110  if (!join_is_removable(root, sjinfo))
111  continue;
112 
113  /*
114  * Currently, join_is_removable can only succeed when the sjinfo's
115  * righthand is a single baserel. Remove that rel from the query and
116  * joinlist.
117  */
118  innerrelid = bms_singleton_member(sjinfo->min_righthand);
119 
120  remove_leftjoinrel_from_query(root, innerrelid, sjinfo);
121 
122  /* We verify that exactly one reference gets removed from joinlist */
123  nremoved = 0;
124  joinlist = remove_rel_from_joinlist(joinlist, innerrelid, &nremoved);
125  if (nremoved != 1)
126  elog(ERROR, "failed to find relation %d in joinlist", innerrelid);
127 
128  /*
129  * We can delete this SpecialJoinInfo from the list too, since it's no
130  * longer of interest. (Since we'll restart the foreach loop
131  * immediately, we don't bother with foreach_delete_current.)
132  */
134 
135  /*
136  * Restart the scan. This is necessary to ensure we find all
137  * removable joins independently of ordering of the join_info_list
138  * (note that removal of attr_needed bits may make a join appear
139  * removable that did not before).
140  */
141  goto restart;
142  }
143 
144  return joinlist;
145 }
static void remove_leftjoinrel_from_query(PlannerInfo *root, int relid, SpecialJoinInfo *sjinfo)
Definition: analyzejoins.c:522
static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
Definition: analyzejoins.c:190
int bms_singleton_member(const Bitmapset *a)
Definition: bitmapset.c:685
List * list_delete_cell(List *list, ListCell *cell)
Definition: list.c:841

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

Referenced by query_planner().

◆ remove_useless_self_joins()

List* remove_useless_self_joins ( PlannerInfo root,
List joinlist 
)

Definition at line 2450 of file analyzejoins.c.

2451 {
2452  Relids toRemove = NULL;
2453  int relid = -1;
2454 
2455  if (!enable_self_join_removal || joinlist == NIL ||
2456  (list_length(joinlist) == 1 && !IsA(linitial(joinlist), List)))
2457  return joinlist;
2458 
2459  /*
2460  * Merge pairs of relations participated in self-join. Remove unnecessary
2461  * range table entries.
2462  */
2463  toRemove = remove_self_joins_recurse(root, joinlist, toRemove);
2464 
2465  if (unlikely(toRemove != NULL))
2466  {
2467  int nremoved = 0;
2468 
2469  /* At the end, remove orphaned relation links */
2470  while ((relid = bms_next_member(toRemove, relid)) >= 0)
2471  joinlist = remove_rel_from_joinlist(joinlist, relid, &nremoved);
2472  }
2473 
2474  return joinlist;
2475 }
bool enable_self_join_removal
Definition: analyzejoins.c:55
#define unlikely(x)
Definition: c.h:300

References bms_next_member(), enable_self_join_removal, IsA, linitial, list_length(), NIL, remove_rel_from_joinlist(), remove_self_joins_recurse(), and unlikely.

Referenced by query_planner().

◆ replace_relid()

static Bitmapset * replace_relid ( Relids  relids,
int  oldId,
int  newId 
)
static

Definition at line 1570 of file analyzejoins.c.

1571 {
1572  if (oldId < 0)
1573  return relids;
1574 
1575  /* Delete relid without substitution. */
1576  if (newId < 0)
1577  return bms_del_member(bms_copy(relids), oldId);
1578 
1579  /* Substitute newId for oldId. */
1580  if (bms_is_member(oldId, relids))
1581  return bms_add_member(bms_del_member(bms_copy(relids), oldId), newId);
1582 
1583  return relids;
1584 }

References bms_add_member(), bms_copy(), bms_del_member(), and bms_is_member().

Referenced by remove_rel_from_query(), remove_self_join_rel(), replace_varno_walker(), and update_eclasses().

◆ replace_varno()

static void replace_varno ( Node node,
int  from,
int  to 
)
static

Definition at line 1468 of file analyzejoins.c.

1469 {
1470  ReplaceVarnoContext ctx;
1471 
1472  if (to <= 0)
1473  return;
1474 
1475  ctx.from = from;
1476  ctx.to = to;
1477  replace_varno_walker(node, &ctx);
1478 }

References ReplaceVarnoContext::from, replace_varno_walker(), and ReplaceVarnoContext::to.

Referenced by match_unique_clauses(), remove_rel_from_query(), remove_self_join_rel(), replace_varno_walker(), split_selfjoin_quals(), and update_eclasses().

◆ replace_varno_walker()

static bool replace_varno_walker ( Node node,
ReplaceVarnoContext ctx 
)
static

Definition at line 1484 of file analyzejoins.c.

1485 {
1486  if (node == NULL)
1487  return false;
1488 
1489  if (IsA(node, Var))
1490  {
1491  Var *var = (Var *) node;
1492 
1493  if (var->varno == ctx->from)
1494  {
1495  var->varno = ctx->to;
1496  var->varnosyn = ctx->to;
1497  }
1498  return false;
1499  }
1500  else if (IsA(node, PlaceHolderVar))
1501  {
1502  PlaceHolderVar *phv = (PlaceHolderVar *) node;
1503 
1504  phv->phrels = replace_relid(phv->phrels, ctx->from, ctx->to);
1505  phv->phnullingrels = replace_relid(phv->phnullingrels, ctx->from, ctx->to);
1506 
1507  /* fall through to recurse into the placeholder's expression */
1508  }
1509  else if (IsA(node, RestrictInfo))
1510  {
1511  RestrictInfo *rinfo = (RestrictInfo *) node;
1512  int relid = -1;
1513  bool is_req_equal =
1514  (rinfo->required_relids == rinfo->clause_relids);
1515 
1516  if (bms_is_member(ctx->from, rinfo->clause_relids))
1517  {
1518  replace_varno((Node *) rinfo->clause, ctx->from, ctx->to);
1519  replace_varno((Node *) rinfo->orclause, ctx->from, ctx->to);
1520  rinfo->clause_relids = replace_relid(rinfo->clause_relids, ctx->from, ctx->to);
1521  rinfo->left_relids = replace_relid(rinfo->left_relids, ctx->from, ctx->to);
1522  rinfo->right_relids = replace_relid(rinfo->right_relids, ctx->from, ctx->to);
1523  }
1524 
1525  if (is_req_equal)
1526  rinfo->required_relids = rinfo->clause_relids;
1527  else
1528  rinfo->required_relids = replace_relid(rinfo->required_relids, ctx->from, ctx->to);
1529 
1530  rinfo->outer_relids = replace_relid(rinfo->outer_relids, ctx->from, ctx->to);
1531  rinfo->incompatible_relids = replace_relid(rinfo->incompatible_relids, ctx->from, ctx->to);
1532 
1533  if (rinfo->mergeopfamilies &&
1534  bms_get_singleton_member(rinfo->clause_relids, &relid) &&
1535  relid == ctx->to && IsA(rinfo->clause, OpExpr))
1536  {
1537  Expr *leftOp;
1538  Expr *rightOp;
1539 
1540  leftOp = (Expr *) get_leftop(rinfo->clause);
1541  rightOp = (Expr *) get_rightop(rinfo->clause);
1542 
1543  if (leftOp != NULL && equal(leftOp, rightOp))
1544  {
1545  NullTest *ntest = makeNode(NullTest);
1546 
1547  ntest->arg = leftOp;
1548  ntest->nulltesttype = IS_NOT_NULL;
1549  ntest->argisrow = false;
1550  ntest->location = -1;
1551  rinfo->clause = (Expr *) ntest;
1552  rinfo->mergeopfamilies = NIL;
1553  }
1554  Assert(rinfo->orclause == NULL);
1555  }
1556 
1557  return false;
1558  }
1559  return expression_tree_walker(node, replace_varno_walker, (void *) ctx);
1560 }
#define expression_tree_walker(n, w, c)
Definition: nodeFuncs.h:151
@ IS_NOT_NULL
Definition: primnodes.h:1694
NullTestType nulltesttype
Definition: primnodes.h:1701
int location
Definition: primnodes.h:1704
Expr * arg
Definition: primnodes.h:1700
Relids outer_relids
Definition: pathnodes.h:2578
Relids incompatible_relids
Definition: pathnodes.h:2575

References NullTest::arg, Assert(), bms_get_singleton_member(), bms_is_member(), RestrictInfo::clause, equal(), expression_tree_walker, ReplaceVarnoContext::from, get_leftop(), get_rightop(), RestrictInfo::incompatible_relids, IS_NOT_NULL, IsA, NullTest::location, makeNode, NIL, NullTest::nulltesttype, RestrictInfo::outer_relids, PlaceHolderVar::phnullingrels, replace_relid(), replace_varno(), RestrictInfo::required_relids, ReplaceVarnoContext::to, and Var::varno.

Referenced by remove_rel_from_query(), remove_self_join_rel(), and replace_varno().

◆ restrict_infos_logically_equal()

static bool restrict_infos_logically_equal ( RestrictInfo a,
RestrictInfo b 
)
static

Definition at line 1709 of file analyzejoins.c.

1710 {
1711  int saved_rinfo_serial = a->rinfo_serial;
1712  bool result;
1713 
1714  a->rinfo_serial = b->rinfo_serial;
1715  result = equal(a, b);
1716  a->rinfo_serial = saved_rinfo_serial;
1717 
1718  return result;
1719 }
int b
Definition: isn.c:70
int a
Definition: isn.c:69

References a, b, and equal().

Referenced by remove_self_join_rel().

◆ self_join_candidates_cmp()

static int self_join_candidates_cmp ( const void *  a,
const void *  b 
)
static

Definition at line 2403 of file analyzejoins.c.

2404 {
2405  const SelfJoinCandidate *ca = (const SelfJoinCandidate *) a;
2406  const SelfJoinCandidate *cb = (const SelfJoinCandidate *) b;
2407 
2408  if (ca->reloid != cb->reloid)
2409  return (ca->reloid < cb->reloid ? -1 : 1);
2410  else
2411  return 0;
2412 }

References a, b, and SelfJoinCandidate::reloid.

Referenced by remove_self_joins_recurse().

◆ split_selfjoin_quals()

static void split_selfjoin_quals ( PlannerInfo root,
List joinquals,
List **  selfjoinquals,
List **  otherjoinquals,
int  from,
int  to 
)
static

Definition at line 1973 of file analyzejoins.c.

1975 {
1976  ListCell *lc;
1977  List *sjoinquals = NIL;
1978  List *ojoinquals = NIL;
1979 
1980  foreach(lc, joinquals)
1981  {
1982  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1983  OpExpr *expr;
1984  Node *leftexpr;
1985  Node *rightexpr;
1986 
1987  /* In general, clause looks like F(arg1) = G(arg2) */
1988  if (!rinfo->mergeopfamilies ||
1989  bms_num_members(rinfo->clause_relids) != 2 ||
1990  bms_membership(rinfo->left_relids) != BMS_SINGLETON ||
1991  bms_membership(rinfo->right_relids) != BMS_SINGLETON)
1992  {
1993  ojoinquals = lappend(ojoinquals, rinfo);
1994  continue;
1995  }
1996 
1997  expr = (OpExpr *) rinfo->clause;
1998 
1999  if (!IsA(expr, OpExpr) || list_length(expr->args) != 2)
2000  {
2001  ojoinquals = lappend(ojoinquals, rinfo);
2002  continue;
2003  }
2004 
2005  leftexpr = get_leftop(rinfo->clause);
2006  rightexpr = copyObject(get_rightop(rinfo->clause));
2007 
2008  if (leftexpr && IsA(leftexpr, RelabelType))
2009  leftexpr = (Node *) ((RelabelType *) leftexpr)->arg;
2010  if (rightexpr && IsA(rightexpr, RelabelType))
2011  rightexpr = (Node *) ((RelabelType *) rightexpr)->arg;
2012 
2013  /*
2014  * Quite an expensive operation, narrowing the use case. For example,
2015  * when we have cast of the same var to different (but compatible)
2016  * types.
2017  */
2018  replace_varno(rightexpr, bms_singleton_member(rinfo->right_relids),
2019  bms_singleton_member(rinfo->left_relids));
2020 
2021  if (equal(leftexpr, rightexpr))
2022  sjoinquals = lappend(sjoinquals, rinfo);
2023  else
2024  ojoinquals = lappend(ojoinquals, rinfo);
2025  }
2026 
2027  *selfjoinquals = sjoinquals;
2028  *otherjoinquals = ojoinquals;
2029 }
@ BMS_SINGLETON
Definition: bitmapset.h:72
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:77
void * arg
List * args
Definition: primnodes.h:771

References arg, OpExpr::args, bms_membership(), bms_num_members(), BMS_SINGLETON, bms_singleton_member(), RestrictInfo::clause, copyObject, equal(), get_leftop(), get_rightop(), if(), IsA, lappend(), lfirst_node, list_length(), NIL, and replace_varno().

Referenced by remove_self_joins_one_group().

◆ update_eclasses()

static void update_eclasses ( EquivalenceClass ec,
int  from,
int  to 
)
static

Definition at line 1609 of file analyzejoins.c.

1610 {
1611  List *new_members = NIL;
1612  List *new_sources = NIL;
1613  ListCell *lc;
1614  ListCell *lc1;
1615 
1616  foreach(lc, ec->ec_members)
1617  {
1619  bool is_redundant = false;
1620 
1621  if (!bms_is_member(from, em->em_relids))
1622  {
1623  new_members = lappend(new_members, em);
1624  continue;
1625  }
1626 
1627  em->em_relids = replace_relid(em->em_relids, from, to);
1628  em->em_jdomain->jd_relids = replace_relid(em->em_jdomain->jd_relids, from, to);
1629 
1630  /* We only process inner joins */
1631  replace_varno((Node *) em->em_expr, from, to);
1632 
1633  foreach(lc1, new_members)
1634  {
1636 
1637  if (!equal(em->em_relids, other->em_relids))
1638  continue;
1639 
1640  if (equal(em->em_expr, other->em_expr))
1641  {
1642  is_redundant = true;
1643  break;
1644  }
1645  }
1646 
1647  if (!is_redundant)
1648  new_members = lappend(new_members, em);
1649  }
1650 
1651  list_free(ec->ec_members);
1652  ec->ec_members = new_members;
1653 
1654  list_free(ec->ec_derives);
1655  ec->ec_derives = NULL;
1656 
1657  /* Update EC source expressions */
1658  foreach(lc, ec->ec_sources)
1659  {
1660  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
1661  bool is_redundant = false;
1662 
1663  if (!bms_is_member(from, rinfo->required_relids))
1664  {
1665  new_sources = lappend(new_sources, rinfo);
1666  continue;
1667  }
1668 
1669  replace_varno((Node *) rinfo, from, to);
1670 
1671  /*
1672  * After switching the clause to the remaining relation, check it for
1673  * redundancy with existing ones. We don't have to check for
1674  * redundancy with derived clauses, because we've just deleted them.
1675  */
1676  foreach(lc1, new_sources)
1677  {
1678  RestrictInfo *other = lfirst_node(RestrictInfo, lc1);
1679 
1680  if (!equal(rinfo->clause_relids, other->clause_relids))
1681  continue;
1682 
1683  if (equal(rinfo->clause, other->clause))
1684  {
1685  is_redundant = true;
1686  break;
1687  }
1688  }
1689 
1690  if (!is_redundant)
1691  new_sources = lappend(new_sources, rinfo);
1692  }
1693 
1694  list_free(ec->ec_sources);
1695  ec->ec_sources = new_sources;
1696  ec->ec_relids = replace_relid(ec->ec_relids, from, to);
1697 }
JoinDomain * em_jdomain
Definition: pathnodes.h:1426
Relids jd_relids
Definition: pathnodes.h:1308

References bms_is_member(), RestrictInfo::clause, EquivalenceClass::ec_derives, EquivalenceClass::ec_members, EquivalenceClass::ec_relids, EquivalenceClass::ec_sources, EquivalenceMember::em_expr, EquivalenceMember::em_jdomain, EquivalenceMember::em_relids, equal(), JoinDomain::jd_relids, lappend(), lfirst_node, list_free(), NIL, replace_relid(), replace_varno(), and RestrictInfo::required_relids.

Referenced by remove_self_join_rel().

Variable Documentation

◆ enable_self_join_removal

bool enable_self_join_removal

Definition at line 55 of file analyzejoins.c.

Referenced by remove_useless_self_joins().