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