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