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