Debian Codegraph @

src/backend/optimizer/plan/analyzejoins.c

raw
1 /*-------------------------------------------------------------------------
2 *
3 * analyzejoins.c
4 * Routines for simplifying joins after initial query analysis
5 *
6 * While we do a great deal of join simplification in prep/prepjointree.c,
7 * certain optimizations cannot be performed at that stage for lack of
8 * detailed information about the query. The routines here are invoked
9 * after initsplan.c has done its work, and can do additional join removal
10 * and simplification steps based on the information extracted. The penalty
11 * is that we have to work harder to clean up after ourselves when we modify
12 * the query, since the derived data structures have to be updated too.
13 *
14 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
15 * Portions Copyright (c) 1994, Regents of the University of California
16 *
17 *
18 * IDENTIFICATION
19 * src/backend/optimizer/plan/analyzejoins.c
20 *
21 *-------------------------------------------------------------------------
22 */
23 #include "postgres.h"
24
25 #include "catalog/pg_class.h"
26 #include "nodes/nodeFuncs.h"
27 #include "optimizer/joininfo.h"
28 #include "optimizer/optimizer.h"
29 #include "optimizer/pathnode.h"
30 #include "optimizer/paths.h"
31 #include "optimizer/placeholder.h"
32 #include "optimizer/planmain.h"
33 #include "optimizer/restrictinfo.h"
34 #include "rewrite/rewriteManip.h"
35 #include "utils/lsyscache.h"
36
37 /*
38 * One element of the list passed to query_is_distinct_for_with_collations().
39 * Each entry names a subquery output column that the caller needs to be
40 * distinct over, plus the upper-level equality operator and its input
41 * collation, so that the subquery's own DISTINCT/GROUP BY/set-op clauses can
42 * be compared for compatibility.
43 */
44 typedef struct DistinctColInfo
45 {
46 int colno; /* subquery output column resno */
47 Oid opid; /* upper-level equality operator */
48 Oid collid; /* input collation of opid */
49 } DistinctColInfo;
50
51 /*
52 * Utility structure. A sorting procedure is needed to simplify the search
53 * of SJE-candidate baserels referencing the same database relation. Having
54 * collected all baserels from the query jointree, the planner sorts them
55 * according to the reloid value, groups them with the next pass and attempts
56 * to remove self-joins.
57 *
58 * Preliminary sorting prevents quadratic behavior that can be harmful in the
59 * case of numerous joins.
60 */
61 typedef struct
62 {
63 int relid;
64 Oid reloid;
65 } SelfJoinCandidate;
66
67 bool enable_self_join_elimination;
68
69 /* local functions */
70 static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
71 static void remove_leftjoinrel_from_query(PlannerInfo *root, int relid,
72 SpecialJoinInfo *sjinfo);
73 static void remove_rel_from_restrictinfo(RestrictInfo *rinfo,
74 int relid, int ojrelid);
75 static void remove_rel_from_eclass(PlannerInfo *root, EquivalenceClass *ec,
76 SpecialJoinInfo *sjinfo,
77 int relid, int subst);
78 static void remove_rel_from_restrictinfo_phvs(RestrictInfo *rinfo,
79 int relid, int ojrelid);
80 static Node *remove_rel_from_phvs(Node *node, int relid, int ojrelid);
81 static Node *remove_rel_from_phvs_mutator(Node *node, Relids removable);
82 static List *remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved);
83 static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel);
84 static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel,
85 List *clause_list, List **extra_clauses);
86 static bool query_is_distinct_for_with_collations(Query *query,
87 List *distinct_cols);
88 static DistinctColInfo *distinct_col_search(int colno, List *distinct_cols);
89 static bool is_innerrel_unique_for(PlannerInfo *root,
90 Relids joinrelids,
91 Relids outerrelids,
92 RelOptInfo *innerrel,
93 JoinType jointype,
94 List *restrictlist,
95 List **extra_clauses);
96 static int self_join_candidates_cmp(const void *a, const void *b);
97 static bool replace_relid_callback(Node *node,
98 ChangeVarNodes_context *context);
99
100
101 /*
102 * remove_useless_joins
103 * Check for relations that don't actually need to be joined at all,
104 * and remove them from the query.
105 *
106 * We are passed the current joinlist and return the updated list. Other
107 * data structures that have to be updated are accessible via "root".
108 */
109 List *
110 remove_useless_joins(PlannerInfo *root, List *joinlist)
111 {
112 ListCell *lc;
113
114 /*
115 * We are only interested in relations that are left-joined to, so we can
116 * scan the join_info_list to find them easily.
117 */
118 restart:
119 foreach(lc, root->join_info_list)
120 {
121 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
122 int innerrelid;
123 int nremoved;
124
125 /* Skip if not removable */
126 if (!join_is_removable(root, sjinfo))
127 continue;
128
129 /*
130 * Currently, join_is_removable can only succeed when the sjinfo's
131 * righthand is a single baserel. Remove that rel from the query and
132 * joinlist.
133 */
134 innerrelid = bms_singleton_member(sjinfo->min_righthand);
135
136 remove_leftjoinrel_from_query(root, innerrelid, sjinfo);
137
138 /* We verify that exactly one reference gets removed from joinlist */
139 nremoved = 0;
140 joinlist = remove_rel_from_joinlist(joinlist, innerrelid, &nremoved);
141 if (nremoved != 1)
142 elog(ERROR, "failed to find relation %d in joinlist", innerrelid);
143
144 /*
145 * We can delete this SpecialJoinInfo from the list too, since it's no
146 * longer of interest. (Since we'll restart the foreach loop
147 * immediately, we don't bother with foreach_delete_current.)
148 */
149 root->join_info_list = list_delete_cell(root->join_info_list, lc);
150
151 /*
152 * Restart the scan. This is necessary to ensure we find all
153 * removable joins independently of ordering of the join_info_list
154 * (note that removal of attr_needed bits may make a join appear
155 * removable that did not before).
156 */
157 goto restart;
158 }
159
160 return joinlist;
161 }
162
163 /*
164 * join_is_removable
165 * Check whether we need not perform this special join at all, because
166 * it will just duplicate its left input.
167 *
168 * This is true for a left join for which the join condition cannot match
169 * more than one inner-side row. (There are other possibly interesting
170 * cases, but we don't have the infrastructure to prove them.) We also
171 * have to check that the inner side doesn't generate any variables needed
172 * above the join.
173 */
174 static bool
175 join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
176 {
177 int innerrelid;
178 RelOptInfo *innerrel;
179 Relids inputrelids;
180 Relids joinrelids;
181 List *clause_list = NIL;
182 ListCell *l;
183 int attroff;
184
185 /*
186 * Must be a left join to a single baserel, else we aren't going to be
187 * able to do anything with it.
188 */
189 if (sjinfo->jointype != JOIN_LEFT)
190 return false;
191
192 if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
193 return false;
194
195 /*
196 * Never try to eliminate a left join to the query result rel. Although
197 * the case is syntactically impossible in standard SQL, MERGE will build
198 * a join tree that looks exactly like that.
199 */
200 if (innerrelid == root->parse->resultRelation)
201 return false;
202
203 innerrel = find_base_rel(root, innerrelid);
204
205 /*
206 * Before we go to the effort of checking whether any innerrel variables
207 * are needed above the join, make a quick check to eliminate cases in
208 * which we will surely be unable to prove uniqueness of the innerrel.
209 */
210 if (!rel_supports_distinctness(root, innerrel))
211 return false;
212
213 /* Compute the relid set for the join we are considering */
214 inputrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
215 Assert(sjinfo->ojrelid != 0);
216 joinrelids = bms_copy(inputrelids);
217 joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid);
218
219 /*
220 * We can't remove the join if any inner-rel attributes are used above the
221 * join. Here, "above" the join includes pushed-down conditions, so we
222 * should reject if attr_needed includes the OJ's own relid; therefore,
223 * compare to inputrelids not joinrelids.
224 *
225 * As a micro-optimization, it seems better to start with max_attr and
226 * count down rather than starting with min_attr and counting up, on the
227 * theory that the system attributes are somewhat less likely to be wanted
228 * and should be tested last.
229 */
230 for (attroff = innerrel->max_attr - innerrel->min_attr;
231 attroff >= 0;
232 attroff--)
233 {
234 if (!bms_is_subset(innerrel->attr_needed[attroff], inputrelids))
235 return false;
236 }
237
238 /*
239 * Similarly check that the inner rel isn't needed by any PlaceHolderVars
240 * that will be used above the join. The PHV case is a little bit more
241 * complicated, because PHVs may have been assigned a ph_eval_at location
242 * that includes the innerrel, yet their contained expression might not
243 * actually reference the innerrel (it could be just a constant, for
244 * instance). If such a PHV is due to be evaluated above the join then it
245 * needn't prevent join removal.
246 */
247 foreach(l, root->placeholder_list)
248 {
249 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
250
251 if (bms_overlap(phinfo->ph_lateral, innerrel->relids))
252 return false; /* it references innerrel laterally */
253 if (!bms_overlap(phinfo->ph_eval_at, innerrel->relids))
254 continue; /* it definitely doesn't reference innerrel */
255 if (bms_is_subset(phinfo->ph_needed, inputrelids))
256 continue; /* PHV is not used above the join */
257 if (!bms_is_member(sjinfo->ojrelid, phinfo->ph_eval_at))
258 return false; /* it has to be evaluated below the join */
259
260 /*
261 * We need to be sure there will still be a place to evaluate the PHV
262 * if we remove the join, ie that ph_eval_at wouldn't become empty.
263 */
264 if (!bms_overlap(sjinfo->min_lefthand, phinfo->ph_eval_at))
265 return false; /* there isn't any other place to eval PHV */
266 /* Check contained expression last, since this is a bit expensive */
267 if (bms_overlap(pull_varnos(root, (Node *) phinfo->ph_var->phexpr),
268 innerrel->relids))
269 return false; /* contained expression references innerrel */
270 }
271
272 /*
273 * Search for mergejoinable clauses that constrain the inner rel against
274 * either the outer rel or a pseudoconstant. If an operator is
275 * mergejoinable then it behaves like equality for some btree opclass, so
276 * it's what we want. The mergejoinability test also eliminates clauses
277 * containing volatile functions, which we couldn't depend on.
278 */
279 foreach(l, innerrel->joininfo)
280 {
281 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
282
283 /*
284 * If the current join commutes with some other outer join(s) via
285 * outer join identity 3, there will be multiple clones of its join
286 * clauses in the joininfo list. We want to consider only the
287 * has_clone form of such clauses. Processing more than one form
288 * would be wasteful, and also some of the others would confuse the
289 * RINFO_IS_PUSHED_DOWN test below.
290 */
291 if (restrictinfo->is_clone)
292 continue; /* ignore it */
293
294 /*
295 * If it's not a join clause for this outer join, we can't use it.
296 * Note that if the clause is pushed-down, then it is logically from
297 * above the outer join, even if it references no other rels (it might
298 * be from WHERE, for example).
299 */
300 if (RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
301 continue; /* ignore; not useful here */
302
303 /* Ignore if it's not a mergejoinable clause */
304 if (!restrictinfo->can_join ||
305 restrictinfo->mergeopfamilies == NIL)
306 continue; /* not mergejoinable */
307
308 /*
309 * Check if the clause has the form "outer op inner" or "inner op
310 * outer", and if so mark which side is inner.
311 */
312 if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand,
313 innerrel->relids))
314 continue; /* no good for these input relations */
315
316 /* OK, add to list */
317 clause_list = lappend(clause_list, restrictinfo);
318 }
319
320 /*
321 * Now that we have the relevant equality join clauses, try to prove the
322 * innerrel distinct.
323 */
324 if (rel_is_distinct_for(root, innerrel, clause_list, NULL))
325 return true;
326
327 /*
328 * Some day it would be nice to check for other methods of establishing
329 * distinctness.
330 */
331 return false;
332 }
333
334
335 /*
336 * Remove the target rel->relid and references to the target join from the
337 * planner's data structures, having determined that there is no need
338 * to include them in the query. Optionally replace them with subst if subst
339 * is non-negative.
340 *
341 * This function updates only parts needed for both left-join removal and
342 * self-join removal.
343 */
344 static void
345 remove_rel_from_query(PlannerInfo *root, RelOptInfo *rel,
346 int subst, SpecialJoinInfo *sjinfo,
347 Relids joinrelids)
348 {
349 int relid = rel->relid;
350 Index rti;
351 ListCell *l;
352 Bitmapset *seen_serials = NULL;
353
354 /*
355 * Update all_baserels and related relid sets.
356 */
357 root->all_baserels = adjust_relid_set(root->all_baserels, relid, subst);
358 root->all_query_rels = adjust_relid_set(root->all_query_rels, relid, subst);
359
360 if (sjinfo != NULL)
361 {
362 root->outer_join_rels = bms_del_member(root->outer_join_rels,
363 sjinfo->ojrelid);
364 root->all_query_rels = bms_del_member(root->all_query_rels,
365 sjinfo->ojrelid);
366 }
367
368 /*
369 * Likewise remove references from SpecialJoinInfo data structures.
370 *
371 * This is relevant in case the outer join we're deleting is nested inside
372 * other outer joins: the upper joins' relid sets have to be adjusted. The
373 * RHS of the target outer join will be made empty here, but that's OK
374 * since caller will delete that SpecialJoinInfo entirely.
375 */
376 foreach(l, root->join_info_list)
377 {
378 SpecialJoinInfo *sjinf = (SpecialJoinInfo *) lfirst(l);
379
380 /*
381 * initsplan.c is fairly cavalier about allowing SpecialJoinInfos'
382 * lefthand/righthand relid sets to be shared with other data
383 * structures. Ensure that we don't modify the original relid sets.
384 * (The commute_xxx sets are always per-SpecialJoinInfo though.)
385 */
386 sjinf->min_lefthand = bms_copy(sjinf->min_lefthand);
387 sjinf->min_righthand = bms_copy(sjinf->min_righthand);
388 sjinf->syn_lefthand = bms_copy(sjinf->syn_lefthand);
389 sjinf->syn_righthand = bms_copy(sjinf->syn_righthand);
390 /* Now remove relid from the sets: */
391 sjinf->min_lefthand = adjust_relid_set(sjinf->min_lefthand, relid, subst);
392 sjinf->min_righthand = adjust_relid_set(sjinf->min_righthand, relid, subst);
393 sjinf->syn_lefthand = adjust_relid_set(sjinf->syn_lefthand, relid, subst);
394 sjinf->syn_righthand = adjust_relid_set(sjinf->syn_righthand, relid, subst);
395
396 if (sjinfo != NULL)
397 {
398 Assert(subst <= 0);
399
400 /* Remove sjinfo->ojrelid bits from the sets: */
401 sjinf->min_lefthand = bms_del_member(sjinf->min_lefthand,
402 sjinfo->ojrelid);
403 sjinf->min_righthand = bms_del_member(sjinf->min_righthand,
404 sjinfo->ojrelid);
405 sjinf->syn_lefthand = bms_del_member(sjinf->syn_lefthand,
406 sjinfo->ojrelid);
407 sjinf->syn_righthand = bms_del_member(sjinf->syn_righthand,
408 sjinfo->ojrelid);
409 /* relid cannot appear in these fields, but ojrelid can: */
410 sjinf->commute_above_l = bms_del_member(sjinf->commute_above_l,
411 sjinfo->ojrelid);
412 sjinf->commute_above_r = bms_del_member(sjinf->commute_above_r,
413 sjinfo->ojrelid);
414 sjinf->commute_below_l = bms_del_member(sjinf->commute_below_l,
415 sjinfo->ojrelid);
416 sjinf->commute_below_r = bms_del_member(sjinf->commute_below_r,
417 sjinfo->ojrelid);
418 }
419 else
420 {
421 Assert(subst > 0);
422
423 ChangeVarNodesExtended((Node *) sjinf->semi_rhs_exprs, relid, subst,
424 0, replace_relid_callback);
425 }
426 }
427
428 /*
429 * Likewise remove references from PlaceHolderVar data structures,
430 * removing any no-longer-needed placeholders entirely. We remove PHV
431 * only for left-join removal. With self-join elimination, PHVs already
432 * get moved to the remaining relation, where they might still be needed.
433 * It might also happen that we skip the removal of some PHVs that could
434 * be removed. However, the overhead of extra PHVs is small compared to
435 * the complexity of analysis needed to remove them.
436 *
437 * Removal is a bit trickier than it might seem: we can remove PHVs that
438 * are used at the target rel and/or in the join qual, but not those that
439 * are used at join partner rels or above the join. It's not that easy to
440 * distinguish PHVs used at partner rels from those used in the join qual,
441 * since they will both have ph_needed sets that are subsets of
442 * joinrelids. However, a PHV used at a partner rel could not have the
443 * target rel in ph_eval_at, so we check that while deciding whether to
444 * remove or just update the PHV. There is no corresponding test in
445 * join_is_removable because it doesn't need to distinguish those cases.
446 */
447 foreach(l, root->placeholder_list)
448 {
449 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
450
451 Assert(sjinfo == NULL || !bms_is_member(relid, phinfo->ph_lateral));
452 if (sjinfo != NULL &&
453 bms_is_subset(phinfo->ph_needed, joinrelids) &&
454 bms_is_member(relid, phinfo->ph_eval_at) &&
455 !bms_is_member(sjinfo->ojrelid, phinfo->ph_eval_at))
456 {
457 /*
458 * This code shouldn't be executed if one relation is substituted
459 * with another: in this case, the placeholder may be employed in
460 * a filter inside the scan node the SJE removes.
461 */
462 root->placeholder_list = foreach_delete_current(root->placeholder_list,
463 l);
464 root->placeholder_array[phinfo->phid] = NULL;
465 }
466 else
467 {
468 PlaceHolderVar *phv = phinfo->ph_var;
469
470 phinfo->ph_eval_at = adjust_relid_set(phinfo->ph_eval_at, relid, subst);
471 if (sjinfo != NULL)
472 phinfo->ph_eval_at = adjust_relid_set(phinfo->ph_eval_at,
473 sjinfo->ojrelid, subst);
474 Assert(!bms_is_empty(phinfo->ph_eval_at)); /* checked previously */
475 /* Reduce ph_needed to contain only "relation 0"; see below */
476 if (bms_is_member(0, phinfo->ph_needed))
477 phinfo->ph_needed = bms_make_singleton(0);
478 else
479 phinfo->ph_needed = NULL;
480
481 phinfo->ph_lateral = adjust_relid_set(phinfo->ph_lateral, relid, subst);
482
483 /*
484 * ph_lateral might contain rels mentioned in ph_eval_at after the
485 * replacement, remove them.
486 */
487 phinfo->ph_lateral = bms_difference(phinfo->ph_lateral, phinfo->ph_eval_at);
488 /* ph_lateral might or might not be empty */
489
490 phv->phrels = adjust_relid_set(phv->phrels, relid, subst);
491 if (sjinfo != NULL)
492 phv->phrels = adjust_relid_set(phv->phrels,
493 sjinfo->ojrelid, subst);
494 Assert(!bms_is_empty(phv->phrels));
495
496 ChangeVarNodesExtended((Node *) phv->phexpr, relid, subst, 0,
497 replace_relid_callback);
498
499 Assert(phv->phnullingrels == NULL); /* no need to adjust */
500 }
501 }
502
503 /*
504 * Likewise remove references from EquivalenceClasses.
505 */
506 foreach(l, root->eq_classes)
507 {
508 EquivalenceClass *ec = (EquivalenceClass *) lfirst(l);
509
510 remove_rel_from_eclass(root, ec, sjinfo, relid, subst);
511 }
512
513 /*
514 * Finally, we must recompute per-Var attr_needed and per-PlaceHolderVar
515 * ph_needed relid sets. These have to be known accurately, else we may
516 * fail to remove other now-removable outer joins. And our removal of the
517 * join clause(s) for this outer join may mean that Vars that were
518 * formerly needed no longer are. So we have to do this honestly by
519 * repeating the construction of those relid sets. We can cheat to one
520 * small extent: we can avoid re-examining the targetlist and HAVING qual
521 * by preserving "relation 0" bits from the existing relid sets. This is
522 * safe because we'd never remove such references.
523 *
524 * So, start by removing all other bits from attr_needed sets and
525 * lateral_vars lists. (We already did this above for ph_needed.)
526 *
527 * Also, for left-join removal, we strip the removed rel and join from any
528 * PlaceHolderVar embedded in the surviving rels' restriction clauses and
529 * join clauses; we needn't bother with the rel being removed, nor when
530 * the query has no PlaceHolderVars.
531 */
532 for (rti = 1; rti < root->simple_rel_array_size; rti++)
533 {
534 RelOptInfo *otherrel = root->simple_rel_array[rti];
535 int attroff;
536
537 /* there may be empty slots corresponding to non-baserel RTEs */
538 if (otherrel == NULL)
539 continue;
540
541 Assert(otherrel->relid == rti); /* sanity check on array */
542
543 for (attroff = otherrel->max_attr - otherrel->min_attr;
544 attroff >= 0;
545 attroff--)
546 {
547 if (bms_is_member(0, otherrel->attr_needed[attroff]))
548 otherrel->attr_needed[attroff] = bms_make_singleton(0);
549 else
550 otherrel->attr_needed[attroff] = NULL;
551 }
552
553 if (subst > 0)
554 ChangeVarNodesExtended((Node *) otherrel->lateral_vars, relid,
555 subst, 0, replace_relid_callback);
556
557 if (sjinfo != NULL && rti != relid && root->glob->lastPHId != 0)
558 {
559 foreach_node(RestrictInfo, rinfo, otherrel->baserestrictinfo)
560 remove_rel_from_restrictinfo_phvs(rinfo, relid, sjinfo->ojrelid);
561
562 /*
563 * Join clauses need the same treatment, but there's no value in
564 * processing any join clause more than once. So it's slightly
565 * annoying that we have to find them via the per-base-relation
566 * joininfo lists. Avoid duplicate processing by tracking the
567 * rinfo_serial numbers of join clauses we've already seen. (This
568 * doesn't work for is_clone clauses, so we must waste effort on
569 * them.)
570 */
571 foreach_node(RestrictInfo, rinfo, otherrel->joininfo)
572 {
573 if (!rinfo->is_clone) /* else serial number is not unique */
574 {
575 if (bms_is_member(rinfo->rinfo_serial, seen_serials))
576 continue; /* saw it already */
577 seen_serials = bms_add_member(seen_serials,
578 rinfo->rinfo_serial);
579 }
580 remove_rel_from_restrictinfo_phvs(rinfo, relid, sjinfo->ojrelid);
581 }
582 }
583 }
584 }
585
586 /*
587 * Remove the target relid and references to the target join from the
588 * planner's data structures, having determined that there is no need
589 * to include them in the query.
590 *
591 * We are not terribly thorough here. We only bother to update parts of
592 * the planner's data structures that will actually be consulted later.
593 */
594 static void
595 remove_leftjoinrel_from_query(PlannerInfo *root, int relid,
596 SpecialJoinInfo *sjinfo)
597 {
598 RelOptInfo *rel = find_base_rel(root, relid);
599 int ojrelid = sjinfo->ojrelid;
600 Relids joinrelids;
601 Relids join_plus_commute;
602 List *joininfos;
603 ListCell *l;
604
605 /* Compute the relid set for the join we are considering */
606 joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
607 Assert(ojrelid != 0);
608 joinrelids = bms_add_member(joinrelids, ojrelid);
609
610 remove_rel_from_query(root, rel, -1, sjinfo, joinrelids);
611
612 /*
613 * Remove any joinquals referencing the rel from the joininfo lists.
614 *
615 * In some cases, a joinqual has to be put back after deleting its
616 * reference to the target rel. This can occur for pseudoconstant and
617 * outerjoin-delayed quals, which can get marked as requiring the rel in
618 * order to force them to be evaluated at or above the join. We can't
619 * just discard them, though. Only quals that logically belonged to the
620 * outer join being discarded should be removed from the query.
621 *
622 * We might encounter a qual that is a clone of a deletable qual with some
623 * outer-join relids added (see deconstruct_distribute_oj_quals). To
624 * ensure we get rid of such clones as well, add the relids of all OJs
625 * commutable with this one to the set we test against for
626 * pushed-down-ness.
627 */
628 join_plus_commute = bms_union(joinrelids,
629 sjinfo->commute_above_r);
630 join_plus_commute = bms_add_members(join_plus_commute,
631 sjinfo->commute_below_l);
632
633 /*
634 * We must make a copy of the rel's old joininfo list before starting the
635 * loop, because otherwise remove_join_clause_from_rels would destroy the
636 * list while we're scanning it.
637 */
638 joininfos = list_copy(rel->joininfo);
639 foreach(l, joininfos)
640 {
641 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
642
643 remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);
644
645 if (RINFO_IS_PUSHED_DOWN(rinfo, join_plus_commute))
646 {
647 /*
648 * There might be references to relid or ojrelid in the
649 * RestrictInfo's relid sets, as a consequence of PHVs having had
650 * ph_eval_at sets that include those. We already checked above
651 * that any such PHV is safe (and updated its ph_eval_at), so we
652 * can just drop those references.
653 */
654 remove_rel_from_restrictinfo(rinfo, relid, ojrelid);
655
656 /*
657 * Cross-check that the clause itself does not reference the
658 * target rel or join.
659 */
660 #ifdef USE_ASSERT_CHECKING
661 {
662 Relids clause_varnos = pull_varnos(root,
663 (Node *) rinfo->clause);
664
665 Assert(!bms_is_member(relid, clause_varnos));
666 Assert(!bms_is_member(ojrelid, clause_varnos));
667 }
668 #endif
669 /* Now throw it back into the joininfo lists */
670 distribute_restrictinfo_to_rels(root, rinfo);
671 }
672 }
673
674 /*
675 * There may be references to the rel in root->fkey_list, but if so,
676 * match_foreign_keys_to_quals() will get rid of them.
677 */
678
679 /*
680 * Now remove the rel from the baserel array to prevent it from being
681 * referenced again. (We can't do this earlier because
682 * remove_join_clause_from_rels will touch it.)
683 */
684 root->simple_rel_array[relid] = NULL;
685 root->simple_rte_array[relid] = NULL;
686
687 /* And nuke the RelOptInfo, just in case there's another access path */
688 pfree(rel);
689
690 /*
691 * Now repeat construction of attr_needed bits coming from all other
692 * sources.
693 */
694 rebuild_placeholder_attr_needed(root);
695 rebuild_joinclause_attr_needed(root);
696 rebuild_eclass_attr_needed(root);
697 rebuild_lateral_attr_needed(root);
698 }
699
700 /*
701 * Remove any references to relid or ojrelid from the RestrictInfo.
702 *
703 * We only bother to clean out bits in the RestrictInfo's various relid sets,
704 * not nullingrel bits in contained Vars and PHVs. (This might have to be
705 * improved sometime.) However, if the RestrictInfo contains an OR clause
706 * we have to also clean up the sub-clauses.
707 */
708 static void
709 remove_rel_from_restrictinfo(RestrictInfo *rinfo, int relid, int ojrelid)
710 {
711 /*
712 * initsplan.c is fairly cavalier about allowing RestrictInfos to share
713 * relid sets with other RestrictInfos, and SpecialJoinInfos too. Make
714 * sure this RestrictInfo has its own relid sets before we modify them.
715 * (In present usage, clause_relids is probably not shared, but
716 * required_relids could be; let's not assume anything.)
717 */
718 rinfo->clause_relids = bms_copy(rinfo->clause_relids);
719 rinfo->clause_relids = bms_del_member(rinfo->clause_relids, relid);
720 rinfo->clause_relids = bms_del_member(rinfo->clause_relids, ojrelid);
721 /* Likewise for required_relids */
722 rinfo->required_relids = bms_copy(rinfo->required_relids);
723 rinfo->required_relids = bms_del_member(rinfo->required_relids, relid);
724 rinfo->required_relids = bms_del_member(rinfo->required_relids, ojrelid);
725 /* Likewise for incompatible_relids */
726 rinfo->incompatible_relids = bms_copy(rinfo->incompatible_relids);
727 rinfo->incompatible_relids = bms_del_member(rinfo->incompatible_relids, relid);
728 rinfo->incompatible_relids = bms_del_member(rinfo->incompatible_relids, ojrelid);
729 /* Likewise for outer_relids */
730 rinfo->outer_relids = bms_copy(rinfo->outer_relids);
731 rinfo->outer_relids = bms_del_member(rinfo->outer_relids, relid);
732 rinfo->outer_relids = bms_del_member(rinfo->outer_relids, ojrelid);
733 /* Likewise for left_relids */
734 rinfo->left_relids = bms_copy(rinfo->left_relids);
735 rinfo->left_relids = bms_del_member(rinfo->left_relids, relid);
736 rinfo->left_relids = bms_del_member(rinfo->left_relids, ojrelid);
737 /* Likewise for right_relids */
738 rinfo->right_relids = bms_copy(rinfo->right_relids);
739 rinfo->right_relids = bms_del_member(rinfo->right_relids, relid);
740 rinfo->right_relids = bms_del_member(rinfo->right_relids, ojrelid);
741
742 /* If it's an OR, recurse to clean up sub-clauses */
743 if (restriction_is_or_clause(rinfo))
744 {
745 ListCell *lc;
746
747 Assert(is_orclause(rinfo->orclause));
748 foreach(lc, ((BoolExpr *) rinfo->orclause)->args)
749 {
750 Node *orarg = (Node *) lfirst(lc);
751
752 /* OR arguments should be ANDs or sub-RestrictInfos */
753 if (is_andclause(orarg))
754 {
755 List *andargs = ((BoolExpr *) orarg)->args;
756 ListCell *lc2;
757
758 foreach(lc2, andargs)
759 {
760 RestrictInfo *rinfo2 = lfirst_node(RestrictInfo, lc2);
761
762 remove_rel_from_restrictinfo(rinfo2, relid, ojrelid);
763 }
764 }
765 else
766 {
767 RestrictInfo *rinfo2 = castNode(RestrictInfo, orarg);
768
769 remove_rel_from_restrictinfo(rinfo2, relid, ojrelid);
770 }
771 }
772 }
773 }
774
775 /*
776 * Remove any references to relid or sjinfo->ojrelid (if sjinfo != NULL)
777 * from the EquivalenceClass.
778 *
779 * We fix the EC and EM relid sets to ensure that implied join equalities will
780 * be generated at the appropriate join level(s). We also strip the removed
781 * rel from PlaceHolderVars embedded in member expressions; a member's
782 * em_relids reflects ph_eval_at rather than the PHV's phrels, so the latter
783 * can still mention the removed rel even when em_relids does not. Like
784 * remove_rel_from_restrictinfo, we don't bother with nullingrel bits in
785 * contained plain Vars.
786 */
787 static void
788 remove_rel_from_eclass(PlannerInfo *root, EquivalenceClass *ec,
789 SpecialJoinInfo *sjinfo,
790 int relid, int subst)
791 {
792 ListCell *lc;
793
794 /*
795 * Strip the removed rel/join from PlaceHolderVars in member expressions.
796 * This is needed even when the EC's relids don't mention the removed rel.
797 * Plain Vars and Consts can't contain a PlaceHolderVar, so skip them.
798 */
799 if (sjinfo != NULL && root->glob->lastPHId != 0)
800 {
801 foreach_node(EquivalenceMember, em, ec->ec_members)
802 {
803 if (!IsA(em->em_expr, Var) && !IsA(em->em_expr, Const))
804 em->em_expr = (Expr *)
805 remove_rel_from_phvs((Node *) em->em_expr, relid,
806 sjinfo->ojrelid);
807 }
808 }
809
810 if (!bms_is_member(relid, ec->ec_relids) &&
811 (sjinfo == NULL || !bms_is_member(sjinfo->ojrelid, ec->ec_relids)))
812 return;
813
814 /* Fix up the EC's overall relids */
815 ec->ec_relids = adjust_relid_set(ec->ec_relids, relid, subst);
816 if (sjinfo != NULL)
817 ec->ec_relids = adjust_relid_set(ec->ec_relids,
818 sjinfo->ojrelid, subst);
819
820 /*
821 * We don't expect any EC child members to exist at this point. Ensure
822 * that's the case, otherwise, we might be getting asked to do something
823 * this function hasn't been coded for.
824 */
825 Assert(ec->ec_childmembers == NULL);
826
827 /*
828 * Fix up the member expressions. Any non-const member that ends with
829 * empty em_relids must be a Var or PHV of the removed relation. We don't
830 * need it anymore, so we can drop it.
831 */
832 foreach(lc, ec->ec_members)
833 {
834 EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
835
836 if (bms_is_member(relid, cur_em->em_relids) ||
837 (sjinfo != NULL && bms_is_member(sjinfo->ojrelid,
838 cur_em->em_relids)))
839 {
840 Assert(!cur_em->em_is_const);
841 cur_em->em_relids = adjust_relid_set(cur_em->em_relids, relid, subst);
842 if (sjinfo != NULL)
843 cur_em->em_relids = adjust_relid_set(cur_em->em_relids,
844 sjinfo->ojrelid, subst);
845 if (bms_is_empty(cur_em->em_relids))
846 ec->ec_members = foreach_delete_current(ec->ec_members, lc);
847 }
848 }
849
850 /* Fix up the source clauses, in case we can re-use them later */
851 foreach(lc, ec->ec_sources)
852 {
853 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
854
855 if (sjinfo == NULL)
856 ChangeVarNodesExtended((Node *) rinfo, relid, subst, 0,
857 replace_relid_callback);
858 else
859 remove_rel_from_restrictinfo(rinfo, relid, sjinfo->ojrelid);
860 }
861
862 /*
863 * Rather than expend code on fixing up any already-derived clauses, just
864 * drop them. (At this point, any such clauses would be base restriction
865 * clauses, which we'd not need anymore anyway.)
866 */
867 ec_clear_derived_clauses(ec);
868 }
869
870 /*
871 * Remove any references to relid or ojrelid from the PlaceHolderVars embedded
872 * in a RestrictInfo's clause.
873 *
874 * If it's an OR clause, we must also fix up the orclause, which is a parallel
875 * representation built from its own sub-RestrictInfos. We recurse into the
876 * sub-clauses for that, mirroring remove_rel_from_restrictinfo.
877 */
878 static void
879 remove_rel_from_restrictinfo_phvs(RestrictInfo *rinfo, int relid, int ojrelid)
880 {
881 rinfo->clause = (Expr *)
882 remove_rel_from_phvs((Node *) rinfo->clause, relid, ojrelid);
883
884 /* If it's an OR, recurse to clean up sub-clauses */
885 if (restriction_is_or_clause(rinfo))
886 {
887 ListCell *lc;
888
889 Assert(is_orclause(rinfo->orclause));
890 foreach(lc, ((BoolExpr *) rinfo->orclause)->args)
891 {
892 Node *orarg = (Node *) lfirst(lc);
893
894 /* OR arguments should be ANDs or sub-RestrictInfos */
895 if (is_andclause(orarg))
896 {
897 List *andargs = ((BoolExpr *) orarg)->args;
898 ListCell *lc2;
899
900 foreach(lc2, andargs)
901 {
902 RestrictInfo *rinfo2 = lfirst_node(RestrictInfo, lc2);
903
904 remove_rel_from_restrictinfo_phvs(rinfo2, relid, ojrelid);
905 }
906 }
907 else
908 {
909 RestrictInfo *rinfo2 = castNode(RestrictInfo, orarg);
910
911 remove_rel_from_restrictinfo_phvs(rinfo2, relid, ojrelid);
912 }
913 }
914 }
915 }
916
917 /*
918 * Remove any references to the specified RT index(es) from the phrels (and
919 * phnullingrels) of every PlaceHolderVar in the given expression.
920 *
921 * remove_rel_from_query() fixes up the relid sets of RestrictInfos and
922 * EquivalenceMembers, but not the PlaceHolderVars embedded in their
923 * expressions. That's normally fine, but such an expression may later be
924 * translated for an appendrel child and have its relids recomputed by
925 * pull_varnos(). A leftover removed relid in phrels would then make
926 * pull_varnos() reference a nonexistent rel, so we strip it here to match the
927 * canonical PlaceHolderVar.
928 */
929 static Node *
930 remove_rel_from_phvs(Node *node, int relid, int ojrelid)
931 {
932 Relids removable = bms_add_member(bms_make_singleton(relid), ojrelid);
933
934 return remove_rel_from_phvs_mutator(node, removable);
935 }
936
937 static Node *
938 remove_rel_from_phvs_mutator(Node *node, Relids removable)
939 {
940 if (node == NULL)
941 return NULL;
942 if (IsA(node, PlaceHolderVar))
943 {
944 PlaceHolderVar *phv = (PlaceHolderVar *) node;
945 Relids newphrels;
946
947 /* Upper-level PlaceHolderVars should be long gone at this point */
948 Assert(phv->phlevelsup == 0);
949
950 /* Copy the PlaceHolderVar and mutate what's below ... */
951 phv = (PlaceHolderVar *)
952 expression_tree_mutator(node,
953 remove_rel_from_phvs_mutator,
954 removable);
955
956 /*
957 * ... then strip the removed rels from its relid sets.
958 *
959 * If stripping would empty phrels, the PHV is evaluated only at the
960 * removed relation(s); it then belongs to an EquivalenceMember that
961 * the caller drops immediately afterwards. Leave such a PHV
962 * untouched rather than build one with empty phrels, which the rest
963 * of the planner assumes never occurs.
964 */
965 newphrels = bms_difference(phv->phrels, removable);
966 if (!bms_is_empty(newphrels))
967 {
968 phv->phrels = newphrels;
969 phv->phnullingrels = bms_difference(phv->phnullingrels,
970 removable);
971 }
972
973 return (Node *) phv;
974 }
975 return expression_tree_mutator(node,
976 remove_rel_from_phvs_mutator,
977 removable);
978 }
979
980 /*
981 * Remove any occurrences of the target relid from a joinlist structure.
982 *
983 * It's easiest to build a whole new list structure, so we handle it that
984 * way. Efficiency is not a big deal here.
985 *
986 * *nremoved is incremented by the number of occurrences removed (there
987 * should be exactly one, but the caller checks that).
988 */
989 static List *
990 remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
991 {
992 List *result = NIL;
993 ListCell *jl;
994
995 foreach(jl, joinlist)
996 {
997 Node *jlnode = (Node *) lfirst(jl);
998
999 if (IsA(jlnode, RangeTblRef))
1000 {
1001 int varno = ((RangeTblRef *) jlnode)->rtindex;
1002
1003 if (varno == relid)
1004 (*nremoved)++;
1005 else
1006 result = lappend(result, jlnode);
1007 }
1008 else if (IsA(jlnode, List))
1009 {
1010 /* Recurse to handle subproblem */
1011 List *sublist;
1012
1013 sublist = remove_rel_from_joinlist((List *) jlnode,
1014 relid, nremoved);
1015 /* Avoid including empty sub-lists in the result */
1016 if (sublist)
1017 result = lappend(result, sublist);
1018 }
1019 else
1020 {
1021 elog(ERROR, "unrecognized joinlist node type: %d",
1022 (int) nodeTag(jlnode));
1023 }
1024 }
1025
1026 return result;
1027 }
1028
1029
1030 /*
1031 * reduce_unique_semijoins
1032 * Check for semijoins that can be simplified to plain inner joins
1033 * because the inner relation is provably unique for the join clauses.
1034 *
1035 * Ideally this would happen during reduce_outer_joins, but we don't have
1036 * enough information at that point.
1037 *
1038 * To perform the strength reduction when applicable, we need only delete
1039 * the semijoin's SpecialJoinInfo from root->join_info_list. (We don't
1040 * bother fixing the join type attributed to it in the query jointree,
1041 * since that won't be consulted again.)
1042 */
1043 void
1044 reduce_unique_semijoins(PlannerInfo *root)
1045 {
1046 ListCell *lc;
1047
1048 /*
1049 * Scan the join_info_list to find semijoins.
1050 */
1051 foreach(lc, root->join_info_list)
1052 {
1053 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
1054 int innerrelid;
1055 RelOptInfo *innerrel;
1056 Relids joinrelids;
1057 List *restrictlist;
1058
1059 /*
1060 * Must be a semijoin to a single baserel, else we aren't going to be
1061 * able to do anything with it.
1062 */
1063 if (sjinfo->jointype != JOIN_SEMI)
1064 continue;
1065
1066 if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
1067 continue;
1068
1069 innerrel = find_base_rel(root, innerrelid);
1070
1071 /*
1072 * Before we trouble to run generate_join_implied_equalities, make a
1073 * quick check to eliminate cases in which we will surely be unable to
1074 * prove uniqueness of the innerrel.
1075 */
1076 if (!rel_supports_distinctness(root, innerrel))
1077 continue;
1078
1079 /* Compute the relid set for the join we are considering */
1080 joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
1081 Assert(sjinfo->ojrelid == 0); /* SEMI joins don't have RT indexes */
1082
1083 /*
1084 * Since we're only considering a single-rel RHS, any join clauses it
1085 * has must be clauses linking it to the semijoin's min_lefthand. We
1086 * can also consider EC-derived join clauses.
1087 */
1088 restrictlist =
1089 list_concat(generate_join_implied_equalities(root,
1090 joinrelids,
1091 sjinfo->min_lefthand,
1092 innerrel,
1093 NULL),
1094 innerrel->joininfo);
1095
1096 /* Test whether the innerrel is unique for those clauses. */
1097 if (!innerrel_is_unique(root,
1098 joinrelids, sjinfo->min_lefthand, innerrel,
1099 JOIN_SEMI, restrictlist, true))
1100 continue;
1101
1102 /* OK, remove the SpecialJoinInfo from the list. */
1103 root->join_info_list = foreach_delete_current(root->join_info_list, lc);
1104 }
1105 }
1106
1107
1108 /*
1109 * rel_supports_distinctness
1110 * Could the relation possibly be proven distinct on some set of columns?
1111 *
1112 * This is effectively a pre-checking function for rel_is_distinct_for().
1113 * It must return true if rel_is_distinct_for() could possibly return true
1114 * with this rel, but it should not expend a lot of cycles. The idea is
1115 * that callers can avoid doing possibly-expensive processing to compute
1116 * rel_is_distinct_for()'s argument lists if the call could not possibly
1117 * succeed.
1118 */
1119 static bool
1120 rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
1121 {
1122 /* We only know about baserels ... */
1123 if (rel->reloptkind != RELOPT_BASEREL)
1124 return false;
1125 if (rel->rtekind == RTE_RELATION)
1126 {
1127 /*
1128 * For a plain relation, we only know how to prove uniqueness by
1129 * reference to unique indexes. Make sure there's at least one
1130 * suitable unique index. It must be immediately enforced, and not a
1131 * partial index. (Keep these conditions in sync with
1132 * relation_has_unique_index_for!)
1133 */
1134 ListCell *lc;
1135
1136 foreach(lc, rel->indexlist)
1137 {
1138 IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);
1139
1140 if (ind->unique && ind->immediate && ind->indpred == NIL)
1141 return true;
1142 }
1143 }
1144 else if (rel->rtekind == RTE_SUBQUERY)
1145 {
1146 Query *subquery = root->simple_rte_array[rel->relid]->subquery;
1147
1148 /* Check if the subquery has any qualities that support distinctness */
1149 if (query_supports_distinctness(subquery))
1150 return true;
1151 }
1152 /* We have no proof rules for any other rtekinds. */
1153 return false;
1154 }
1155
1156 /*
1157 * rel_is_distinct_for
1158 * Does the relation return only distinct rows according to clause_list?
1159 *
1160 * clause_list is a list of join restriction clauses involving this rel and
1161 * some other one. Return true if no two rows emitted by this rel could
1162 * possibly join to the same row of the other rel.
1163 *
1164 * The caller must have already determined that each condition is a
1165 * mergejoinable equality with an expression in this relation on one side, and
1166 * an expression not involving this relation on the other. The transient
1167 * outer_is_left flag is used to identify which side references this relation:
1168 * left side if outer_is_left is false, right side if it is true.
1169 *
1170 * Note that the passed-in clause_list may be destructively modified! This
1171 * is OK for current uses, because the clause_list is built by the caller for
1172 * the sole purpose of passing to this function.
1173 *
1174 * (*extra_clauses) to be set to the right sides of baserestrictinfo clauses,
1175 * looking like "x = const" if distinctness is derived from such clauses, not
1176 * joininfo clauses. Pass NULL to the extra_clauses if this value is not
1177 * needed.
1178 */
1179 static bool
1180 rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list,
1181 List **extra_clauses)
1182 {
1183 /*
1184 * We could skip a couple of tests here if we assume all callers checked
1185 * rel_supports_distinctness first, but it doesn't seem worth taking any
1186 * risk for.
1187 */
1188 if (rel->reloptkind != RELOPT_BASEREL)
1189 return false;
1190 if (rel->rtekind == RTE_RELATION)
1191 {
1192 /*
1193 * Examine the indexes to see if we have a matching unique index.
1194 * relation_has_unique_index_ext automatically adds any usable
1195 * restriction clauses for the rel, so we needn't do that here.
1196 */
1197 if (relation_has_unique_index_ext(root, rel, clause_list, NIL, NIL,
1198 extra_clauses))
1199 return true;
1200 }
1201 else if (rel->rtekind == RTE_SUBQUERY)
1202 {
1203 Index relid = rel->relid;
1204 Query *subquery = root->simple_rte_array[relid]->subquery;
1205 List *distinct_cols = NIL;
1206 ListCell *l;
1207
1208 /*
1209 * Build the argument list for query_is_distinct_for_with_collations:
1210 * a list of DistinctColInfo entries, each holding an output column
1211 * number that the query needs to be distinct over, the equality
1212 * operator that the column needs to be distinct according to, and
1213 * that operator's input collation. The collation matters because the
1214 * subquery's own DISTINCT / GROUP BY / set-op proves uniqueness under
1215 * its own collation, which need not agree with the operator's.
1216 *
1217 * (XXX we are not considering restriction clauses attached to the
1218 * subquery; is that worth doing?)
1219 */
1220 foreach(l, clause_list)
1221 {
1222 RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
1223 OpExpr *opexpr;
1224 Var *var;
1225 DistinctColInfo *dcinfo;
1226
1227 /*
1228 * The caller's mergejoinability test should have selected only
1229 * OpExprs. The operator might be a cross-type operator and thus
1230 * not exactly the same operator the subquery would consider;
1231 * that's all right since query_is_distinct_for_with_collations
1232 * can resolve such cases.
1233 */
1234 opexpr = castNode(OpExpr, rinfo->clause);
1235
1236 /* caller identified the inner side for us */
1237 if (rinfo->outer_is_left)
1238 var = (Var *) get_rightop(rinfo->clause);
1239 else
1240 var = (Var *) get_leftop(rinfo->clause);
1241
1242 /*
1243 * We may ignore any RelabelType node above the operand. (There
1244 * won't be more than one, since eval_const_expressions() has been
1245 * applied already.)
1246 */
1247 if (var && IsA(var, RelabelType))
1248 var = (Var *) ((RelabelType *) var)->arg;
1249
1250 /*
1251 * If inner side isn't a Var referencing a subquery output column,
1252 * this clause doesn't help us.
1253 */
1254 if (!var || !IsA(var, Var) ||
1255 var->varno != relid || var->varlevelsup != 0)
1256 continue;
1257
1258 dcinfo = palloc(sizeof(DistinctColInfo));
1259 dcinfo->colno = var->varattno;
1260 dcinfo->opid = opexpr->opno;
1261 dcinfo->collid = opexpr->inputcollid;
1262 distinct_cols = lappend(distinct_cols, dcinfo);
1263 }
1264
1265 if (query_is_distinct_for_with_collations(subquery, distinct_cols))
1266 return true;
1267 }
1268 return false;
1269 }
1270
1271
1272 /*
1273 * query_supports_distinctness - could the query possibly be proven distinct
1274 * on some set of output columns?
1275 *
1276 * This is effectively a pre-checking function for query_is_distinct_for().
1277 * It must return true if query_is_distinct_for() could possibly return true
1278 * with this query, but it should not expend a lot of cycles. The idea is
1279 * that callers can avoid doing possibly-expensive processing to compute
1280 * query_is_distinct_for()'s argument lists if the call could not possibly
1281 * succeed.
1282 */
1283 bool
1284 query_supports_distinctness(Query *query)
1285 {
1286 /* SRFs break distinctness except with DISTINCT, see below */
1287 if (query->hasTargetSRFs && query->distinctClause == NIL)
1288 return false;
1289
1290 /* check for features we can prove distinctness with */
1291 if (query->distinctClause != NIL ||
1292 query->groupClause != NIL ||
1293 query->groupingSets != NIL ||
1294 query->hasAggs ||
1295 query->havingQual ||
1296 query->setOperations)
1297 return true;
1298
1299 return false;
1300 }
1301
1302 /*
1303 * query_is_distinct_for - ABI-preserving wrapper around
1304 * query_is_distinct_for_with_collations().
1305 *
1306 * The original signature took parallel colnos/opids lists and did not
1307 * consider collations. External callers built against earlier minor
1308 * releases continue to call it with the historical (collation-blind)
1309 * semantics; we forward with InvalidOid collations, which makes the
1310 * collation check a no-op (see collations_agree_on_equality()).
1311 */
1312 bool
1313 query_is_distinct_for(Query *query, List *colnos, List *opids)
1314 {
1315 List *distinct_cols = NIL;
1316 ListCell *lc1;
1317 ListCell *lc2;
1318
1319 Assert(list_length(colnos) == list_length(opids));
1320
1321 forboth(lc1, colnos, lc2, opids)
1322 {
1323 DistinctColInfo *dcinfo = palloc(sizeof(DistinctColInfo));
1324
1325 dcinfo->colno = lfirst_int(lc1);
1326 dcinfo->opid = lfirst_oid(lc2);
1327 dcinfo->collid = InvalidOid;
1328 distinct_cols = lappend(distinct_cols, dcinfo);
1329 }
1330
1331 return query_is_distinct_for_with_collations(query, distinct_cols);
1332 }
1333
1334 /*
1335 * query_is_distinct_for_with_collations - does query never return duplicates
1336 * of the specified columns?
1337 *
1338 * query is a not-yet-planned subquery (in current usage, it's always from
1339 * a subquery RTE, which the planner avoids scribbling on).
1340 *
1341 * distinct_cols is a list of DistinctColInfo, one per requested output column.
1342 * Each entry names the subquery output column number we want distinct, the
1343 * upper-level equality operator we'll compare values with, and that operator's
1344 * input collation. We are interested in whether rows consisting of just these
1345 * columns are certain to be distinct.
1346 *
1347 * "Distinctness" is defined according to whether the corresponding upper-level
1348 * equality operators would think the values are distinct. (Note: each opid
1349 * could be a cross-type operator, and thus not exactly the equality operator
1350 * that the subquery would use itself. We use equality_ops_are_compatible() to
1351 * check compatibility. That looks at opfamily membership for index AMs that
1352 * have declared that they support consistent equality semantics within an
1353 * opfamily, and so should give trustworthy answers for all operators that we
1354 * might need to deal with here.)
1355 *
1356 * The collid must also agree on equality with the collation the subquery's own
1357 * DISTINCT/GROUP BY/set-op uses to deduplicate the column, else the subquery's
1358 * distinctness does not carry over to the caller's equality semantics. Two
1359 * collations agree on equality if they match or if both are deterministic (in
1360 * which case both reduce equality to byte-equality; see CREATE COLLATION).
1361 */
1362 static bool
1363 query_is_distinct_for_with_collations(Query *query, List *distinct_cols)
1364 {
1365 ListCell *l;
1366 DistinctColInfo *dcinfo;
1367
1368 /*
1369 * DISTINCT (including DISTINCT ON) guarantees uniqueness if all the
1370 * columns in the DISTINCT clause appear in colnos and operator semantics
1371 * match. This is true even if there are SRFs in the DISTINCT columns or
1372 * elsewhere in the tlist.
1373 */
1374 if (query->distinctClause)
1375 {
1376 foreach(l, query->distinctClause)
1377 {
1378 SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
1379 TargetEntry *tle = get_sortgroupclause_tle(sgc,
1380 query->targetList);
1381
1382 dcinfo = distinct_col_search(tle->resno, distinct_cols);
1383 if (dcinfo == NULL ||
1384 !equality_ops_are_compatible(dcinfo->opid, sgc->eqop) ||
1385 !collations_agree_on_equality(dcinfo->collid,
1386 exprCollation((Node *) tle->expr)))
1387 break; /* exit early if no match */
1388 }
1389 if (l == NULL) /* had matches for all? */
1390 return true;
1391 }
1392
1393 /*
1394 * Otherwise, a set-returning function in the query's targetlist can
1395 * result in returning duplicate rows, despite any grouping that might
1396 * occur before tlist evaluation. (If all tlist SRFs are within GROUP BY
1397 * columns, it would be safe because they'd be expanded before grouping.
1398 * But it doesn't currently seem worth the effort to check for that.)
1399 */
1400 if (query->hasTargetSRFs)
1401 return false;
1402
1403 /*
1404 * Similarly, GROUP BY without GROUPING SETS guarantees uniqueness if all
1405 * the grouped columns appear in colnos and operator semantics match.
1406 */
1407 if (query->groupClause && !query->groupingSets)
1408 {
1409 foreach(l, query->groupClause)
1410 {
1411 SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
1412 TargetEntry *tle = get_sortgroupclause_tle(sgc,
1413 query->targetList);
1414
1415 dcinfo = distinct_col_search(tle->resno, distinct_cols);
1416 if (dcinfo == NULL ||
1417 !equality_ops_are_compatible(dcinfo->opid, sgc->eqop) ||
1418 !collations_agree_on_equality(dcinfo->collid,
1419 exprCollation((Node *) tle->expr)))
1420 break; /* exit early if no match */
1421 }
1422 if (l == NULL) /* had matches for all? */
1423 return true;
1424 }
1425 else if (query->groupingSets)
1426 {
1427 /*
1428 * If we have grouping sets with expressions, we probably don't have
1429 * uniqueness and analysis would be hard. Punt.
1430 */
1431 if (query->groupClause)
1432 return false;
1433
1434 /*
1435 * If we have no groupClause (therefore no grouping expressions), we
1436 * might have one or many empty grouping sets. If there's just one,
1437 * then we're returning only one row and are certainly unique. But
1438 * otherwise, we know we're certainly not unique.
1439 */
1440 if (list_length(query->groupingSets) == 1 &&
1441 ((GroupingSet *) linitial(query->groupingSets))->kind == GROUPING_SET_EMPTY)
1442 return true;
1443 else
1444 return false;
1445 }
1446 else
1447 {
1448 /*
1449 * If we have no GROUP BY, but do have aggregates or HAVING, then the
1450 * result is at most one row so it's surely unique, for any operators.
1451 */
1452 if (query->hasAggs || query->havingQual)
1453 return true;
1454 }
1455
1456 /*
1457 * UNION, INTERSECT, EXCEPT guarantee uniqueness of the whole output row,
1458 * except with ALL.
1459 */
1460 if (query->setOperations)
1461 {
1462 SetOperationStmt *topop = castNode(SetOperationStmt, query->setOperations);
1463
1464 Assert(topop->op != SETOP_NONE);
1465
1466 if (!topop->all)
1467 {
1468 ListCell *lg;
1469
1470 /* We're good if all the nonjunk output columns are in colnos */
1471 lg = list_head(topop->groupClauses);
1472 foreach(l, query->targetList)
1473 {
1474 TargetEntry *tle = (TargetEntry *) lfirst(l);
1475 SortGroupClause *sgc;
1476
1477 if (tle->resjunk)
1478 continue; /* ignore resjunk columns */
1479
1480 /* non-resjunk columns should have grouping clauses */
1481 Assert(lg != NULL);
1482 sgc = (SortGroupClause *) lfirst(lg);
1483 lg = lnext(topop->groupClauses, lg);
1484
1485 dcinfo = distinct_col_search(tle->resno, distinct_cols);
1486 if (dcinfo == NULL ||
1487 !equality_ops_are_compatible(dcinfo->opid, sgc->eqop) ||
1488 !collations_agree_on_equality(dcinfo->collid,
1489 exprCollation((Node *) tle->expr)))
1490 break; /* exit early if no match */
1491 }
1492 if (l == NULL) /* had matches for all? */
1493 return true;
1494 }
1495 }
1496
1497 /*
1498 * XXX Are there any other cases in which we can easily see the result
1499 * must be distinct?
1500 *
1501 * If you do add more smarts to this function, be sure to update
1502 * query_supports_distinctness() to match.
1503 */
1504
1505 return false;
1506 }
1507
1508 /*
1509 * distinct_col_search - subroutine for query_is_distinct_for_with_collations
1510 *
1511 * If colno matches the colno field of an entry in distinct_cols, return a
1512 * pointer to that entry; else return NULL. (Ordinarily distinct_cols would
1513 * not contain duplicate colnos, but if it does, we arbitrarily select the
1514 * first match.)
1515 */
1516 static DistinctColInfo *
1517 distinct_col_search(int colno, List *distinct_cols)
1518 {
1519 foreach_ptr(DistinctColInfo, dcinfo, distinct_cols)
1520 {
1521 if (dcinfo->colno == colno)
1522 return dcinfo;
1523 }
1524
1525 return NULL;
1526 }
1527
1528
1529 /*
1530 * innerrel_is_unique
1531 * Check if the innerrel provably contains at most one tuple matching any
1532 * tuple from the outerrel, based on join clauses in the 'restrictlist'.
1533 *
1534 * We need an actual RelOptInfo for the innerrel, but it's sufficient to
1535 * identify the outerrel by its Relids. This asymmetry supports use of this
1536 * function before joinrels have been built. (The caller is expected to
1537 * also supply the joinrelids, just to save recalculating that.)
1538 *
1539 * The proof must be made based only on clauses that will be "joinquals"
1540 * rather than "otherquals" at execution. For an inner join there's no
1541 * difference; but if the join is outer, we must ignore pushed-down quals,
1542 * as those will become "otherquals". Note that this means the answer might
1543 * vary depending on whether IS_OUTER_JOIN(jointype); since we cache the
1544 * answer without regard to that, callers must take care not to call this
1545 * with jointypes that would be classified differently by IS_OUTER_JOIN().
1546 *
1547 * The actual proof is undertaken by is_innerrel_unique_for(); this function
1548 * is a frontend that is mainly concerned with caching the answers.
1549 * In particular, the force_cache argument allows overriding the internal
1550 * heuristic about whether to cache negative answers; it should be "true"
1551 * if making an inquiry that is not part of the normal bottom-up join search
1552 * sequence.
1553 */
1554 bool
1555 innerrel_is_unique(PlannerInfo *root,
1556 Relids joinrelids,
1557 Relids outerrelids,
1558 RelOptInfo *innerrel,
1559 JoinType jointype,
1560 List *restrictlist,
1561 bool force_cache)
1562 {
1563 return innerrel_is_unique_ext(root, joinrelids, outerrelids, innerrel,
1564 jointype, restrictlist, force_cache, NULL);
1565 }
1566
1567 /*
1568 * innerrel_is_unique_ext
1569 * Do the same as innerrel_is_unique(), but also set to (*extra_clauses)
1570 * additional clauses from a baserestrictinfo list used to prove the
1571 * uniqueness.
1572 *
1573 * A non-NULL extra_clauses indicates that we're checking for self-join and
1574 * correspondingly dealing with filtered clauses.
1575 */
1576 bool
1577 innerrel_is_unique_ext(PlannerInfo *root,
1578 Relids joinrelids,
1579 Relids outerrelids,
1580 RelOptInfo *innerrel,
1581 JoinType jointype,
1582 List *restrictlist,
1583 bool force_cache,
1584 List **extra_clauses)
1585 {
1586 MemoryContext old_context;
1587 ListCell *lc;
1588 UniqueRelInfo *uniqueRelInfo;
1589 List *outer_exprs = NIL;
1590 bool self_join = (extra_clauses != NULL);
1591
1592 /* Certainly can't prove uniqueness when there are no joinclauses */
1593 if (restrictlist == NIL)
1594 return false;
1595
1596 /*
1597 * Make a quick check to eliminate cases in which we will surely be unable
1598 * to prove uniqueness of the innerrel.
1599 */
1600 if (!rel_supports_distinctness(root, innerrel))
1601 return false;
1602
1603 /*
1604 * Query the cache to see if we've managed to prove that innerrel is
1605 * unique for any subset of this outerrel. For non-self-join search, we
1606 * don't need an exact match, as extra outerrels can't make the innerrel
1607 * any less unique (or more formally, the restrictlist for a join to a
1608 * superset outerrel must be a superset of the conditions we successfully
1609 * used before). For self-join search, we require an exact match of
1610 * outerrels because we need extra clauses to be valid for our case. Also,
1611 * for self-join checking we've filtered the clauses list. Thus, we can
1612 * match only the result cached for a self-join search for another
1613 * self-join check.
1614 */
1615 foreach(lc, innerrel->unique_for_rels)
1616 {
1617 uniqueRelInfo = (UniqueRelInfo *) lfirst(lc);
1618
1619 if ((!self_join && bms_is_subset(uniqueRelInfo->outerrelids, outerrelids)) ||
1620 (self_join && bms_equal(uniqueRelInfo->outerrelids, outerrelids) &&
1621 uniqueRelInfo->self_join))
1622 {
1623 if (extra_clauses)
1624 *extra_clauses = uniqueRelInfo->extra_clauses;
1625 return true; /* Success! */
1626 }
1627 }
1628
1629 /*
1630 * Conversely, we may have already determined that this outerrel, or some
1631 * superset thereof, cannot prove this innerrel to be unique.
1632 */
1633 foreach(lc, innerrel->non_unique_for_rels)
1634 {
1635 Relids unique_for_rels = (Relids) lfirst(lc);
1636
1637 if (bms_is_subset(outerrelids, unique_for_rels))
1638 return false;
1639 }
1640
1641 /* No cached information, so try to make the proof. */
1642 if (is_innerrel_unique_for(root, joinrelids, outerrelids, innerrel,
1643 jointype, restrictlist,
1644 self_join ? &outer_exprs : NULL))
1645 {
1646 /*
1647 * Cache the positive result for future probes, being sure to keep it
1648 * in the planner_cxt even if we are working in GEQO.
1649 *
1650 * Note: one might consider trying to isolate the minimal subset of
1651 * the outerrels that proved the innerrel unique. But it's not worth
1652 * the trouble, because the planner builds up joinrels incrementally
1653 * and so we'll see the minimally sufficient outerrels before any
1654 * supersets of them anyway.
1655 */
1656 old_context = MemoryContextSwitchTo(root->planner_cxt);
1657 uniqueRelInfo = makeNode(UniqueRelInfo);
1658 uniqueRelInfo->outerrelids = bms_copy(outerrelids);
1659 uniqueRelInfo->self_join = self_join;
1660 uniqueRelInfo->extra_clauses = outer_exprs;
1661 innerrel->unique_for_rels = lappend(innerrel->unique_for_rels,
1662 uniqueRelInfo);
1663 MemoryContextSwitchTo(old_context);
1664
1665 if (extra_clauses)
1666 *extra_clauses = outer_exprs;
1667 return true; /* Success! */
1668 }
1669 else
1670 {
1671 /*
1672 * None of the join conditions for outerrel proved innerrel unique, so
1673 * we can safely reject this outerrel or any subset of it in future
1674 * checks.
1675 *
1676 * However, in normal planning mode, caching this knowledge is totally
1677 * pointless; it won't be queried again, because we build up joinrels
1678 * from smaller to larger. It is useful in GEQO mode, where the
1679 * knowledge can be carried across successive planning attempts; and
1680 * it's likely to be useful when using join-search plugins, too. Hence
1681 * cache when join_search_private is non-NULL. (Yeah, that's a hack,
1682 * but it seems reasonable.)
1683 *
1684 * Also, allow callers to override that heuristic and force caching;
1685 * that's useful for reduce_unique_semijoins, which calls here before
1686 * the normal join search starts.
1687 */
1688 if (force_cache || root->join_search_private)
1689 {
1690 old_context = MemoryContextSwitchTo(root->planner_cxt);
1691 innerrel->non_unique_for_rels =
1692 lappend(innerrel->non_unique_for_rels,
1693 bms_copy(outerrelids));
1694 MemoryContextSwitchTo(old_context);
1695 }
1696
1697 return false;
1698 }
1699 }
1700
1701 /*
1702 * is_innerrel_unique_for
1703 * Check if the innerrel provably contains at most one tuple matching any
1704 * tuple from the outerrel, based on join clauses in the 'restrictlist'.
1705 */
1706 static bool
1707 is_innerrel_unique_for(PlannerInfo *root,
1708 Relids joinrelids,
1709 Relids outerrelids,
1710 RelOptInfo *innerrel,
1711 JoinType jointype,
1712 List *restrictlist,
1713 List **extra_clauses)
1714 {
1715 List *clause_list = NIL;
1716 ListCell *lc;
1717
1718 /*
1719 * Search for mergejoinable clauses that constrain the inner rel against
1720 * the outer rel. If an operator is mergejoinable then it behaves like
1721 * equality for some btree opclass, so it's what we want. The
1722 * mergejoinability test also eliminates clauses containing volatile
1723 * functions, which we couldn't depend on.
1724 */
1725 foreach(lc, restrictlist)
1726 {
1727 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
1728
1729 /*
1730 * As noted above, if it's a pushed-down clause and we're at an outer
1731 * join, we can't use it.
1732 */
1733 if (IS_OUTER_JOIN(jointype) &&
1734 RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
1735 continue;
1736
1737 /* Ignore if it's not a mergejoinable clause */
1738 if (!restrictinfo->can_join ||
1739 restrictinfo->mergeopfamilies == NIL)
1740 continue; /* not mergejoinable */
1741
1742 /*
1743 * Check if the clause has the form "outer op inner" or "inner op
1744 * outer", and if so mark which side is inner.
1745 */
1746 if (!clause_sides_match_join(restrictinfo, outerrelids,
1747 innerrel->relids))
1748 continue; /* no good for these input relations */
1749
1750 /* OK, add to the list */
1751 clause_list = lappend(clause_list, restrictinfo);
1752 }
1753
1754 /* Let rel_is_distinct_for() do the hard work */
1755 return rel_is_distinct_for(root, innerrel, clause_list, extra_clauses);
1756 }
1757
1758 /*
1759 * Update EC members to point to the remaining relation instead of the removed
1760 * one, removing duplicates.
1761 *
1762 * Restriction clauses for base relations are already distributed to
1763 * the respective baserestrictinfo lists (see
1764 * generate_implied_equalities_for_column). The above code has already processed
1765 * this list and updated these clauses to reference the remaining
1766 * relation, so that we can skip them here based on their relids.
1767 *
1768 * Likewise, we have already processed the join clauses that join the
1769 * removed relation to the remaining one.
1770 *
1771 * Finally, there might be join clauses tying the removed relation to
1772 * some third relation. We can't just delete the source clauses and
1773 * regenerate them from the EC because the corresponding equality
1774 * operators might be missing (see the handling of ec_broken).
1775 * Therefore, we will update the references in the source clauses.
1776 *
1777 * Derived clauses can be generated again, so it is simpler just to
1778 * delete them.
1779 */
1780 static void
1781 update_eclasses(EquivalenceClass *ec, int from, int to)
1782 {
1783 List *new_members = NIL;
1784 List *new_sources = NIL;
1785
1786 /*
1787 * We don't expect any EC child members to exist at this point. Ensure
1788 * that's the case, otherwise, we might be getting asked to do something
1789 * this function hasn't been coded for.
1790 */
1791 Assert(ec->ec_childmembers == NULL);
1792
1793 foreach_node(EquivalenceMember, em, ec->ec_members)
1794 {
1795 bool is_redundant = false;
1796
1797 if (!bms_is_member(from, em->em_relids))
1798 {
1799 new_members = lappend(new_members, em);
1800 continue;
1801 }
1802
1803 em->em_relids = adjust_relid_set(em->em_relids, from, to);
1804 em->em_jdomain->jd_relids = adjust_relid_set(em->em_jdomain->jd_relids, from, to);
1805
1806 /* We only process inner joins */
1807 ChangeVarNodesExtended((Node *) em->em_expr, from, to, 0,
1808 replace_relid_callback);
1809
1810 foreach_node(EquivalenceMember, other, new_members)
1811 {
1812 if (!equal(em->em_relids, other->em_relids))
1813 continue;
1814
1815 if (equal(em->em_expr, other->em_expr))
1816 {
1817 is_redundant = true;
1818 break;
1819 }
1820 }
1821
1822 if (!is_redundant)
1823 new_members = lappend(new_members, em);
1824 }
1825
1826 list_free(ec->ec_members);
1827 ec->ec_members = new_members;
1828
1829 ec_clear_derived_clauses(ec);
1830
1831 /* Update EC source expressions */
1832 foreach_node(RestrictInfo, rinfo, ec->ec_sources)
1833 {
1834 bool is_redundant = false;
1835
1836 if (!bms_is_member(from, rinfo->required_relids))
1837 {
1838 new_sources = lappend(new_sources, rinfo);
1839 continue;
1840 }
1841
1842 ChangeVarNodesExtended((Node *) rinfo, from, to, 0,
1843 replace_relid_callback);
1844
1845 /*
1846 * After switching the clause to the remaining relation, check it for
1847 * redundancy with existing ones. We don't have to check for
1848 * redundancy with derived clauses, because we've just deleted them.
1849 */
1850 foreach_node(RestrictInfo, other, new_sources)
1851 {
1852 if (!equal(rinfo->clause_relids, other->clause_relids))
1853 continue;
1854
1855 if (equal(rinfo->clause, other->clause))
1856 {
1857 is_redundant = true;
1858 break;
1859 }
1860 }
1861
1862 if (!is_redundant)
1863 new_sources = lappend(new_sources, rinfo);
1864 }
1865
1866 list_free(ec->ec_sources);
1867 ec->ec_sources = new_sources;
1868 ec->ec_relids = adjust_relid_set(ec->ec_relids, from, to);
1869 }
1870
1871 /*
1872 * "Logically" compares two RestrictInfo's ignoring the 'rinfo_serial' field,
1873 * which makes almost every RestrictInfo unique. This type of comparison is
1874 * useful when removing duplicates while moving RestrictInfo's from removed
1875 * relation to remaining relation during self-join elimination.
1876 *
1877 * XXX: In the future, we might remove the 'rinfo_serial' field completely and
1878 * get rid of this function.
1879 */
1880 static bool
1881 restrict_infos_logically_equal(RestrictInfo *a, RestrictInfo *b)
1882 {
1883 int saved_rinfo_serial = a->rinfo_serial;
1884 bool result;
1885
1886 a->rinfo_serial = b->rinfo_serial;
1887 result = equal(a, b);
1888 a->rinfo_serial = saved_rinfo_serial;
1889
1890 return result;
1891 }
1892
1893 /*
1894 * This function adds all non-redundant clauses to the keeping relation
1895 * during self-join elimination. That is a contradictory operation. On the
1896 * one hand, we reduce the length of the `restrict` lists, which can
1897 * impact planning or executing time. Additionally, we improve the
1898 * accuracy of cardinality estimation. On the other hand, it is one more
1899 * place that can make planning time much longer in specific cases. It
1900 * would have been better to avoid calling the equal() function here, but
1901 * it's the only way to detect duplicated inequality expressions.
1902 *
1903 * (*keep_rinfo_list) is given by pointer because it might be altered by
1904 * distribute_restrictinfo_to_rels().
1905 */
1906 static void
1907 add_non_redundant_clauses(PlannerInfo *root,
1908 List *rinfo_candidates,
1909 List **keep_rinfo_list,
1910 Index removed_relid)
1911 {
1912 foreach_node(RestrictInfo, rinfo, rinfo_candidates)
1913 {
1914 bool is_redundant = false;
1915
1916 Assert(!bms_is_member(removed_relid, rinfo->required_relids));
1917
1918 foreach_node(RestrictInfo, src, (*keep_rinfo_list))
1919 {
1920 if (!bms_equal(src->clause_relids, rinfo->clause_relids))
1921 /* Can't compare trivially different clauses */
1922 continue;
1923
1924 if (src == rinfo ||
1925 (rinfo->parent_ec != NULL &&
1926 src->parent_ec == rinfo->parent_ec) ||
1927 restrict_infos_logically_equal(rinfo, src))
1928 {
1929 is_redundant = true;
1930 break;
1931 }
1932 }
1933 if (!is_redundant)
1934 distribute_restrictinfo_to_rels(root, rinfo);
1935 }
1936 }
1937
1938 /*
1939 * A custom callback for ChangeVarNodesExtended() providing Self-join
1940 * elimination (SJE) related functionality
1941 *
1942 * SJE needs to skip the RangeTblRef node type. During SJE's last
1943 * step, remove_rel_from_joinlist() removes remaining RangeTblRefs
1944 * with target relid. If ChangeVarNodes() replaces the target relid
1945 * before, remove_rel_from_joinlist() would fail to identify the nodes
1946 * to delete.
1947 *
1948 * SJE also needs to change the relids within RestrictInfo's.
1949 */
1950 static bool
1951 replace_relid_callback(Node *node, ChangeVarNodes_context *context)
1952 {
1953 if (IsA(node, RangeTblRef))
1954 {
1955 return true;
1956 }
1957 else if (IsA(node, RestrictInfo))
1958 {
1959 RestrictInfo *rinfo = (RestrictInfo *) node;
1960 int relid = -1;
1961 bool is_req_equal =
1962 (rinfo->required_relids == rinfo->clause_relids);
1963 bool clause_relids_is_multiple =
1964 (bms_membership(rinfo->clause_relids) == BMS_MULTIPLE);
1965
1966 /*
1967 * Recurse down into clauses if the target relation is present in
1968 * clause_relids or required_relids. We must check required_relids
1969 * because the relation not present in clause_relids might still be
1970 * present somewhere in orclause.
1971 */
1972 if (bms_is_member(context->rt_index, rinfo->clause_relids) ||
1973 bms_is_member(context->rt_index, rinfo->required_relids))
1974 {
1975 Relids new_clause_relids;
1976
1977 ChangeVarNodesWalkExpression((Node *) rinfo->clause, context);
1978 ChangeVarNodesWalkExpression((Node *) rinfo->orclause, context);
1979
1980 new_clause_relids = adjust_relid_set(rinfo->clause_relids,
1981 context->rt_index,
1982 context->new_index);
1983
1984 /*
1985 * Incrementally adjust num_base_rels based on the change of
1986 * clause_relids, which could contain both base relids and
1987 * outer-join relids. This operation is legal until we remove
1988 * only baserels.
1989 */
1990 rinfo->num_base_rels -= bms_num_members(rinfo->clause_relids) -
1991 bms_num_members(new_clause_relids);
1992
1993 rinfo->clause_relids = new_clause_relids;
1994 rinfo->left_relids =
1995 adjust_relid_set(rinfo->left_relids, context->rt_index, context->new_index);
1996 rinfo->right_relids =
1997 adjust_relid_set(rinfo->right_relids, context->rt_index, context->new_index);
1998 }
1999
2000 if (is_req_equal)
2001 rinfo->required_relids = rinfo->clause_relids;
2002 else
2003 rinfo->required_relids =
2004 adjust_relid_set(rinfo->required_relids, context->rt_index, context->new_index);
2005
2006 rinfo->outer_relids =
2007 adjust_relid_set(rinfo->outer_relids, context->rt_index, context->new_index);
2008 rinfo->incompatible_relids =
2009 adjust_relid_set(rinfo->incompatible_relids, context->rt_index, context->new_index);
2010
2011 if (rinfo->mergeopfamilies &&
2012 bms_get_singleton_member(rinfo->clause_relids, &relid) &&
2013 clause_relids_is_multiple &&
2014 relid == context->new_index && IsA(rinfo->clause, OpExpr))
2015 {
2016 Expr *leftOp;
2017 Expr *rightOp;
2018
2019 leftOp = (Expr *) get_leftop(rinfo->clause);
2020 rightOp = (Expr *) get_rightop(rinfo->clause);
2021
2022 /*
2023 * For self-join elimination, changing varnos could transform
2024 * "t1.a = t2.a" into "t1.a = t1.a". That is always true as long
2025 * as "t1.a" is not null. We use equal() to check for such a
2026 * case, and then we replace the qual with a check for not null
2027 * (NullTest).
2028 */
2029 if (leftOp != NULL && equal(leftOp, rightOp))
2030 {
2031 NullTest *ntest = makeNode(NullTest);
2032
2033 ntest->arg = leftOp;
2034 ntest->nulltesttype = IS_NOT_NULL;
2035 ntest->argisrow = false;
2036 ntest->location = -1;
2037 rinfo->clause = (Expr *) ntest;
2038 rinfo->mergeopfamilies = NIL;
2039 rinfo->left_em = NULL;
2040 rinfo->right_em = NULL;
2041 }
2042 Assert(rinfo->orclause == NULL);
2043 }
2044 return true;
2045 }
2046
2047 return false;
2048 }
2049
2050 /*
2051 * Remove a relation after we have proven that it participates only in an
2052 * unneeded unique self-join.
2053 *
2054 * Replace any links in planner info structures.
2055 *
2056 * Transfer join and restriction clauses from the removed relation to the
2057 * remaining one. We change the Vars of the clause to point to the
2058 * remaining relation instead of the removed one. The clauses that require
2059 * a subset of joinrelids become restriction clauses of the remaining
2060 * relation, and others remain join clauses. We append them to
2061 * baserestrictinfo and joininfo, respectively, trying not to introduce
2062 * duplicates.
2063 *
2064 * We also have to process the 'joinclauses' list here, because it
2065 * contains EC-derived join clauses which must become filter clauses. It
2066 * is not enough to just correct the ECs because the EC-derived
2067 * restrictions are generated before join removal (see
2068 * generate_base_implied_equalities).
2069 *
2070 * NOTE: Remember to keep the code in sync with PlannerInfo to be sure all
2071 * cached relids and relid bitmapsets can be correctly cleaned during the
2072 * self-join elimination procedure.
2073 */
2074 static void
2075 remove_self_join_rel(PlannerInfo *root, PlanRowMark *kmark, PlanRowMark *rmark,
2076 RelOptInfo *toKeep, RelOptInfo *toRemove,
2077 List *restrictlist)
2078 {
2079 List *joininfos;
2080 ListCell *lc;
2081 int i;
2082 List *jinfo_candidates = NIL;
2083 List *binfo_candidates = NIL;
2084
2085 Assert(toKeep->relid > 0);
2086 Assert(toRemove->relid > 0);
2087
2088 /*
2089 * Replace the index of the removing table with the keeping one. The
2090 * technique of removing/distributing restrictinfo is used here to attach
2091 * just appeared (for keeping relation) join clauses and avoid adding
2092 * duplicates of those that already exist in the joininfo list.
2093 */
2094 joininfos = list_copy(toRemove->joininfo);
2095 foreach_node(RestrictInfo, rinfo, joininfos)
2096 {
2097 remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);
2098 ChangeVarNodesExtended((Node *) rinfo, toRemove->relid, toKeep->relid,
2099 0, replace_relid_callback);
2100
2101 if (bms_membership(rinfo->required_relids) == BMS_MULTIPLE)
2102 jinfo_candidates = lappend(jinfo_candidates, rinfo);
2103 else
2104 binfo_candidates = lappend(binfo_candidates, rinfo);
2105 }
2106
2107 /*
2108 * Concatenate restrictlist to the list of base restrictions of the
2109 * removing table just to simplify the replacement procedure: all of them
2110 * weren't connected to any keeping relations and need to be added to some
2111 * rels.
2112 */
2113 toRemove->baserestrictinfo = list_concat(toRemove->baserestrictinfo,
2114 restrictlist);
2115 foreach_node(RestrictInfo, rinfo, toRemove->baserestrictinfo)
2116 {
2117 ChangeVarNodesExtended((Node *) rinfo, toRemove->relid, toKeep->relid,
2118 0, replace_relid_callback);
2119
2120 if (bms_membership(rinfo->required_relids) == BMS_MULTIPLE)
2121 jinfo_candidates = lappend(jinfo_candidates, rinfo);
2122 else
2123 binfo_candidates = lappend(binfo_candidates, rinfo);
2124 }
2125
2126 /*
2127 * Now, add all non-redundant clauses to the keeping relation.
2128 */
2129 add_non_redundant_clauses(root, binfo_candidates,
2130 &toKeep->baserestrictinfo, toRemove->relid);
2131 add_non_redundant_clauses(root, jinfo_candidates,
2132 &toKeep->joininfo, toRemove->relid);
2133
2134 list_free(binfo_candidates);
2135 list_free(jinfo_candidates);
2136
2137 /*
2138 * Arrange equivalence classes, mentioned removing a table, with the
2139 * keeping one: varno of removing table should be replaced in members and
2140 * sources lists. Also, remove duplicated elements if this replacement
2141 * procedure created them.
2142 */
2143 i = -1;
2144 while ((i = bms_next_member(toRemove->eclass_indexes, i)) >= 0)
2145 {
2146 EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes, i);
2147
2148 update_eclasses(ec, toRemove->relid, toKeep->relid);
2149 toKeep->eclass_indexes = bms_add_member(toKeep->eclass_indexes, i);
2150 }
2151
2152 /*
2153 * Transfer the targetlist and attr_needed flags.
2154 */
2155
2156 foreach(lc, toRemove->reltarget->exprs)
2157 {
2158 Node *node = lfirst(lc);
2159
2160 ChangeVarNodesExtended(node, toRemove->relid, toKeep->relid, 0,
2161 replace_relid_callback);
2162 if (!list_member(toKeep->reltarget->exprs, node))
2163 toKeep->reltarget->exprs = lappend(toKeep->reltarget->exprs, node);
2164 }
2165
2166 for (i = toKeep->min_attr; i <= toKeep->max_attr; i++)
2167 {
2168 int attno = i - toKeep->min_attr;
2169
2170 toRemove->attr_needed[attno] = adjust_relid_set(toRemove->attr_needed[attno],
2171 toRemove->relid, toKeep->relid);
2172 toKeep->attr_needed[attno] = bms_add_members(toKeep->attr_needed[attno],
2173 toRemove->attr_needed[attno]);
2174 }
2175
2176 /*
2177 * If the removed relation has a row mark, transfer it to the remaining
2178 * one.
2179 *
2180 * If both rels have row marks, just keep the one corresponding to the
2181 * remaining relation because we verified earlier that they have the same
2182 * strength.
2183 */
2184 if (rmark)
2185 {
2186 if (kmark)
2187 {
2188 Assert(kmark->markType == rmark->markType);
2189
2190 root->rowMarks = list_delete_ptr(root->rowMarks, rmark);
2191 }
2192 else
2193 {
2194 /* Shouldn't have inheritance children here. */
2195 Assert(rmark->rti == rmark->prti);
2196
2197 rmark->rti = rmark->prti = toKeep->relid;
2198 }
2199 }
2200
2201 /*
2202 * Replace varno in all the query structures, except nodes RangeTblRef
2203 * otherwise later remove_rel_from_joinlist will yield errors.
2204 */
2205 ChangeVarNodesExtended((Node *) root->parse, toRemove->relid, toKeep->relid,
2206 0, replace_relid_callback);
2207
2208 /* Replace links in the planner info */
2209 remove_rel_from_query(root, toRemove, toKeep->relid, NULL, NULL);
2210
2211 /* At last, replace varno in root targetlist and HAVING clause */
2212 ChangeVarNodesExtended((Node *) root->processed_tlist, toRemove->relid,
2213 toKeep->relid, 0, replace_relid_callback);
2214 ChangeVarNodesExtended((Node *) root->processed_groupClause,
2215 toRemove->relid, toKeep->relid, 0,
2216 replace_relid_callback);
2217
2218 adjust_relid_set(root->all_result_relids, toRemove->relid, toKeep->relid);
2219 adjust_relid_set(root->leaf_result_relids, toRemove->relid, toKeep->relid);
2220
2221 /*
2222 * There may be references to the rel in root->fkey_list, but if so,
2223 * match_foreign_keys_to_quals() will get rid of them.
2224 */
2225
2226 /*
2227 * Finally, remove the rel from the baserel array to prevent it from being
2228 * referenced again. (We can't do this earlier because
2229 * remove_join_clause_from_rels will touch it.)
2230 */
2231 root->simple_rel_array[toRemove->relid] = NULL;
2232 root->simple_rte_array[toRemove->relid] = NULL;
2233
2234 /* And nuke the RelOptInfo, just in case there's another access path. */
2235 pfree(toRemove);
2236
2237
2238 /*
2239 * Now repeat construction of attr_needed bits coming from all other
2240 * sources.
2241 */
2242 rebuild_placeholder_attr_needed(root);
2243 rebuild_joinclause_attr_needed(root);
2244 rebuild_eclass_attr_needed(root);
2245 rebuild_lateral_attr_needed(root);
2246 }
2247
2248 /*
2249 * split_selfjoin_quals
2250 * Processes 'joinquals' by building two lists: one containing the quals
2251 * where the columns/exprs are on either side of the join match and
2252 * another one containing the remaining quals.
2253 *
2254 * 'joinquals' must only contain quals for a RTE_RELATION being joined to
2255 * itself.
2256 */
2257 static void
2258 split_selfjoin_quals(PlannerInfo *root, List *joinquals, List **selfjoinquals,
2259 List **otherjoinquals, int from, int to)
2260 {
2261 List *sjoinquals = NIL;
2262 List *ojoinquals = NIL;
2263
2264 foreach_node(RestrictInfo, rinfo, joinquals)
2265 {
2266 OpExpr *expr;
2267 Node *leftexpr;
2268 Node *rightexpr;
2269
2270 /* In general, clause looks like F(arg1) = G(arg2) */
2271 if (!rinfo->mergeopfamilies ||
2272 bms_num_members(rinfo->clause_relids) != 2 ||
2273 bms_membership(rinfo->left_relids) != BMS_SINGLETON ||
2274 bms_membership(rinfo->right_relids) != BMS_SINGLETON)
2275 {
2276 ojoinquals = lappend(ojoinquals, rinfo);
2277 continue;
2278 }
2279
2280 expr = (OpExpr *) rinfo->clause;
2281
2282 if (!IsA(expr, OpExpr) || list_length(expr->args) != 2)
2283 {
2284 ojoinquals = lappend(ojoinquals, rinfo);
2285 continue;
2286 }
2287
2288 leftexpr = get_leftop(rinfo->clause);
2289 rightexpr = copyObject(get_rightop(rinfo->clause));
2290
2291 if (leftexpr && IsA(leftexpr, RelabelType))
2292 leftexpr = (Node *) ((RelabelType *) leftexpr)->arg;
2293 if (rightexpr && IsA(rightexpr, RelabelType))
2294 rightexpr = (Node *) ((RelabelType *) rightexpr)->arg;
2295
2296 /*
2297 * Quite an expensive operation, narrowing the use case. For example,
2298 * when we have cast of the same var to different (but compatible)
2299 * types.
2300 */
2301 ChangeVarNodesExtended(rightexpr,
2302 bms_singleton_member(rinfo->right_relids),
2303 bms_singleton_member(rinfo->left_relids), 0,
2304 replace_relid_callback);
2305
2306 if (equal(leftexpr, rightexpr))
2307 sjoinquals = lappend(sjoinquals, rinfo);
2308 else
2309 ojoinquals = lappend(ojoinquals, rinfo);
2310 }
2311
2312 *selfjoinquals = sjoinquals;
2313 *otherjoinquals = ojoinquals;
2314 }
2315
2316 /*
2317 * Check for a case when uniqueness is at least partly derived from a
2318 * baserestrictinfo clause. In this case, we have a chance to return only
2319 * one row (if such clauses on both sides of SJ are equal) or nothing (if they
2320 * are different).
2321 */
2322 static bool
2323 match_unique_clauses(PlannerInfo *root, RelOptInfo *outer, List *uclauses,
2324 Index relid)
2325 {
2326 foreach_node(RestrictInfo, rinfo, uclauses)
2327 {
2328 Expr *clause;
2329 Node *iclause;
2330 Node *c1;
2331 bool matched = false;
2332
2333 Assert(outer->relid > 0 && relid > 0);
2334
2335 /* Only filters like f(R.x1,...,R.xN) == expr we should consider. */
2336 Assert(bms_is_empty(rinfo->left_relids) ^
2337 bms_is_empty(rinfo->right_relids));
2338
2339 clause = (Expr *) copyObject(rinfo->clause);
2340 ChangeVarNodesExtended((Node *) clause, relid, outer->relid, 0,
2341 replace_relid_callback);
2342
2343 iclause = bms_is_empty(rinfo->left_relids) ? get_rightop(clause) :
2344 get_leftop(clause);
2345 c1 = bms_is_empty(rinfo->left_relids) ? get_leftop(clause) :
2346 get_rightop(clause);
2347
2348 /*
2349 * Compare these left and right sides with the corresponding sides of
2350 * the outer's filters. If no one is detected - return immediately.
2351 */
2352 foreach_node(RestrictInfo, orinfo, outer->baserestrictinfo)
2353 {
2354 Node *oclause;
2355 Node *c2;
2356
2357 if (orinfo->mergeopfamilies == NIL)
2358 /* Don't consider clauses that aren't similar to 'F(X)=G(Y)' */
2359 continue;
2360
2361 Assert(is_opclause(orinfo->clause));
2362
2363 oclause = bms_is_empty(orinfo->left_relids) ?
2364 get_rightop(orinfo->clause) : get_leftop(orinfo->clause);
2365 c2 = (bms_is_empty(orinfo->left_relids) ?
2366 get_leftop(orinfo->clause) : get_rightop(orinfo->clause));
2367
2368 if (equal(iclause, oclause) && equal(c1, c2))
2369 {
2370 matched = true;
2371 break;
2372 }
2373 }
2374
2375 if (!matched)
2376 return false;
2377 }
2378
2379 return true;
2380 }
2381
2382 /*
2383 * Find and remove unique self-joins in a group of base relations that have
2384 * the same Oid.
2385 *
2386 * Returns a set of relids that were removed.
2387 */
2388 static Relids
2389 remove_self_joins_one_group(PlannerInfo *root, Relids relids)
2390 {
2391 Relids result = NULL;
2392 int k; /* Index of kept relation */
2393 int r = -1; /* Index of removed relation */
2394
2395 while ((r = bms_next_member(relids, r)) > 0)
2396 {
2397 RelOptInfo *rrel = root->simple_rel_array[r];
2398
2399 k = r;
2400
2401 while ((k = bms_next_member(relids, k)) > 0)
2402 {
2403 Relids joinrelids = NULL;
2404 RelOptInfo *krel = root->simple_rel_array[k];
2405 List *restrictlist;
2406 List *selfjoinquals;
2407 List *otherjoinquals;
2408 ListCell *lc;
2409 bool jinfo_check = true;
2410 PlanRowMark *kmark = NULL;
2411 PlanRowMark *rmark = NULL;
2412 List *uclauses = NIL;
2413
2414 /* A sanity check: the relations have the same Oid. */
2415 Assert(root->simple_rte_array[k]->relid ==
2416 root->simple_rte_array[r]->relid);
2417
2418 /*
2419 * It is impossible to eliminate the join of two relations if they
2420 * belong to different rules of order. Otherwise, the planner
2421 * can't find any variants of the correct query plan.
2422 */
2423 foreach(lc, root->join_info_list)
2424 {
2425 SpecialJoinInfo *info = (SpecialJoinInfo *) lfirst(lc);
2426
2427 if ((bms_is_member(k, info->syn_lefthand) ^
2428 bms_is_member(r, info->syn_lefthand)) ||
2429 (bms_is_member(k, info->syn_righthand) ^
2430 bms_is_member(r, info->syn_righthand)))
2431 {
2432 jinfo_check = false;
2433 break;
2434 }
2435 }
2436 if (!jinfo_check)
2437 continue;
2438
2439 /*
2440 * Check Row Marks equivalence. We can't remove the join if the
2441 * relations have row marks of different strength (e.g., one is
2442 * locked FOR UPDATE, and another just has ROW_MARK_REFERENCE for
2443 * EvalPlanQual rechecking).
2444 */
2445 foreach(lc, root->rowMarks)
2446 {
2447 PlanRowMark *rowMark = (PlanRowMark *) lfirst(lc);
2448
2449 if (rowMark->rti == r)
2450 {
2451 Assert(rmark == NULL);
2452 rmark = rowMark;
2453 }
2454 else if (rowMark->rti == k)
2455 {
2456 Assert(kmark == NULL);
2457 kmark = rowMark;
2458 }
2459
2460 if (kmark && rmark)
2461 break;
2462 }
2463 if (kmark && rmark && kmark->markType != rmark->markType)
2464 continue;
2465
2466 /*
2467 * We only deal with base rels here, so their relids bitset
2468 * contains only one member -- their relid.
2469 */
2470 joinrelids = bms_add_member(joinrelids, r);
2471 joinrelids = bms_add_member(joinrelids, k);
2472
2473 /*
2474 * PHVs should not impose any constraints on removing self-joins.
2475 */
2476
2477 /*
2478 * At this stage, joininfo lists of inner and outer can contain
2479 * only clauses required for a superior outer join that can't
2480 * influence this optimization. So, we can avoid to call the
2481 * build_joinrel_restrictlist() routine.
2482 */
2483 restrictlist = generate_join_implied_equalities(root, joinrelids,
2484 rrel->relids,
2485 krel, NULL);
2486 if (restrictlist == NIL)
2487 continue;
2488
2489 /*
2490 * Process restrictlist to separate the self-join quals from the
2491 * other quals. e.g., "x = x" goes to selfjoinquals and "a = b" to
2492 * otherjoinquals.
2493 */
2494 split_selfjoin_quals(root, restrictlist, &selfjoinquals,
2495 &otherjoinquals, rrel->relid, krel->relid);
2496
2497 Assert(list_length(restrictlist) ==
2498 (list_length(selfjoinquals) + list_length(otherjoinquals)));
2499
2500 /*
2501 * To enable SJE for the only degenerate case without any self
2502 * join clauses at all, add baserestrictinfo to this list. The
2503 * degenerate case works only if both sides have the same clause.
2504 * So doesn't matter which side to add.
2505 */
2506 selfjoinquals = list_concat(selfjoinquals, krel->baserestrictinfo);
2507
2508 /*
2509 * Determine if the rrel can duplicate outer rows. We must bypass
2510 * the unique rel cache here since we're possibly using a subset
2511 * of join quals. We can use 'force_cache' == true when all join
2512 * quals are self-join quals. Otherwise, we could end up putting
2513 * false negatives in the cache.
2514 */
2515 if (!innerrel_is_unique_ext(root, joinrelids, rrel->relids,
2516 krel, JOIN_INNER, selfjoinquals,
2517 list_length(otherjoinquals) == 0,
2518 &uclauses))
2519 continue;
2520
2521 /*
2522 * 'uclauses' is the copy of outer->baserestrictinfo that are
2523 * associated with an index. We proved by matching selfjoinquals
2524 * to a unique index that the outer relation has at most one
2525 * matching row for each inner row. Sometimes that is not enough.
2526 * e.g. "WHERE s1.b = s2.b AND s1.a = 1 AND s2.a = 2" when the
2527 * unique index is (a,b). Having non-empty uclauses, we must
2528 * validate that the inner baserestrictinfo contains the same
2529 * expressions, or we won't match the same row on each side of the
2530 * join.
2531 */
2532 if (!match_unique_clauses(root, rrel, uclauses, krel->relid))
2533 continue;
2534
2535 /*
2536 * Remove rrel ReloptInfo from the planner structures and the
2537 * corresponding row mark.
2538 */
2539 remove_self_join_rel(root, kmark, rmark, krel, rrel, restrictlist);
2540
2541 result = bms_add_member(result, r);
2542
2543 /* We have removed the outer relation, try the next one. */
2544 break;
2545 }
2546 }
2547
2548 return result;
2549 }
2550
2551 /*
2552 * Gather indexes of base relations from the joinlist and try to eliminate self
2553 * joins.
2554 */
2555 static Relids
2556 remove_self_joins_recurse(PlannerInfo *root, List *joinlist, Relids toRemove)
2557 {
2558 ListCell *jl;
2559 Relids relids = NULL;
2560 SelfJoinCandidate *candidates = NULL;
2561 int i;
2562 int j;
2563 int numRels;
2564
2565 /* Collect indexes of base relations of the join tree */
2566 foreach(jl, joinlist)
2567 {
2568 Node *jlnode = (Node *) lfirst(jl);
2569
2570 if (IsA(jlnode, RangeTblRef))
2571 {
2572 int varno = ((RangeTblRef *) jlnode)->rtindex;
2573 RangeTblEntry *rte = root->simple_rte_array[varno];
2574
2575 /*
2576 * We only consider ordinary relations as candidates to be
2577 * removed, and these relations should not have TABLESAMPLE
2578 * clauses specified. Removing a relation with TABLESAMPLE clause
2579 * could potentially change the syntax of the query. Because of
2580 * UPDATE/DELETE EPQ mechanism, currently Query->resultRelation or
2581 * Query->mergeTargetRelation associated rel cannot be eliminated.
2582 */
2583 if (rte->rtekind == RTE_RELATION &&
2584 rte->relkind == RELKIND_RELATION &&
2585 rte->tablesample == NULL &&
2586 varno != root->parse->resultRelation &&
2587 varno != root->parse->mergeTargetRelation)
2588 {
2589 Assert(!bms_is_member(varno, relids));
2590 relids = bms_add_member(relids, varno);
2591 }
2592 }
2593 else if (IsA(jlnode, List))
2594 {
2595 /* Recursively go inside the sub-joinlist */
2596 toRemove = remove_self_joins_recurse(root, (List *) jlnode,
2597 toRemove);
2598 }
2599 else
2600 elog(ERROR, "unrecognized joinlist node type: %d",
2601 (int) nodeTag(jlnode));
2602 }
2603
2604 numRels = bms_num_members(relids);
2605
2606 /* Need at least two relations for the join */
2607 if (numRels < 2)
2608 return toRemove;
2609
2610 /*
2611 * In order to find relations with the same oid we first build an array of
2612 * candidates and then sort it by oid.
2613 */
2614 candidates = (SelfJoinCandidate *) palloc(sizeof(SelfJoinCandidate) *
2615 numRels);
2616 i = -1;
2617 j = 0;
2618 while ((i = bms_next_member(relids, i)) >= 0)
2619 {
2620 candidates[j].relid = i;
2621 candidates[j].reloid = root->simple_rte_array[i]->relid;
2622 j++;
2623 }
2624
2625 qsort(candidates, numRels, sizeof(SelfJoinCandidate),
2626 self_join_candidates_cmp);
2627
2628 /*
2629 * Iteratively form a group of relation indexes with the same oid and
2630 * launch the routine that detects self-joins in this group and removes
2631 * excessive range table entries.
2632 *
2633 * At the end of the iteration, exclude the group from the overall relids
2634 * list. So each next iteration of the cycle will involve less and less
2635 * value of relids.
2636 */
2637 i = 0;
2638 for (j = 1; j < numRels + 1; j++)
2639 {
2640 if (j == numRels || candidates[j].reloid != candidates[i].reloid)
2641 {
2642 if (j - i >= 2)
2643 {
2644 /* Create a group of relation indexes with the same oid */
2645 Relids group = NULL;
2646 Relids removed;
2647
2648 while (i < j)
2649 {
2650 group = bms_add_member(group, candidates[i].relid);
2651 i++;
2652 }
2653 relids = bms_del_members(relids, group);
2654
2655 /*
2656 * Try to remove self-joins from a group of identical entries.
2657 * Make the next attempt iteratively - if something is deleted
2658 * from a group, changes in clauses and equivalence classes
2659 * can give us a chance to find more candidates.
2660 */
2661 do
2662 {
2663 Assert(!bms_overlap(group, toRemove));
2664 removed = remove_self_joins_one_group(root, group);
2665 toRemove = bms_add_members(toRemove, removed);
2666 group = bms_del_members(group, removed);
2667 } while (!bms_is_empty(removed) &&
2668 bms_membership(group) == BMS_MULTIPLE);
2669 bms_free(removed);
2670 bms_free(group);
2671 }
2672 else
2673 {
2674 /* Single relation, just remove it from the set */
2675 relids = bms_del_member(relids, candidates[i].relid);
2676 i = j;
2677 }
2678 }
2679 }
2680
2681 Assert(bms_is_empty(relids));
2682
2683 return toRemove;
2684 }
2685
2686 /*
2687 * Compare self-join candidates by their oids.
2688 */
2689 static int
2690 self_join_candidates_cmp(const void *a, const void *b)
2691 {
2692 const SelfJoinCandidate *ca = (const SelfJoinCandidate *) a;
2693 const SelfJoinCandidate *cb = (const SelfJoinCandidate *) b;
2694
2695 if (ca->reloid != cb->reloid)
2696 return (ca->reloid < cb->reloid ? -1 : 1);
2697 else
2698 return 0;
2699 }
2700
2701 /*
2702 * Find and remove useless self joins.
2703 *
2704 * Search for joins where a relation is joined to itself. If the join clause
2705 * for each tuple from one side of the join is proven to match the same
2706 * physical row (or nothing) on the other side, that self-join can be
2707 * eliminated from the query. Suitable join clauses are assumed to be in the
2708 * form of X = X, and can be replaced with NOT NULL clauses.
2709 *
2710 * For the sake of simplicity, we don't apply this optimization to special
2711 * joins. Here is a list of what we could do in some particular cases:
2712 * 'a a1 semi join a a2': is reduced to inner by reduce_unique_semijoins,
2713 * and then removed normally.
2714 * 'a a1 anti join a a2': could simplify to a scan with 'outer quals AND
2715 * (IS NULL on join columns OR NOT inner quals)'.
2716 * 'a a1 left join a a2': could simplify to a scan like inner but without
2717 * NOT NULL conditions on join columns.
2718 * 'a a1 left join (a a2 join b)': can't simplify this, because join to b
2719 * can both remove rows and introduce duplicates.
2720 *
2721 * To search for removable joins, we order all the relations on their Oid,
2722 * go over each set with the same Oid, and consider each pair of relations
2723 * in this set.
2724 *
2725 * To remove the join, we mark one of the participating relations as dead
2726 * and rewrite all references to it to point to the remaining relation.
2727 * This includes modifying RestrictInfos, EquivalenceClasses, and
2728 * EquivalenceMembers. We also have to modify the row marks. The join clauses
2729 * of the removed relation become either restriction or join clauses, based on
2730 * whether they reference any relations not participating in the removed join.
2731 *
2732 * 'joinlist' is the top-level joinlist of the query. If it has any
2733 * references to the removed relations, we update them to point to the
2734 * remaining ones.
2735 */
2736 List *
2737 remove_useless_self_joins(PlannerInfo *root, List *joinlist)
2738 {
2739 Relids toRemove = NULL;
2740 int relid = -1;
2741
2742 if (!enable_self_join_elimination || joinlist == NIL ||
2743 (list_length(joinlist) == 1 && !IsA(linitial(joinlist), List)))
2744 return joinlist;
2745
2746 /*
2747 * Merge pairs of relations participated in self-join. Remove unnecessary
2748 * range table entries.
2749 */
2750 toRemove = remove_self_joins_recurse(root, joinlist, toRemove);
2751
2752 if (unlikely(toRemove != NULL))
2753 {
2754 /* At the end, remove orphaned relation links */
2755 while ((relid = bms_next_member(toRemove, relid)) >= 0)
2756 {
2757 int nremoved = 0;
2758
2759 joinlist = remove_rel_from_joinlist(joinlist, relid, &nremoved);
2760 if (nremoved != 1)
2761 elog(ERROR, "failed to find relation %d in joinlist", relid);
2762 }
2763 }
2764
2765 return joinlist;
2766 }