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.
11 : : *
12 : : * Although the decisions about what can be removed are made using the
13 : : * planner's derived data structures, the removals themselves are implemented
14 : : * by editing the query's jointree, which is a far simpler and more stable
15 : : * representation. We make no attempt to update the derived data structures
16 : : * to match; instead, query_planner() throws them all away and recomputes them
17 : : * whenever we report having removed something.
18 : : *
19 : : * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
20 : : * Portions Copyright (c) 1994, Regents of the University of California
21 : : *
22 : : *
23 : : * IDENTIFICATION
24 : : * src/backend/optimizer/plan/analyzejoins.c
25 : : *
26 : : *-------------------------------------------------------------------------
27 : : */
28 : : #include "postgres.h"
29 : :
30 : : #include "catalog/pg_class.h"
31 : : #include "nodes/makefuncs.h"
32 : : #include "nodes/nodeFuncs.h"
33 : : #include "optimizer/optimizer.h"
34 : : #include "optimizer/pathnode.h"
35 : : #include "optimizer/paths.h"
36 : : #include "optimizer/planmain.h"
37 : : #include "optimizer/prep.h"
38 : : #include "optimizer/restrictinfo.h"
39 : : #include "parser/parse_agg.h"
40 : : #include "parser/parse_relation.h"
41 : : #include "rewrite/rewriteManip.h"
42 : : #include "utils/lsyscache.h"
43 : :
44 : : /*
45 : : * Utility structure. A sorting procedure is needed to simplify the search
46 : : * for SJE-candidate baserels, which must reference the same database relation
47 : : * with the same reader permissions (checkAsUser value). We require the
48 : : * checkAsUser fields to match to ensure that merged RTEs carry the same
49 : : * securityQuals; in future this rule might keep us out of trouble with other
50 : : * role-based features, too. Having collected all baserels from the jointree,
51 : : * remove_self_joins_recurse sorts them according to their reloid and useroid
52 : : * values, groups them in another pass and attempts to remove self-joins
53 : : * within each group. This preliminary sorting prevents quadratic behavior
54 : : * in the case of numerous joins.
55 : : */
56 : : typedef struct
57 : : {
58 : : int relid;
59 : : Oid reloid;
60 : : Oid useroid;
61 : : } SelfJoinCandidate;
62 : :
63 : : bool enable_self_join_elimination;
64 : :
65 : : /* local functions */
66 : : static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
67 : : static Node *remove_join_from_jointree(Node *jtnode, int ojrelid,
68 : : int *nremoved);
69 : : static void remove_rels_from_query_tree(PlannerInfo *root,
70 : : Relids removed_relids);
71 : : static bool reduce_semijoin_in_jointree(Node *jtnode, Relids syn_righthand);
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 innerrel_is_unique_ext(PlannerInfo *root,
77 : : Relids joinrelids,
78 : : Relids outerrelids,
79 : : RelOptInfo *innerrel,
80 : : JoinType jointype,
81 : : List *restrictlist,
82 : : bool force_cache,
83 : : List **extra_clauses);
84 : : static bool is_innerrel_unique_for(PlannerInfo *root,
85 : : Relids joinrelids,
86 : : Relids outerrelids,
87 : : RelOptInfo *innerrel,
88 : : JoinType jointype,
89 : : List *restrictlist,
90 : : List **extra_clauses);
91 : : static Node *remove_rel_from_jointree(Node *jtnode, int relid,
92 : : Node **orphan_quals, int *nremoved);
93 : : static Node *merge_quals(Node *quals1, Node *quals2);
94 : : static void fixup_selfjoin_jointree(PlannerInfo *root, Node *jtnode, int relid,
95 : : Node **hoist_quals, bool *found_relid);
96 : : static List *fixup_selfjoin_quals(PlannerInfo *root, List *quals, int relid);
97 : : static Node *replace_selfjoin_qual(Node *qual);
98 : : static int self_join_candidates_cmp(const void *a, const void *b);
99 : :
100 : :
101 : : /*
102 : : * remove_useless_outer_joins
103 : : * Check for relations that don't actually need to be joined at all,
104 : : * and remove them from the query's jointree.
105 : : *
106 : : * Returns true if we removed anything. In that case the caller must discard
107 : : * everything it has derived from the jointree and compute it over again,
108 : : * since we don't try to update any of that here.
109 : : */
110 : : bool
45 tgl@sss.pgh.pa.us 111 :CBC 254004 : remove_useless_outer_joins(PlannerInfo *root)
112 : : {
113 : 254004 : Relids removed_relids = NULL;
114 : : ListCell *lc;
115 : :
116 : : /*
117 : : * We are only interested in relations that are left-joined to, so we can
118 : : * scan the join_info_list to find them easily.
119 : : */
6042 120 [ + + + + : 303101 : foreach(lc, root->join_info_list)
+ + ]
121 : : {
122 : 49097 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
123 : : int innerrelid;
124 : : int nremoved;
125 : : RangeTblEntry *rte;
126 : :
127 : : /* Skip if not removable */
128 [ + + ]: 49097 : if (!join_is_removable(root, sjinfo))
129 : 40297 : continue;
130 : :
131 : : /*
132 : : * join_is_removable insists that the join's syntactic righthand side
133 : : * be a single baserel, so we can implement the removal by dropping
134 : : * the JoinExpr and everything below its righthand side.
135 : : */
45 136 : 8800 : innerrelid = bms_singleton_member(sjinfo->syn_righthand);
137 : :
138 : : /* We verify that exactly one JoinExpr gets removed */
6042 139 : 8800 : nremoved = 0;
45 140 : 17600 : root->parse->jointree = (FromExpr *)
141 : 8800 : remove_join_from_jointree((Node *) root->parse->jointree,
142 : 8800 : sjinfo->ojrelid, &nremoved);
6042 143 [ - + ]: 8800 : if (nremoved != 1)
45 tgl@sss.pgh.pa.us 144 [ # # ]:UBC 0 : elog(ERROR, "failed to find join %d in jointree", sjinfo->ojrelid);
145 : :
146 : : /* Track all the relids we've removed, for use below */
45 tgl@sss.pgh.pa.us 147 :CBC 8800 : removed_relids = bms_add_member(removed_relids, innerrelid);
148 : 8800 : removed_relids = bms_add_member(removed_relids, sjinfo->ojrelid);
149 : :
150 : : /*
151 : : * As in pull_up_simple_subquery, discard no-longer-needed subqueries.
152 : : * This is not just an optimization, but is necessary to prevent
153 : : * subsequent processing from descending into stale subtrees and
154 : : * seeing inconsistent data. Likewise discard any securityQuals of
155 : : * the removed rel. (Although simple_rte_array[] will be rebuilt
156 : : * shortly, we can still use it to find the RTE in the parse tree.)
157 : : */
158 : 8800 : rte = root->simple_rte_array[innerrelid];
159 [ + + ]: 8800 : if (rte->rtekind == RTE_SUBQUERY)
160 : 193 : rte->subquery = NULL;
161 : 8800 : rte->securityQuals = NIL;
162 : :
163 : : /*
164 : : * It's okay to keep scanning join_info_list for more removable joins,
165 : : * even though the data that join_is_removable consults is now
166 : : * slightly out of date. Removing a join can only delete attr_needed
167 : : * bits and join clauses, and any attr_needed bit or join clause that
168 : : * mentions the removed rel above its own join level would have
169 : : * prevented that rel from being removable. So what remains to be
170 : : * examined is unchanged by what we just did.
171 : : *
172 : : * The converse doesn't hold: dropping a join can make some other join
173 : : * removable that didn't look so before. That's why our caller loops
174 : : * until we report finding nothing more to remove.
175 : : */
176 : : }
177 : :
178 [ + + ]: 254004 : if (bms_is_empty(removed_relids))
179 : 245927 : return false;
180 : :
181 : : /* Clean up the traces that the removed rels have left elsewhere */
182 : 8077 : remove_rels_from_query_tree(root, removed_relids);
183 : :
184 : 8077 : return true;
185 : : }
186 : :
187 : : /*
188 : : * join_is_removable
189 : : * Check whether we need not perform this special join at all, because
190 : : * it will just duplicate its left input.
191 : : *
192 : : * This is true for a left join for which the join condition cannot match
193 : : * more than one inner-side row. (There are other possibly interesting
194 : : * cases, but we don't have the infrastructure to prove them.) We also
195 : : * have to check that the inner side doesn't generate any variables needed
196 : : * above the join.
197 : : */
198 : : static bool
6042 199 : 49097 : join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
200 : : {
201 : : int innerrelid;
202 : : RelOptInfo *innerrel;
203 : : Relids inputrelids;
204 : : Relids joinrelids;
205 : 49097 : List *clause_list = NIL;
206 : : ListCell *l;
207 : : int attroff;
208 : :
209 : : /*
210 : : * Must be a left join to a single baserel, else we aren't going to be
211 : : * able to do anything with it.
212 : : */
1351 213 [ + + ]: 49097 : if (sjinfo->jointype != JOIN_LEFT)
4336 214 : 13616 : return false;
215 : :
216 : : /*
217 : : * We test the syntactic righthand side, not min_righthand, because the
218 : : * removal is done by deleting the whole righthand subtree of the join.
219 : : * (min_righthand can be a singleton when syn_righthand is not, but in
220 : : * such a case the attr_needed tests below would reject the join anyway.)
221 : : */
45 222 [ + + ]: 35481 : if (!bms_get_singleton_member(sjinfo->syn_righthand, &innerrelid))
6042 223 : 1633 : return false;
45 224 [ - + ]: 33848 : Assert(bms_equal(sjinfo->min_righthand, sjinfo->syn_righthand));
225 : :
226 : : /*
227 : : * Never try to eliminate a left join to the query result rel. Although
228 : : * the case is syntactically impossible in standard SQL, MERGE will build
229 : : * a join tree that looks exactly like that.
230 : : */
1330 231 [ + + ]: 33848 : if (innerrelid == root->parse->resultRelation)
232 : 636 : return false;
233 : :
6042 234 : 33212 : innerrel = find_base_rel(root, innerrelid);
235 : :
236 : : /*
237 : : * Before we go to the effort of checking whether any innerrel variables
238 : : * are needed above the join, make a quick check to eliminate cases in
239 : : * which we will surely be unable to prove uniqueness of the innerrel.
240 : : */
3840 241 [ + + ]: 33212 : if (!rel_supports_distinctness(root, innerrel))
242 : 2710 : return false;
243 : :
244 : : /* Compute the relid set for the join we are considering */
1242 245 : 30502 : inputrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
1346 246 [ - + ]: 30502 : Assert(sjinfo->ojrelid != 0);
247 : 30502 : joinrelids = bms_copy(inputrelids);
248 : 30502 : joinrelids = bms_add_member(joinrelids, sjinfo->ojrelid);
249 : :
250 : : /*
251 : : * We can't remove the join if any inner-rel attributes are used above the
252 : : * join. Here, "above" the join includes pushed-down conditions, so we
253 : : * should reject if attr_needed includes the OJ's own relid; therefore,
254 : : * compare to inputrelids not joinrelids.
255 : : *
256 : : * As a micro-optimization, it seems better to start with max_attr and
257 : : * count down rather than starting with min_attr and counting up, on the
258 : : * theory that the system attributes are somewhat less likely to be wanted
259 : : * and should be tested last.
260 : : */
6042 261 : 30502 : for (attroff = innerrel->max_attr - innerrel->min_attr;
262 [ + + ]: 279741 : attroff >= 0;
263 : 249239 : attroff--)
264 : : {
1346 265 [ + + ]: 270642 : if (!bms_is_subset(innerrel->attr_needed[attroff], inputrelids))
6042 266 : 21403 : return false;
267 : : }
268 : :
269 : : /*
270 : : * Similarly check that the inner rel isn't needed by any PlaceHolderVars
271 : : * that will be used above the join. The PHV case is a little bit more
272 : : * complicated, because PHVs may have been assigned a ph_eval_at location
273 : : * that includes the innerrel, yet their contained expression might not
274 : : * actually reference the innerrel (it could be just a constant, for
275 : : * instance). If such a PHV is due to be evaluated above the join then it
276 : : * needn't prevent join removal.
277 : : */
278 [ + + + + : 9320 : foreach(l, root->placeholder_list)
+ + ]
279 : : {
280 : 251 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
281 : :
4804 282 [ - + ]: 251 : if (bms_overlap(phinfo->ph_lateral, innerrel->relids))
283 : 30 : return false; /* it references innerrel laterally */
5861 284 [ + + ]: 251 : if (!bms_overlap(phinfo->ph_eval_at, innerrel->relids))
285 : 91 : continue; /* it definitely doesn't reference innerrel */
1344 286 [ - + ]: 160 : if (bms_is_subset(phinfo->ph_needed, inputrelids))
1344 tgl@sss.pgh.pa.us 287 :UBC 0 : continue; /* PHV is not used above the join */
1344 tgl@sss.pgh.pa.us 288 [ + + ]:CBC 160 : if (!bms_is_member(sjinfo->ojrelid, phinfo->ph_eval_at))
289 : 25 : return false; /* it has to be evaluated below the join */
290 : :
291 : : /*
292 : : * We need to be sure there will still be a place to evaluate the PHV
293 : : * if we remove the join, ie that ph_eval_at wouldn't become empty.
294 : : */
295 [ + + ]: 135 : if (!bms_overlap(sjinfo->min_lefthand, phinfo->ph_eval_at))
4804 296 : 5 : return false; /* there isn't any other place to eval PHV */
297 : : /* Check contained expression last, since this is a bit expensive */
2090 298 [ - + ]: 130 : if (bms_overlap(pull_varnos(root, (Node *) phinfo->ph_var->phexpr),
5861 299 : 130 : innerrel->relids))
1344 tgl@sss.pgh.pa.us 300 :UBC 0 : return false; /* contained expression references innerrel */
301 : : }
302 : :
303 : : /*
304 : : * Search for mergejoinable clauses that constrain the inner rel against
305 : : * either the outer rel or a pseudoconstant. If an operator is
306 : : * mergejoinable then it behaves like equality for some btree opclass, so
307 : : * it's what we want. The mergejoinability test also eliminates clauses
308 : : * containing volatile functions, which we couldn't depend on.
309 : : */
6042 tgl@sss.pgh.pa.us 310 [ + + + + :CBC 18317 : foreach(l, innerrel->joininfo)
+ + ]
311 : : {
312 : 9248 : RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
313 : :
314 : : /*
315 : : * If the current join commutes with some other outer join(s) via
316 : : * outer join identity 3, there will be multiple clones of its join
317 : : * clauses in the joininfo list. We want to consider only the
318 : : * has_clone form of such clauses. Processing more than one form
319 : : * would be wasteful, and also some of the others would confuse the
320 : : * RINFO_IS_PUSHED_DOWN test below.
321 : : */
1351 322 [ + + ]: 9248 : if (restrictinfo->is_clone)
323 : 87 : continue; /* ignore it */
324 : :
325 : : /*
326 : : * If it's not a join clause for this outer join, we can't use it.
327 : : * Note that if the clause is pushed-down, then it is logically from
328 : : * above the outer join, even if it references no other rels (it might
329 : : * be from WHERE, for example).
330 : : */
3097 331 [ + + + + ]: 9161 : if (RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
1346 332 : 125 : continue; /* ignore; not useful here */
333 : :
334 : : /* Ignore if it's not a mergejoinable clause */
6042 335 [ + + ]: 9036 : if (!restrictinfo->can_join ||
336 [ - + ]: 8872 : restrictinfo->mergeopfamilies == NIL)
337 : 164 : continue; /* not mergejoinable */
338 : :
339 : : /*
340 : : * Check if the clause has the form "outer op inner" or "inner op
341 : : * outer", and if so mark which side is inner.
342 : : */
343 [ + + ]: 8872 : if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand,
344 : : innerrel->relids))
345 : 5 : continue; /* no good for these input relations */
346 : :
347 : : /* OK, add to list */
348 : 8867 : clause_list = lappend(clause_list, restrictinfo);
349 : : }
350 : :
351 : : /*
352 : : * Now that we have the relevant equality join clauses, try to prove the
353 : : * innerrel distinct.
354 : : */
606 akorotkov@postgresql 355 [ + + ]: 9069 : if (rel_is_distinct_for(root, innerrel, clause_list, NULL))
3840 tgl@sss.pgh.pa.us 356 : 8800 : return true;
357 : :
358 : : /*
359 : : * Some day it would be nice to check for other methods of establishing
360 : : * distinctness.
361 : : */
6042 362 : 269 : return false;
363 : : }
364 : :
365 : : /*
366 : : * remove_join_from_jointree
367 : : * Delete the JoinExpr with the given RT index, along with everything
368 : : * below its righthand side, from the query's jointree.
369 : : *
370 : : * The JoinExpr is replaced by its lefthand input. Its ON conditions can just
371 : : * be dropped: since this is a left join, they could only have determined
372 : : * which righthand rows join to a given lefthand row, and there are no
373 : : * righthand rows anymore.
374 : : *
375 : : * *nremoved is incremented by the number of JoinExprs removed (there should
376 : : * be exactly one, but the caller checks that).
377 : : */
378 : : static Node *
45 379 : 27890 : remove_join_from_jointree(Node *jtnode, int ojrelid, int *nremoved)
380 : : {
381 [ - + ]: 27890 : if (jtnode == NULL)
45 tgl@sss.pgh.pa.us 382 :UBC 0 : return NULL;
45 tgl@sss.pgh.pa.us 383 [ + + ]:CBC 27890 : if (IsA(jtnode, RangeTblRef))
384 : : {
385 : : /* nothing to do here */
386 : : }
387 [ + + ]: 22609 : else if (IsA(jtnode, FromExpr))
388 : : {
389 : 8830 : FromExpr *f = (FromExpr *) jtnode;
390 : : ListCell *l;
391 : :
392 [ + - + + : 17962 : foreach(l, f->fromlist)
+ + ]
393 : 9132 : lfirst(l) = remove_join_from_jointree((Node *) lfirst(l),
394 : : ojrelid, nremoved);
395 : : }
396 [ + - ]: 13779 : else if (IsA(jtnode, JoinExpr))
397 : : {
398 : 13779 : JoinExpr *j = (JoinExpr *) jtnode;
399 : :
400 [ + + ]: 13779 : if (j->rtindex == ojrelid)
401 : : {
402 : 8800 : (*nremoved)++;
403 : 8800 : return j->larg;
404 : : }
405 : 4979 : j->larg = remove_join_from_jointree(j->larg, ojrelid, nremoved);
406 : 4979 : j->rarg = remove_join_from_jointree(j->rarg, ojrelid, nremoved);
407 : : }
408 : : else
45 tgl@sss.pgh.pa.us 409 [ # # ]:UBC 0 : elog(ERROR, "unrecognized jointree node type: %d",
410 : : (int) nodeTag(jtnode));
411 : :
45 tgl@sss.pgh.pa.us 412 :CBC 19090 : return jtnode;
413 : : }
414 : :
415 : : /*
416 : : * remove_rels_from_query_tree
417 : : * Delete all remaining references to the given relids from the query.
418 : : *
419 : : * Having removed some relations and outer joins from the jointree, we must
420 : : * get rid of any references to them that are left behind elsewhere. There
421 : : * should be no ordinary Vars of a removed relation left, but OJ relids can
422 : : * still appear in the nullingrels sets of surviving Vars and PlaceHolderVars,
423 : : * and both regular and OJ relids can appear in the phrels sets of
424 : : * PlaceHolderVars. ChangeVarNodes knows how to strip a relid out of all of
425 : : * those.
426 : : */
427 : : static void
428 : 8077 : remove_rels_from_query_tree(PlannerInfo *root, Relids removed_relids)
429 : : {
430 : 8077 : int relid = -1;
431 : :
432 [ + + ]: 25677 : while ((relid = bms_next_member(removed_relids, relid)) >= 0)
433 : : {
434 : 17600 : ChangeVarNodes((Node *) root->parse, relid, INVALID_VAR, 0);
435 : :
436 : : /*
437 : : * processed_tlist shares some but not all of its nodes with
438 : : * parse->targetList, so it has to be processed separately. (That's
439 : : * harmless: ChangeVarNodes works in-place, and removing a relid that
440 : : * isn't there is idempotent.)
441 : : */
442 : 17600 : ChangeVarNodes((Node *) root->processed_tlist, relid, INVALID_VAR, 0);
443 : :
444 : : /* There could be references in the append_rel_list, too */
445 [ + + ]: 17600 : if (root->append_rel_list != NIL)
446 : 20 : ChangeVarNodes((Node *) root->append_rel_list, relid, INVALID_VAR, 0);
447 : : }
112 rguo@postgresql.org 448 : 8077 : }
449 : :
450 : : /*
451 : : * reduce_unique_semijoins
452 : : * Check for semijoins that can be simplified to plain inner joins
453 : : * because the inner relation is provably unique for the join clauses.
454 : : *
455 : : * Ideally this would happen during reduce_outer_joins, but we don't have
456 : : * enough information at that point.
457 : : *
458 : : * Like the join removal cases, we do this on the query's jointree, so
459 : : * returning true means the caller must recompute the derived data.
460 : : */
461 : : bool
3451 tgl@sss.pgh.pa.us 462 : 245927 : reduce_unique_semijoins(PlannerInfo *root)
463 : : {
45 464 : 245927 : bool changed = false;
465 : : ListCell *lc;
466 : :
467 : : /*
468 : : * Scan the join_info_list to find semijoins.
469 : : */
2646 470 [ + + + + : 283345 : foreach(lc, root->join_info_list)
+ + ]
471 : : {
3451 472 : 37418 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
473 : : int innerrelid;
474 : : RelOptInfo *innerrel;
475 : : Relids joinrelids;
476 : : List *restrictlist;
477 : :
478 : : /*
479 : : * Must be a semijoin to a single baserel, else we aren't going to be
480 : : * able to do anything with it.
481 : : */
1351 482 [ + + ]: 37418 : if (sjinfo->jointype != JOIN_SEMI)
3451 483 : 37174 : continue;
484 : :
485 : : /*
486 : : * We test the syntactic righthand side, since that's what identifies
487 : : * the JoinExpr we'll modify.
488 : : */
45 489 [ + + ]: 4109 : if (!bms_get_singleton_member(sjinfo->syn_righthand, &innerrelid))
3451 490 : 140 : continue;
45 491 [ - + ]: 3969 : Assert(bms_equal(sjinfo->min_righthand, sjinfo->syn_righthand));
492 : :
3451 493 : 3969 : innerrel = find_base_rel(root, innerrelid);
494 : :
495 : : /*
496 : : * Before we trouble to run generate_join_implied_equalities, make a
497 : : * quick check to eliminate cases in which we will surely be unable to
498 : : * prove uniqueness of the innerrel.
499 : : */
500 [ + + ]: 3969 : if (!rel_supports_distinctness(root, innerrel))
501 : 876 : continue;
502 : :
503 : : /* Compute the relid set for the join we are considering */
504 : 3093 : joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
1351 505 [ - + ]: 3093 : Assert(sjinfo->ojrelid == 0); /* SEMI joins don't have RT indexes */
506 : :
507 : : /*
508 : : * Since we're only considering a single-rel RHS, any join clauses it
509 : : * has must be clauses linking it to the semijoin's min_lefthand. We
510 : : * can also consider EC-derived join clauses.
511 : : */
512 : : restrictlist =
3451 513 : 3093 : list_concat(generate_join_implied_equalities(root,
514 : : joinrelids,
515 : : sjinfo->min_lefthand,
516 : : innerrel,
517 : : NULL),
518 : 3093 : innerrel->joininfo);
519 : :
520 : : /* Test whether the innerrel is unique for those clauses. */
45 521 [ + + ]: 3093 : if (!innerrel_is_unique(root,
522 : : joinrelids, sjinfo->min_lefthand, innerrel,
523 : : JOIN_SEMI, restrictlist, true))
524 : 2849 : continue;
525 : :
526 : : /* OK, reduce the join to a plain inner join in the jointree. */
527 [ - + ]: 244 : if (!reduce_semijoin_in_jointree((Node *) root->parse->jointree,
528 : : sjinfo->syn_righthand))
45 tgl@sss.pgh.pa.us 529 [ # # ]:UBC 0 : elog(ERROR, "failed to find semijoin in jointree");
45 tgl@sss.pgh.pa.us 530 :CBC 244 : changed = true;
531 : : }
532 : :
533 : 245927 : return changed;
534 : : }
535 : :
536 : : /*
537 : : * reduce_semijoin_in_jointree
538 : : * Find the JoinExpr for the semijoin with the given syntactic righthand
539 : : * side, and turn it into an inner join.
540 : : *
541 : : * Semijoins have no RT index of their own, so we have to identify the one
542 : : * we want by the set of relids on its righthand side.
543 : : */
544 : : static bool
545 : 559 : reduce_semijoin_in_jointree(Node *jtnode, Relids syn_righthand)
546 : : {
547 [ - + ]: 559 : if (jtnode == NULL)
45 tgl@sss.pgh.pa.us 548 :UBC 0 : return false;
45 tgl@sss.pgh.pa.us 549 [ + + ]:CBC 559 : if (IsA(jtnode, RangeTblRef))
550 : : {
551 : : /* nothing to do here */
552 : : }
553 [ + + ]: 534 : else if (IsA(jtnode, FromExpr))
554 : : {
555 : 251 : FromExpr *f = (FromExpr *) jtnode;
556 : : ListCell *l;
557 : :
558 [ + - + - : 251 : foreach(l, f->fromlist)
+ - ]
559 : : {
560 [ + - ]: 251 : if (reduce_semijoin_in_jointree((Node *) lfirst(l), syn_righthand))
561 : 251 : return true;
562 : : }
563 : : }
564 [ + - ]: 283 : else if (IsA(jtnode, JoinExpr))
565 : : {
566 : 283 : JoinExpr *j = (JoinExpr *) jtnode;
567 : :
568 [ + + + + ]: 541 : if (j->jointype == JOIN_SEMI &&
569 : 258 : bms_equal(get_relids_in_jointree(j->rarg, true, false),
570 : : syn_righthand))
571 : : {
572 : 244 : j->jointype = JOIN_INNER;
573 : 244 : return true;
574 : : }
575 [ + + ]: 39 : if (reduce_semijoin_in_jointree(j->larg, syn_righthand))
576 : 14 : return true;
577 [ + - ]: 25 : if (reduce_semijoin_in_jointree(j->rarg, syn_righthand))
578 : 25 : return true;
579 : : }
580 : : else
45 tgl@sss.pgh.pa.us 581 [ # # ]:UBC 0 : elog(ERROR, "unrecognized jointree node type: %d",
582 : : (int) nodeTag(jtnode));
583 : :
45 tgl@sss.pgh.pa.us 584 :CBC 25 : return false;
585 : : }
586 : :
587 : :
588 : : /*
589 : : * rel_supports_distinctness
590 : : * Could the relation possibly be proven distinct on some set of columns?
591 : : *
592 : : * This is effectively a pre-checking function for rel_is_distinct_for().
593 : : * It must return true if rel_is_distinct_for() could possibly return true
594 : : * with this rel, but it should not expend a lot of cycles. The idea is
595 : : * that callers can avoid doing possibly-expensive processing to compute
596 : : * rel_is_distinct_for()'s argument lists if the call could not possibly
597 : : * succeed.
598 : : */
599 : : static bool
3840 600 : 541200 : rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
601 : : {
602 : : /* We only know about baserels ... */
603 [ + + ]: 541200 : if (rel->reloptkind != RELOPT_BASEREL)
604 : 197311 : return false;
605 [ + + ]: 343889 : if (rel->rtekind == RTE_RELATION)
606 : : {
607 : : /*
608 : : * For a plain relation, we only know how to prove uniqueness by
609 : : * reference to unique indexes. Make sure there's at least one
610 : : * suitable unique index. It must be immediately enforced, and not a
611 : : * partial index. (Keep these conditions in sync with
612 : : * relation_has_unique_index_for!)
613 : : */
614 : : ListCell *lc;
615 : :
616 [ + + + + : 427630 : foreach(lc, rel->indexlist)
+ + ]
617 : : {
618 : 377205 : IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);
619 : :
1211 drowley@postgresql.o 620 [ + + + - : 377205 : if (ind->unique && ind->immediate && ind->indpred == NIL)
+ + ]
3840 tgl@sss.pgh.pa.us 621 : 266665 : return true;
622 : : }
623 : : }
624 [ + + ]: 26799 : else if (rel->rtekind == RTE_SUBQUERY)
625 : : {
626 : 10046 : Query *subquery = root->simple_rte_array[rel->relid]->subquery;
627 : :
628 : : /* Check if the subquery has any qualities that support distinctness */
629 [ + + ]: 10046 : if (query_supports_distinctness(subquery))
630 : 8625 : return true;
631 : : }
632 : : /* We have no proof rules for any other rtekinds. */
633 : 68599 : return false;
634 : : }
635 : :
636 : : /*
637 : : * rel_is_distinct_for
638 : : * Does the relation return only distinct rows according to clause_list?
639 : : *
640 : : * clause_list is a list of join restriction clauses involving this rel and
641 : : * some other one. Return true if no two rows emitted by this rel could
642 : : * possibly join to the same row of the other rel.
643 : : *
644 : : * The caller must have already determined that each condition is a
645 : : * mergejoinable equality with an expression in this relation on one side, and
646 : : * an expression not involving this relation on the other. The transient
647 : : * outer_is_left flag is used to identify which side references this relation:
648 : : * left side if outer_is_left is false, right side if it is true.
649 : : *
650 : : * Note that the passed-in clause_list may be destructively modified! This
651 : : * is OK for current uses, because the clause_list is built by the caller for
652 : : * the sole purpose of passing to this function.
653 : : *
654 : : * (*extra_clauses) to be set to the right sides of baserestrictinfo clauses,
655 : : * looking like "x = const" if distinctness is derived from such clauses, not
656 : : * joininfo clauses. Pass NULL to the extra_clauses if this value is not
657 : : * needed.
658 : : */
659 : : static bool
606 akorotkov@postgresql 660 : 178122 : rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list,
661 : : List **extra_clauses)
662 : : {
663 : : /*
664 : : * We could skip a couple of tests here if we assume all callers checked
665 : : * rel_supports_distinctness first, but it doesn't seem worth taking any
666 : : * risk for.
667 : : */
3840 tgl@sss.pgh.pa.us 668 [ - + ]: 178122 : if (rel->reloptkind != RELOPT_BASEREL)
3840 tgl@sss.pgh.pa.us 669 :UBC 0 : return false;
3840 tgl@sss.pgh.pa.us 670 [ + + ]:CBC 178122 : if (rel->rtekind == RTE_RELATION)
671 : : {
672 : : /*
673 : : * Examine the indexes to see if we have a matching unique index.
674 : : * relation_has_unique_index_for automatically adds any usable
675 : : * restriction clauses for the rel, so we needn't do that here.
676 : : */
419 rguo@postgresql.org 677 [ + + ]: 173634 : if (relation_has_unique_index_for(root, rel, clause_list, extra_clauses))
3840 tgl@sss.pgh.pa.us 678 : 105241 : return true;
679 : : }
680 [ + - ]: 4488 : else if (rel->rtekind == RTE_SUBQUERY)
681 : : {
682 : 4488 : Index relid = rel->relid;
683 : 4488 : Query *subquery = root->simple_rte_array[relid]->subquery;
160 rguo@postgresql.org 684 : 4488 : List *distinct_cols = NIL;
685 : : ListCell *l;
686 : :
687 : : /*
688 : : * Build the argument list for query_is_distinct_for: a list of
689 : : * DistinctColInfo entries, each holding an output column number that
690 : : * the query needs to be distinct over, the equality operator that the
691 : : * column needs to be distinct according to, and that operator's input
692 : : * collation. The collation matters because the subquery's own
693 : : * DISTINCT / GROUP BY / set-op proves uniqueness under its own
694 : : * collation, which need not agree with the operator's.
695 : : *
696 : : * (XXX we are not considering restriction clauses attached to the
697 : : * subquery; is that worth doing?)
698 : : */
3840 tgl@sss.pgh.pa.us 699 [ + + + + : 8601 : foreach(l, clause_list)
+ + ]
700 : : {
3472 701 : 4113 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
702 : : OpExpr *opexpr;
703 : : Var *var;
704 : : DistinctColInfo *dcinfo;
705 : :
706 : : /*
707 : : * The caller's mergejoinability test should have selected only
708 : : * OpExprs. The operator might be a cross-type operator and thus
709 : : * not exactly the same operator the subquery would consider;
710 : : * that's all right since query_is_distinct_for can resolve such
711 : : * cases.
712 : : */
160 rguo@postgresql.org 713 : 4113 : opexpr = castNode(OpExpr, rinfo->clause);
714 : :
715 : : /* caller identified the inner side for us */
3840 tgl@sss.pgh.pa.us 716 [ + + ]: 4113 : if (rinfo->outer_is_left)
717 : 3762 : var = (Var *) get_rightop(rinfo->clause);
718 : : else
719 : 351 : var = (Var *) get_leftop(rinfo->clause);
720 : :
721 : : /*
722 : : * We may ignore any RelabelType node above the operand. (There
723 : : * won't be more than one, since eval_const_expressions() has been
724 : : * applied already.)
725 : : */
3312 726 [ + - + + ]: 4113 : if (var && IsA(var, RelabelType))
727 : 2718 : var = (Var *) ((RelabelType *) var)->arg;
728 : :
729 : : /*
730 : : * If inner side isn't a Var referencing a subquery output column,
731 : : * this clause doesn't help us.
732 : : */
3840 733 [ + - + + ]: 4113 : if (!var || !IsA(var, Var) ||
734 [ + - - + ]: 4103 : var->varno != relid || var->varlevelsup != 0)
735 : 10 : continue;
736 : :
56 michael@paquier.xyz 737 :GNC 4103 : dcinfo = palloc_object(DistinctColInfo);
160 rguo@postgresql.org 738 :CBC 4103 : dcinfo->colno = var->varattno;
739 : 4103 : dcinfo->opid = opexpr->opno;
740 : 4103 : dcinfo->collid = opexpr->inputcollid;
741 : 4103 : distinct_cols = lappend(distinct_cols, dcinfo);
742 : : }
743 : :
744 [ + + ]: 4488 : if (query_is_distinct_for(subquery, distinct_cols))
3840 tgl@sss.pgh.pa.us 745 : 654 : return true;
746 : : }
747 : 72227 : return false;
748 : : }
749 : :
750 : :
751 : : /*
752 : : * query_supports_distinctness - could the query possibly be proven distinct
753 : : * on some set of output columns?
754 : : *
755 : : * This is effectively a pre-checking function for query_is_distinct_for().
756 : : * It must return true if query_is_distinct_for() could possibly return true
757 : : * with this query, but it should not expend a lot of cycles. The idea is
758 : : * that callers can avoid doing possibly-expensive processing to compute
759 : : * query_is_distinct_for()'s argument lists if the call could not possibly
760 : : * succeed.
761 : : */
762 : : bool
4472 763 : 10046 : query_supports_distinctness(Query *query)
764 : : {
765 : : /* SRFs break distinctness except with plain DISTINCT, see below */
48 rguo@postgresql.org 766 [ + + ]: 10046 : if (query->hasTargetSRFs &&
767 [ + + + - ]: 766 : (query->distinctClause == NIL || query->hasDistinctOn))
3681 tgl@sss.pgh.pa.us 768 : 766 : return false;
769 : :
770 : : /* check for features we can prove distinctness with */
4472 771 [ + + ]: 9280 : if (query->distinctClause != NIL ||
772 [ + + ]: 9095 : query->groupClause != NIL ||
4167 andres@anarazel.de 773 [ + + ]: 8909 : query->groupingSets != NIL ||
4472 tgl@sss.pgh.pa.us 774 [ + + ]: 8869 : query->hasAggs ||
775 [ + - ]: 7161 : query->havingQual ||
776 [ + + ]: 7161 : query->setOperations)
777 : 8625 : return true;
778 : :
779 : 655 : return false;
780 : : }
781 : :
782 : : /*
783 : : * query_is_distinct_for - does query never return duplicates of the
784 : : * specified columns?
785 : : *
786 : : * query is a not-yet-planned subquery (in current usage, it's always from
787 : : * a subquery RTE, which the planner avoids scribbling on).
788 : : *
789 : : * distinct_cols is a list of DistinctColInfo, one per requested output column.
790 : : * Each entry names the subquery output column number we want distinct, the
791 : : * upper-level equality operator we'll compare values with, and that operator's
792 : : * input collation. We are interested in whether rows consisting of just these
793 : : * columns are certain to be distinct.
794 : : *
795 : : * "Distinctness" is defined according to whether the corresponding upper-level
796 : : * equality operators would think the values are distinct. (Note: each opid
797 : : * could be a cross-type operator, and thus not exactly the equality operator
798 : : * that the subquery would use itself. We use equality_ops_are_compatible() to
799 : : * check compatibility. That looks at opfamily membership for index AMs that
800 : : * have declared that they support consistent equality semantics within an
801 : : * opfamily, and so should give trustworthy answers for all operators that we
802 : : * might need to deal with here.)
803 : : *
804 : : * The collid must also agree on equality with the collation the subquery's own
805 : : * DISTINCT/GROUP BY/set-op uses to deduplicate the column, else the subquery's
806 : : * distinctness does not carry over to the caller's equality semantics. Two
807 : : * collations agree on equality if they match or if both are deterministic (in
808 : : * which case both reduce equality to byte-equality; see CREATE COLLATION).
809 : : */
810 : : bool
160 rguo@postgresql.org 811 : 4488 : query_is_distinct_for(Query *query, List *distinct_cols)
812 : : {
813 : : ListCell *l;
814 : : DistinctColInfo *dcinfo;
815 : :
816 : : /*
817 : : * DISTINCT (including DISTINCT ON) guarantees uniqueness if all the
818 : : * columns in the DISTINCT clause appear in colnos and operator semantics
819 : : * match. With plain DISTINCT this is true even if there are SRFs in the
820 : : * tlist, since they are all DISTINCT columns and hence get expanded
821 : : * before the Unique step. But with DISTINCT ON, the planner may postpone
822 : : * SRFs that are not DISTINCT ON or ORDER BY columns until after the
823 : : * Unique step, which can produce duplicates of the DISTINCT ON columns;
824 : : * so we can't rely on DISTINCT ON if there are any tlist SRFs.
825 : : */
48 826 [ + + ]: 4488 : if (query->distinctClause &&
827 [ - + - - ]: 155 : !(query->hasTargetSRFs && query->hasDistinctOn))
828 : : {
4472 tgl@sss.pgh.pa.us 829 [ + - + + : 220 : foreach(l, query->distinctClause)
+ + ]
830 : : {
831 : 170 : SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
832 : 170 : TargetEntry *tle = get_sortgroupclause_tle(sgc,
833 : : query->targetList);
834 : :
160 rguo@postgresql.org 835 : 170 : dcinfo = distinct_col_search(tle->resno, distinct_cols);
836 [ + + ]: 170 : if (dcinfo == NULL ||
837 [ + - ]: 105 : !equality_ops_are_compatible(dcinfo->opid, sgc->eqop) ||
838 [ + + ]: 105 : !collations_agree_on_equality(dcinfo->collid,
839 : 105 : exprCollation((Node *) tle->expr)))
840 : : break; /* exit early if no match */
841 : : }
4472 tgl@sss.pgh.pa.us 842 [ + + ]: 155 : if (l == NULL) /* had matches for all? */
843 : 50 : return true;
844 : : }
845 : :
846 : : /*
847 : : * Otherwise, a set-returning function in the query's targetlist can
848 : : * result in returning duplicate rows, despite any grouping that might
849 : : * occur before tlist evaluation. (If all tlist SRFs are within GROUP BY
850 : : * columns, it would be safe because they'd be expanded before grouping.
851 : : * But it doesn't currently seem worth the effort to check for that.)
852 : : */
3243 853 [ - + ]: 4438 : if (query->hasTargetSRFs)
3243 tgl@sss.pgh.pa.us 854 :UBC 0 : return false;
855 : :
856 : : /*
857 : : * Similarly, GROUP BY without GROUPING SETS guarantees uniqueness if all
858 : : * the grouped columns appear in colnos and operator semantics match.
859 : : */
4167 andres@anarazel.de 860 [ + + + + ]:CBC 4438 : if (query->groupClause && !query->groupingSets)
861 : : {
4472 tgl@sss.pgh.pa.us 862 [ + - + + : 226 : foreach(l, query->groupClause)
+ + ]
863 : : {
864 : 159 : SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
865 : 159 : TargetEntry *tle = get_sortgroupclause_tle(sgc,
866 : : query->targetList);
867 : :
160 rguo@postgresql.org 868 : 159 : dcinfo = distinct_col_search(tle->resno, distinct_cols);
869 [ + + ]: 159 : if (dcinfo == NULL ||
870 [ + - ]: 112 : !equality_ops_are_compatible(dcinfo->opid, sgc->eqop) ||
871 [ + + ]: 112 : !collations_agree_on_equality(dcinfo->collid,
872 : 112 : exprCollation((Node *) tle->expr)))
873 : : break; /* exit early if no match */
874 : : }
4472 tgl@sss.pgh.pa.us 875 [ + + ]: 124 : if (l == NULL) /* had matches for all? */
876 : 67 : return true;
877 : : }
4167 andres@anarazel.de 878 [ + + ]: 4314 : else if (query->groupingSets)
879 : : {
880 : : List *gsets;
881 : :
882 : : /*
883 : : * If we have grouping sets with expressions, we probably don't have
884 : : * uniqueness and analysis would be hard. Punt.
885 : : */
886 [ + + ]: 50 : if (query->groupClause)
887 : 10 : return false;
888 : :
889 : : /*
890 : : * If we have no groupClause (therefore no grouping expressions), we
891 : : * might have one or many empty grouping sets. If there's just one,
892 : : * or if the DISTINCT clause is used on the GROUP BY, then we're
893 : : * returning only one row and are certainly unique. But otherwise, we
894 : : * know we're certainly not unique.
895 : : */
307 rguo@postgresql.org 896 [ + + ]: 40 : if (query->groupDistinct)
4167 andres@anarazel.de 897 : 5 : return true;
898 : :
307 rguo@postgresql.org 899 : 35 : gsets = expand_grouping_sets(query->groupingSets, false, -1);
900 : :
901 : 35 : return (list_length(gsets) == 1);
902 : : }
903 : : else
904 : : {
905 : : /*
906 : : * If we have no GROUP BY, but do have aggregates or HAVING, then the
907 : : * result is at most one row so it's surely unique, for any operators.
908 : : */
4472 tgl@sss.pgh.pa.us 909 [ + + - + ]: 4264 : if (query->hasAggs || query->havingQual)
910 : 413 : return true;
911 : : }
912 : :
913 : : /*
914 : : * UNION, INTERSECT, EXCEPT guarantee uniqueness of the whole output row,
915 : : * except with ALL.
916 : : */
917 [ + + ]: 3908 : if (query->setOperations)
918 : : {
3520 peter_e@gmx.net 919 : 3746 : SetOperationStmt *topop = castNode(SetOperationStmt, query->setOperations);
920 : :
4472 tgl@sss.pgh.pa.us 921 [ - + ]: 3746 : Assert(topop->op != SETOP_NONE);
922 : :
923 [ + + ]: 3746 : if (!topop->all)
924 : : {
925 : : ListCell *lg;
926 : :
927 : : /* We're good if all the nonjunk output columns are in colnos */
928 : 147 : lg = list_head(topop->groupClauses);
929 [ + - + + : 256 : foreach(l, query->targetList)
+ + ]
930 : : {
931 : 152 : TargetEntry *tle = (TargetEntry *) lfirst(l);
932 : : SortGroupClause *sgc;
933 : :
934 [ - + ]: 152 : if (tle->resjunk)
4472 tgl@sss.pgh.pa.us 935 :UBC 0 : continue; /* ignore resjunk columns */
936 : :
937 : : /* non-resjunk columns should have grouping clauses */
4472 tgl@sss.pgh.pa.us 938 [ - + ]:CBC 152 : Assert(lg != NULL);
939 : 152 : sgc = (SortGroupClause *) lfirst(lg);
2646 940 : 152 : lg = lnext(topop->groupClauses, lg);
941 : :
160 rguo@postgresql.org 942 : 152 : dcinfo = distinct_col_search(tle->resno, distinct_cols);
943 [ + + ]: 152 : if (dcinfo == NULL ||
944 [ + - ]: 119 : !equality_ops_are_compatible(dcinfo->opid, sgc->eqop) ||
945 [ + + ]: 119 : !collations_agree_on_equality(dcinfo->collid,
946 : 119 : exprCollation((Node *) tle->expr)))
947 : : break; /* exit early if no match */
948 : : }
4472 tgl@sss.pgh.pa.us 949 [ + + ]: 147 : if (l == NULL) /* had matches for all? */
950 : 104 : return true;
951 : : }
952 : : }
953 : :
954 : : /*
955 : : * XXX Are there any other cases in which we can easily see the result
956 : : * must be distinct?
957 : : *
958 : : * If you do add more smarts to this function, be sure to update
959 : : * query_supports_distinctness() to match.
960 : : */
961 : :
962 : 3804 : return false;
963 : : }
964 : :
965 : : /*
966 : : * distinct_col_search - subroutine for query_is_distinct_for
967 : : *
968 : : * If colno matches the colno field of an entry in distinct_cols, return a
969 : : * pointer to that entry; else return NULL. (Ordinarily distinct_cols would
970 : : * not contain duplicate colnos, but if it does, we arbitrarily select the
971 : : * first match.)
972 : : */
973 : : static DistinctColInfo *
160 rguo@postgresql.org 974 : 481 : distinct_col_search(int colno, List *distinct_cols)
975 : : {
976 [ + - + + : 789 : foreach_ptr(DistinctColInfo, dcinfo, distinct_cols)
+ + ]
977 : : {
978 [ + + ]: 499 : if (dcinfo->colno == colno)
979 : 336 : return dcinfo;
980 : : }
981 : :
982 : 145 : return NULL;
983 : : }
984 : :
985 : :
986 : : /*
987 : : * innerrel_is_unique
988 : : * Check if the innerrel provably contains at most one tuple matching any
989 : : * tuple from the outerrel, based on join clauses in the 'restrictlist'.
990 : : *
991 : : * We need an actual RelOptInfo for the innerrel, but it's sufficient to
992 : : * identify the outerrel by its Relids. This asymmetry supports use of this
993 : : * function before joinrels have been built. (The caller is expected to
994 : : * also supply the joinrelids, just to save recalculating that.)
995 : : *
996 : : * The proof must be made based only on clauses that will be "joinquals"
997 : : * rather than "otherquals" at execution. For an inner join there's no
998 : : * difference; but if the join is outer, we must ignore pushed-down quals,
999 : : * as those will become "otherquals". Note that this means the answer might
1000 : : * vary depending on whether IS_OUTER_JOIN(jointype); since we cache the
1001 : : * answer without regard to that, callers must take care not to call this
1002 : : * with jointypes that would be classified differently by IS_OUTER_JOIN().
1003 : : *
1004 : : * The actual proof is undertaken by is_innerrel_unique_for(); this function
1005 : : * is a frontend that is mainly concerned with caching the answers.
1006 : : * In particular, the force_cache argument allows overriding the internal
1007 : : * heuristic about whether to cache negative answers; it should be "true"
1008 : : * if making an inquiry that is not part of the normal bottom-up join search
1009 : : * sequence.
1010 : : */
1011 : : bool
3475 tgl@sss.pgh.pa.us 1012 : 586755 : innerrel_is_unique(PlannerInfo *root,
1013 : : Relids joinrelids,
1014 : : Relids outerrelids,
1015 : : RelOptInfo *innerrel,
1016 : : JoinType jointype,
1017 : : List *restrictlist,
1018 : : bool force_cache)
1019 : : {
606 akorotkov@postgresql 1020 : 586755 : return innerrel_is_unique_ext(root, joinrelids, outerrelids, innerrel,
1021 : : jointype, restrictlist, force_cache, NULL);
1022 : : }
1023 : :
1024 : : /*
1025 : : * innerrel_is_unique_ext
1026 : : * Do the same as innerrel_is_unique(), but also set to (*extra_clauses)
1027 : : * additional clauses from a baserestrictinfo list used to prove the
1028 : : * uniqueness.
1029 : : *
1030 : : * A non-NULL extra_clauses indicates that we're checking for self-join and
1031 : : * correspondingly dealing with filtered clauses.
1032 : : */
1033 : : static bool
1034 : 588616 : innerrel_is_unique_ext(PlannerInfo *root,
1035 : : Relids joinrelids,
1036 : : Relids outerrelids,
1037 : : RelOptInfo *innerrel,
1038 : : JoinType jointype,
1039 : : List *restrictlist,
1040 : : bool force_cache,
1041 : : List **extra_clauses)
1042 : : {
1043 : : MemoryContext old_context;
1044 : : ListCell *lc;
1045 : : UniqueRelInfo *uniqueRelInfo;
1046 : 588616 : List *outer_exprs = NIL;
1047 : 588616 : bool self_join = (extra_clauses != NULL);
1048 : :
1049 : : /* Certainly can't prove uniqueness when there are no joinclauses */
3475 tgl@sss.pgh.pa.us 1050 [ + + ]: 588616 : if (restrictlist == NIL)
1051 : 84597 : return false;
1052 : :
1053 : : /*
1054 : : * Make a quick check to eliminate cases in which we will surely be unable
1055 : : * to prove uniqueness of the innerrel.
1056 : : */
1057 [ + + ]: 504019 : if (!rel_supports_distinctness(root, innerrel))
1058 : 262324 : return false;
1059 : :
1060 : : /*
1061 : : * Query the cache to see if we've managed to prove that innerrel is
1062 : : * unique for any subset of this outerrel. For non-self-join search, we
1063 : : * don't need an exact match, as extra outerrels can't make the innerrel
1064 : : * any less unique (or more formally, the restrictlist for a join to a
1065 : : * superset outerrel must be a superset of the conditions we successfully
1066 : : * used before). For self-join search, we require an exact match of
1067 : : * outerrels because we need extra clauses to be valid for our case. Also,
1068 : : * for self-join checking we've filtered the clauses list. Thus, we can
1069 : : * match only the result cached for a self-join search for another
1070 : : * self-join check.
1071 : : */
1072 [ + + + + : 261332 : foreach(lc, innerrel->unique_for_rels)
+ + ]
1073 : : {
606 akorotkov@postgresql 1074 : 91977 : uniqueRelInfo = (UniqueRelInfo *) lfirst(lc);
1075 : :
1076 [ + - + + : 91977 : if ((!self_join && bms_is_subset(uniqueRelInfo->outerrelids, outerrelids)) ||
- + ]
606 akorotkov@postgresql 1077 [ # # ]:UBC 0 : (self_join && bms_equal(uniqueRelInfo->outerrelids, outerrelids) &&
1078 [ # # ]: 0 : uniqueRelInfo->self_join))
1079 : : {
606 akorotkov@postgresql 1080 [ - + ]:CBC 72340 : if (extra_clauses)
606 akorotkov@postgresql 1081 :UBC 0 : *extra_clauses = uniqueRelInfo->extra_clauses;
3475 tgl@sss.pgh.pa.us 1082 :CBC 72340 : return true; /* Success! */
1083 : : }
1084 : : }
1085 : :
1086 : : /*
1087 : : * Conversely, we may have already determined that this outerrel, or some
1088 : : * superset thereof, cannot prove this innerrel to be unique.
1089 : : */
1090 [ + + + + : 169721 : foreach(lc, innerrel->non_unique_for_rels)
+ + ]
1091 : : {
1092 : 668 : Relids unique_for_rels = (Relids) lfirst(lc);
1093 : :
3451 1094 [ + + ]: 668 : if (bms_is_subset(outerrelids, unique_for_rels))
3475 1095 : 302 : return false;
1096 : : }
1097 : :
1098 : : /* No cached information, so try to make the proof. */
3097 1099 [ + + + + ]: 169053 : if (is_innerrel_unique_for(root, joinrelids, outerrelids, innerrel,
1100 : : jointype, restrictlist,
1101 : : self_join ? &outer_exprs : NULL))
1102 : : {
1103 : : /*
1104 : : * Cache the positive result for future probes, being sure to keep it
1105 : : * in the planner_cxt even if we are working in GEQO.
1106 : : *
1107 : : * Note: one might consider trying to isolate the minimal subset of
1108 : : * the outerrels that proved the innerrel unique. But it's not worth
1109 : : * the trouble, because the planner builds up joinrels incrementally
1110 : : * and so we'll see the minimally sufficient outerrels before any
1111 : : * supersets of them anyway.
1112 : : */
3475 1113 : 97095 : old_context = MemoryContextSwitchTo(root->planner_cxt);
606 akorotkov@postgresql 1114 : 97095 : uniqueRelInfo = makeNode(UniqueRelInfo);
1115 : 97095 : uniqueRelInfo->outerrelids = bms_copy(outerrelids);
1116 : 97095 : uniqueRelInfo->self_join = self_join;
1117 : 97095 : uniqueRelInfo->extra_clauses = outer_exprs;
3475 tgl@sss.pgh.pa.us 1118 : 97095 : innerrel->unique_for_rels = lappend(innerrel->unique_for_rels,
1119 : : uniqueRelInfo);
1120 : 97095 : MemoryContextSwitchTo(old_context);
1121 : :
606 akorotkov@postgresql 1122 [ + + ]: 97095 : if (extra_clauses)
1123 : 513 : *extra_clauses = outer_exprs;
3475 tgl@sss.pgh.pa.us 1124 : 97095 : return true; /* Success! */
1125 : : }
1126 : : else
1127 : : {
1128 : : /*
1129 : : * None of the join conditions for outerrel proved innerrel unique, so
1130 : : * we can safely reject this outerrel or any subset of it in future
1131 : : * checks.
1132 : : *
1133 : : * However, in normal planning mode, caching this knowledge is totally
1134 : : * pointless; it won't be queried again, because we build up joinrels
1135 : : * from smaller to larger. It's only useful when using GEQO or
1136 : : * another planner extension that attempts planning multiple times.
1137 : : *
1138 : : * Also, allow callers to override that heuristic and force caching;
1139 : : * that's useful for reduce_unique_semijoins, which calls here before
1140 : : * the normal join search starts.
1141 : : */
418 rhaas@postgresql.org 1142 [ + + - + ]: 71958 : if (force_cache || root->assumeReplanning)
1143 : : {
3475 tgl@sss.pgh.pa.us 1144 : 3146 : old_context = MemoryContextSwitchTo(root->planner_cxt);
1145 : 3146 : innerrel->non_unique_for_rels =
1146 : 3146 : lappend(innerrel->non_unique_for_rels,
3451 1147 : 3146 : bms_copy(outerrelids));
3475 1148 : 3146 : MemoryContextSwitchTo(old_context);
1149 : : }
1150 : :
1151 : 71958 : return false;
1152 : : }
1153 : : }
1154 : :
1155 : : /*
1156 : : * is_innerrel_unique_for
1157 : : * Check if the innerrel provably contains at most one tuple matching any
1158 : : * tuple from the outerrel, based on join clauses in the 'restrictlist'.
1159 : : */
1160 : : static bool
1161 : 169053 : is_innerrel_unique_for(PlannerInfo *root,
1162 : : Relids joinrelids,
1163 : : Relids outerrelids,
1164 : : RelOptInfo *innerrel,
1165 : : JoinType jointype,
1166 : : List *restrictlist,
1167 : : List **extra_clauses)
1168 : : {
1169 : 169053 : List *clause_list = NIL;
1170 : : ListCell *lc;
1171 : :
1172 : : /*
1173 : : * Search for mergejoinable clauses that constrain the inner rel against
1174 : : * the outer rel. If an operator is mergejoinable then it behaves like
1175 : : * equality for some btree opclass, so it's what we want. The
1176 : : * mergejoinability test also eliminates clauses containing volatile
1177 : : * functions, which we couldn't depend on.
1178 : : */
1179 [ + - + + : 379076 : foreach(lc, restrictlist)
+ + ]
1180 : : {
1181 : 210023 : RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
1182 : :
1183 : : /*
1184 : : * As noted above, if it's a pushed-down clause and we're at an outer
1185 : : * join, we can't use it.
1186 : : */
3097 1187 [ + + ]: 210023 : if (IS_OUTER_JOIN(jointype) &&
1188 [ + + - + ]: 86260 : RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
3475 1189 : 7585 : continue;
1190 : :
1191 : : /* Ignore if it's not a mergejoinable clause */
1192 [ + + ]: 202438 : if (!restrictinfo->can_join ||
1193 [ + + ]: 189448 : restrictinfo->mergeopfamilies == NIL)
1194 : 13699 : continue; /* not mergejoinable */
1195 : :
1196 : : /*
1197 : : * Check if the clause has the form "outer op inner" or "inner op
1198 : : * outer", and if so mark which side is inner.
1199 : : */
3451 1200 [ + + ]: 188739 : if (!clause_sides_match_join(restrictinfo, outerrelids,
1201 : : innerrel->relids))
3475 1202 : 20 : continue; /* no good for these input relations */
1203 : :
1204 : : /* OK, add to the list */
1205 : 188719 : clause_list = lappend(clause_list, restrictinfo);
1206 : : }
1207 : :
1208 : : /* Let rel_is_distinct_for() do the hard work */
606 akorotkov@postgresql 1209 : 169053 : return rel_is_distinct_for(root, innerrel, clause_list, extra_clauses);
1210 : : }
1211 : :
1212 : : /*
1213 : : * Remove the toRemove relation after we have proven that it participates only
1214 : : * in an unneeded unique self-join with toKeep.
1215 : : *
1216 : : * The removal is done by deleting the relation's RangeTblRef from the
1217 : : * jointree and then pointing everything that referenced it at the relation we
1218 : : * are keeping. All the conditions that were attached to the removed relation
1219 : : * thereby become conditions on the remaining one, which is what we want:
1220 : : * we've proven that the two relations select the same rows. Note that
1221 : : * this change requires us to hoist those conditions up to someplace
1222 : : * syntactically enclosing toKeep.
1223 : : *
1224 : : * kmark and rmark are the PlanRowMarks (if any) for the kept and removed
1225 : : * relations. We could re-locate those, but the caller already found them.
1226 : : */
1227 : : static void
45 tgl@sss.pgh.pa.us 1228 : 458 : remove_self_join_rel(PlannerInfo *root,
1229 : : RelOptInfo *toKeep, RelOptInfo *toRemove,
1230 : : PlanRowMark *kmark, PlanRowMark *rmark)
1231 : : {
1232 : 458 : Node *orphan_quals = NULL;
1233 : 458 : int nremoved = 0;
1234 : 458 : Node *hoist_quals = NULL;
1235 : 458 : bool found_relid = false;
1236 : :
1237 [ - + ]: 458 : Assert(toKeep->relid > 0);
1238 [ - + ]: 458 : Assert(toRemove->relid > 0);
1239 : :
1240 : : /* We verify that exactly one reference gets removed from the jointree */
1241 : 916 : root->parse->jointree = (FromExpr *)
1242 : 458 : remove_rel_from_jointree((Node *) root->parse->jointree,
1243 : 458 : toRemove->relid,
1244 : : &orphan_quals, &nremoved);
1245 [ - + ]: 458 : if (nremoved != 1)
45 tgl@sss.pgh.pa.us 1246 [ # # ]:UBC 0 : elog(ERROR, "failed to find relation %d in jointree", toRemove->relid);
1247 : : /* The topmost FromExpr can't have gone away, so nothing can be orphaned */
45 tgl@sss.pgh.pa.us 1248 [ - + ]:CBC 458 : Assert(root->parse->jointree != NULL);
1249 [ - + ]: 458 : Assert(orphan_quals == NULL);
1250 : :
1251 : : /*
1252 : : * Replace all references to the removed relation. Note that this must
1253 : : * happen after the jointree surgery, else we'd not be able to tell the
1254 : : * two relations' RangeTblRefs apart.
1255 : : */
1256 : 458 : ChangeVarNodes((Node *) root->parse, toRemove->relid, toKeep->relid, 0);
1257 : :
1258 : : /*
1259 : : * processed_tlist shares some but not all of its nodes with
1260 : : * parse->targetList, so it has to be processed separately. (That's
1261 : : * harmless: ChangeVarNodes works in-place, and the second visit to a
1262 : : * shared node finds nothing to change.)
1263 : : */
1264 : 458 : ChangeVarNodes((Node *) root->processed_tlist, toRemove->relid,
1265 : 458 : toKeep->relid, 0);
1266 : :
1267 : : /* There could be references in the append_rel_list, too */
1268 [ - + ]: 458 : if (root->append_rel_list != NIL)
45 tgl@sss.pgh.pa.us 1269 :UBC 0 : ChangeVarNodes((Node *) root->append_rel_list, toRemove->relid,
1270 : 0 : toKeep->relid, 0);
1271 : :
1272 : : /* Clean up the quals that the substitution has messed with */
45 tgl@sss.pgh.pa.us 1273 :CBC 458 : fixup_selfjoin_jointree(root, (Node *) root->parse->jointree,
1274 : 458 : toKeep->relid,
1275 : : &hoist_quals, &found_relid);
1276 : : /* We shouldn't have any leftover quals, and we must have found toKeep */
1277 [ - + ]: 458 : Assert(hoist_quals == NULL);
1278 [ - + ]: 458 : Assert(found_relid);
1279 : :
1280 : : /*
1281 : : * If the removed relation has a row mark, transfer it to the remaining
1282 : : * one.
1283 : : *
1284 : : * If both rels have row marks, just keep the one corresponding to the
1285 : : * remaining relation because we verified earlier that they have the same
1286 : : * strength.
1287 : : */
1288 [ + + ]: 458 : if (rmark)
1289 : : {
1290 [ + - ]: 36 : if (kmark)
1291 : : {
1292 [ - + ]: 36 : Assert(kmark->markType == rmark->markType);
1293 : :
1294 : 36 : root->rowMarks = list_delete_ptr(root->rowMarks, rmark);
1295 : : }
1296 : : else
1297 : : {
1298 : : /* Shouldn't have inheritance children yet. */
45 tgl@sss.pgh.pa.us 1299 [ # # ]:UBC 0 : Assert(rmark->rti == rmark->prti);
1300 : :
1301 : 0 : rmark->rti = rmark->prti = toKeep->relid;
1302 : : }
1303 : : }
45 tgl@sss.pgh.pa.us 1304 :CBC 458 : }
1305 : :
1306 : : /*
1307 : : * remove_rel_from_jointree
1308 : : * Delete the RangeTblRef for the given relation from the query's
1309 : : * jointree.
1310 : : *
1311 : : * This is used for self-join elimination, where the removed relation's
1312 : : * qual conditions must all be preserved (they will be transposed onto the
1313 : : * remaining relation afterwards). Hence, if dropping the RangeTblRef leaves
1314 : : * a JoinExpr or FromExpr with nothing under it, we can't simply drop that
1315 : : * node; we hand its quals back to the caller in *orphan_quals, to be merged
1316 : : * into the nearest enclosing node that still has some content. That's a
1317 : : * valid transformation only for inner joins, but a jointree node can't become
1318 : : * empty at an outer join here: remove_self_joins_one_group() insists that the
1319 : : * two relations be on the same side of every outer join, so the relation we
1320 : : * are keeping would have to be in the emptied subtree too.
1321 : : *
1322 : : * *nremoved is incremented by the number of RangeTblRefs removed (there
1323 : : * should be exactly one, but the caller checks that).
1324 : : */
1325 : : static Node *
1326 : 2245 : remove_rel_from_jointree(Node *jtnode, int relid,
1327 : : Node **orphan_quals, int *nremoved)
1328 : : {
1329 [ - + ]: 2245 : if (jtnode == NULL)
45 tgl@sss.pgh.pa.us 1330 :UBC 0 : return NULL;
45 tgl@sss.pgh.pa.us 1331 [ + + ]:CBC 2245 : if (IsA(jtnode, RangeTblRef))
1332 : : {
1333 : 1169 : RangeTblRef *rtr = (RangeTblRef *) jtnode;
1334 : :
1335 [ + + ]: 1169 : if (rtr->rtindex == relid)
1336 : : {
1337 : 458 : (*nremoved)++;
1338 : 458 : return NULL;
1339 : : }
1340 : : }
1341 [ + + ]: 1076 : else if (IsA(jtnode, FromExpr))
1342 : : {
1343 : 560 : FromExpr *f = (FromExpr *) jtnode;
1344 : 560 : List *newfromlist = NIL;
1345 : 560 : Node *sub_orphans = NULL;
1346 : : ListCell *l;
1347 : :
1348 [ + - + + : 1315 : foreach(l, f->fromlist)
+ + ]
1349 : : {
1350 : : Node *newchild;
1351 : :
1352 : 755 : newchild = remove_rel_from_jointree((Node *) lfirst(l), relid,
1353 : : &sub_orphans, nremoved);
1354 [ + + ]: 755 : if (newchild != NULL)
1355 : 568 : newfromlist = lappend(newfromlist, newchild);
1356 : : }
1357 : 560 : f->fromlist = newfromlist;
1358 : 560 : f->quals = merge_quals(sub_orphans, f->quals);
1359 [ + + ]: 560 : if (newfromlist == NIL)
1360 : : {
1361 : : /* Nothing left here, so pass our quals up to the parent */
1362 : 32 : *orphan_quals = merge_quals(f->quals, *orphan_quals);
1363 : 32 : return NULL;
1364 : : }
1365 : : }
1366 [ + - ]: 516 : else if (IsA(jtnode, JoinExpr))
1367 : : {
1368 : 516 : JoinExpr *j = (JoinExpr *) jtnode;
1369 : 516 : Node *sub_orphans = NULL;
1370 : :
1371 : 516 : j->larg = remove_rel_from_jointree(j->larg, relid,
1372 : : &sub_orphans, nremoved);
1373 : 516 : j->rarg = remove_rel_from_jointree(j->rarg, relid,
1374 : : &sub_orphans, nremoved);
1375 [ + + + + ]: 516 : if (j->larg == NULL || j->rarg == NULL)
1376 : : {
1377 [ + + ]: 303 : Node *surviving = (j->larg != NULL) ? j->larg : j->rarg;
1378 : 303 : Node *quals = merge_quals(sub_orphans, j->quals);
1379 : :
1380 : : /* As explained above, this can only happen for an inner join */
1381 [ - + ]: 303 : Assert(j->jointype == JOIN_INNER);
1382 : : /* We can't have removed both children */
1383 [ - + ]: 303 : Assert(surviving != NULL);
1384 : :
1385 : : /*
1386 : : * Replace the join by a FromExpr, so that the surviving side's
1387 : : * rows are still filtered by the join's conditions.
1388 : : */
1389 : 303 : return (Node *) makeFromExpr(list_make1(surviving), quals);
1390 : : }
1391 : : /* A subtree that survives never hands any quals back to us */
1392 [ - + ]: 213 : Assert(sub_orphans == NULL);
1393 : : }
1394 : : else
45 tgl@sss.pgh.pa.us 1395 [ # # ]:UBC 0 : elog(ERROR, "unrecognized jointree node type: %d",
1396 : : (int) nodeTag(jtnode));
1397 : :
45 tgl@sss.pgh.pa.us 1398 :CBC 1452 : return jtnode;
1399 : : }
1400 : :
1401 : : /*
1402 : : * merge_quals
1403 : : * Combine two jointree qual conditions.
1404 : : *
1405 : : * quals1 should be the quals from the lower of the two jointree levels,
1406 : : * so that those quals get applied first.
1407 : : *
1408 : : * Jointree quals have been through preprocess_expression() by now, so each
1409 : : * one is either NULL or an implicitly-ANDed List.
1410 : : */
1411 : : static Node *
1412 : 1989 : merge_quals(Node *quals1, Node *quals2)
1413 : : {
1414 [ + + ]: 1989 : if (quals1 == NULL)
1415 : 1919 : return quals2;
1416 [ + + ]: 70 : if (quals2 == NULL)
1417 : 40 : return quals1;
1418 : 30 : return (Node *) list_concat(castNode(List, quals1),
1419 : 30 : castNode(List, quals2));
1420 : : }
1421 : :
1422 : : /*
1423 : : * fixup_selfjoin_jointree
1424 : : * Clean up the query's jointree quals after self-join elimination has
1425 : : * merged one relation into another. (relid is the kept relation.)
1426 : : *
1427 : : * See fixup_selfjoin_quals() for what needs fixing locally to each qual list.
1428 : : * In addition, we need to check quals to see if they refer to relid, and if
1429 : : * so make sure they get hoisted to someplace syntactically above relid.
1430 : : * Do that using a "hoist_quals" in/out parameter similar to "orphan_quals"
1431 : : * in remove_rel_from_jointree. (We can't readily merge these concerns into
1432 : : * a single pass, since remove_rel_from_jointree must run before we relabel
1433 : : * the removed rel's Vars.) In addition, *found_relid is set true if
1434 : : * the subtree rooted at jtnode is found to contain relid's RangeTblRef,
1435 : : * so that we can tell when to stop hoisting quals.
1436 : : * If a qual gets hoisted up, we apply fixup_selfjoin_quals() to it only
1437 : : * after it reaches its final level. This rule improves the odds of
1438 : : * detecting duplicate quals.
1439 : : */
1440 : : static void
1441 : 1755 : fixup_selfjoin_jointree(PlannerInfo *root, Node *jtnode, int relid,
1442 : : Node **hoist_quals, bool *found_relid)
1443 : : {
1444 [ - + ]: 1755 : if (jtnode == NULL)
45 tgl@sss.pgh.pa.us 1445 :UBC 0 : return;
45 tgl@sss.pgh.pa.us 1446 [ + + ]:CBC 1755 : if (IsA(jtnode, RangeTblRef))
1447 : : {
1448 : 711 : RangeTblRef *rtr = (RangeTblRef *) jtnode;
1449 : :
1450 [ + + ]: 711 : if (rtr->rtindex == relid)
1451 : : {
1452 [ - + ]: 458 : Assert(!*found_relid);
1453 : 458 : *found_relid = true;
1454 : : }
1455 : : }
1456 [ + + ]: 1044 : else if (IsA(jtnode, FromExpr))
1457 : : {
1458 : 831 : FromExpr *f = (FromExpr *) jtnode;
1459 : 831 : Node *sub_hoist_quals = NULL;
1460 : 831 : bool sub_found_relid = false;
1461 : : ListCell *l;
1462 : :
1463 [ + - + + : 1702 : foreach(l, f->fromlist)
+ + ]
1464 : 871 : fixup_selfjoin_jointree(root, (Node *) lfirst(l), relid,
1465 : : &sub_hoist_quals, &sub_found_relid);
1466 [ + + ]: 831 : if (sub_found_relid)
1467 : : {
1468 : : /* This FromExpr covers relid, so OK to stop hoisting quals here */
1469 : 796 : f->quals = merge_quals(sub_hoist_quals, f->quals);
1470 [ - + ]: 796 : Assert(!*found_relid);
1471 : 796 : *found_relid = true;
1472 : : }
1473 : : else
1474 : : {
1475 : : /* We might need to hoist some of our own quals too */
1476 : 35 : List *hoistable = NIL;
1477 : 35 : List *keepable = NIL;
1478 : :
1479 [ + + + + : 100 : foreach_ptr(Node, qual, castNode(List, f->quals))
+ + ]
1480 : : {
1481 [ + + ]: 30 : if (bms_is_member(relid, pull_varnos(root, qual)))
1482 : 10 : hoistable = lappend(hoistable, qual);
1483 : : else
1484 : 20 : keepable = lappend(keepable, qual);
1485 : : }
1486 : 35 : f->quals = (Node *) keepable;
1487 : 35 : sub_hoist_quals = merge_quals(sub_hoist_quals, (Node *) hoistable);
1488 : 35 : *hoist_quals = merge_quals(sub_hoist_quals, *hoist_quals);
1489 : : }
1490 : 831 : f->quals = (Node *) fixup_selfjoin_quals(root,
1491 : 831 : castNode(List, f->quals),
1492 : : relid);
1493 : : }
1494 [ + - ]: 213 : else if (IsA(jtnode, JoinExpr))
1495 : : {
1496 : 213 : JoinExpr *j = (JoinExpr *) jtnode;
1497 : 213 : Node *sub_hoist_quals = NULL;
1498 : 213 : bool sub_found_relid = false;
1499 : :
1500 : 213 : fixup_selfjoin_jointree(root, j->larg, relid,
1501 : : &sub_hoist_quals, &sub_found_relid);
1502 : 213 : fixup_selfjoin_jointree(root, j->rarg, relid,
1503 : : &sub_hoist_quals, &sub_found_relid);
1504 [ + + ]: 213 : if (sub_found_relid)
1505 : : {
1506 : : /* This JoinExpr covers relid, so OK to stop hoisting quals here */
1507 : 198 : j->quals = merge_quals(sub_hoist_quals, j->quals);
1508 [ - + ]: 198 : Assert(!*found_relid);
1509 : 198 : *found_relid = true;
1510 : : }
1511 : : else
1512 : : {
1513 : : /* We might need to hoist some of our own quals too */
1514 : 15 : List *hoistable = NIL;
1515 : 15 : List *keepable = NIL;
1516 : :
1517 [ + - + + : 45 : foreach_ptr(Node, qual, castNode(List, j->quals))
+ + ]
1518 : : {
1519 [ + + ]: 15 : if (bms_is_member(relid, pull_varnos(root, qual)))
1520 : 5 : hoistable = lappend(hoistable, qual);
1521 : : else
1522 : 10 : keepable = lappend(keepable, qual);
1523 : : }
1524 : 15 : j->quals = (Node *) keepable;
1525 : 15 : sub_hoist_quals = merge_quals(sub_hoist_quals, (Node *) hoistable);
1526 : : /* We should never need to hoist quals above an outer join */
1527 [ + + - + ]: 15 : Assert(sub_hoist_quals == NULL || j->jointype == JOIN_INNER);
1528 : 15 : *hoist_quals = merge_quals(sub_hoist_quals, *hoist_quals);
1529 : : }
1530 : 213 : j->quals = (Node *) fixup_selfjoin_quals(root,
1531 : 213 : castNode(List, j->quals),
1532 : : relid);
1533 : : }
1534 : : else
45 tgl@sss.pgh.pa.us 1535 [ # # ]:UBC 0 : elog(ERROR, "unrecognized jointree node type: %d",
1536 : : (int) nodeTag(jtnode));
1537 : : }
1538 : :
1539 : : /*
1540 : : * fixup_selfjoin_quals
1541 : : * Clean up one qual list after self-join elimination.
1542 : : *
1543 : : * Two things need fixing here. First, a join clause such as "t1.a = t2.a"
1544 : : * has turned into "t1.a = t1.a". For a strict mergejoinable operator that
1545 : : * means "t1.a IS NOT NULL", and we should make the substitution, for two
1546 : : * reasons:
1547 : : * 1. It will typically result in better selectivity estimates.
1548 : : * 2. EquivalenceClass processing is likely to make the substitution
1549 : : * if we don't. While not directly harmful, we'd then fail to
1550 : : * recognize it as a duplicate of a user-written "t1.a IS NOT NULL"
1551 : : * clause, again leading to bad selectivity estimates.
1552 : : * Second, conditions that were written against the two relations separately
1553 : : * may now be identical, and we don't want to apply the same condition twice
1554 : : * (much less double-count its selectivity).
1555 : : *
1556 : : * We only touch the top-level conjuncts of the list. There, turning a NULL
1557 : : * result into FALSE makes no difference, whereas below a NOT it would,
1558 : : * invalidating the IS NOT NULL substitution. EquivalenceClass processing
1559 : : * will not be applied to sub-clauses, and cleaning up duplicates in them
1560 : : * seems like more trouble than it's worth. Also, we only consider clauses
1561 : : * that mention the relation we merged into, so that we don't change the
1562 : : * treatment of anything we didn't touch.
1563 : : *
1564 : : * Since this is not a correctness issue but just an optimization opportunity,
1565 : : * we likewise don't worry about recognizing duplicates that appear in
1566 : : * different qual lists.
1567 : : */
1568 : : static List *
45 tgl@sss.pgh.pa.us 1569 :CBC 1044 : fixup_selfjoin_quals(PlannerInfo *root, List *quals, int relid)
1570 : : {
1571 : 1044 : List *result = NIL;
1572 : : ListCell *l;
1573 : :
1574 [ + + + + : 2121 : foreach(l, quals)
+ + ]
1575 : : {
1576 : 1077 : Node *qual = (Node *) lfirst(l);
1577 : :
1578 [ + + ]: 1077 : if (bms_is_member(relid, pull_varnos(root, qual)))
1579 : : {
1580 : 1007 : qual = replace_selfjoin_qual(qual);
1581 : : /* Drop it if the substitution has made it a duplicate */
1582 [ + + ]: 1007 : if (list_member(result, qual))
1583 : 77 : continue;
1584 : : }
1585 : 1000 : result = lappend(result, qual);
1586 : : }
1587 : :
1588 : 1044 : return result;
1589 : : }
1590 : :
1591 : : /*
1592 : : * replace_selfjoin_qual
1593 : : * Replace one "X = X" qual by "X IS NOT NULL", if it is one.
1594 : : */
1595 : : static Node *
1596 : 1007 : replace_selfjoin_qual(Node *qual)
1597 : : {
1598 : : OpExpr *opexpr;
1599 : : Node *leftop;
1600 : : Node *rightop;
1601 : : NullTest *ntest;
1602 : :
1603 : : /* See if it looks like "X op X" */
1604 [ + + ]: 1007 : if (!is_opclause(qual))
1605 : 105 : return qual;
1606 : 902 : opexpr = (OpExpr *) qual;
1607 [ - + ]: 902 : if (list_length(opexpr->args) != 2)
45 tgl@sss.pgh.pa.us 1608 :UBC 0 : return qual;
45 tgl@sss.pgh.pa.us 1609 :CBC 902 : leftop = get_leftop((Expr *) opexpr);
1610 : 902 : rightop = get_rightop((Expr *) opexpr);
1611 [ + + ]: 902 : if (!equal(leftop, rightop))
1612 : 379 : return qual;
1613 : :
1614 : : /*
1615 : : * The operator must be strict and behave like btree equality, else we
1616 : : * can't conclude that it yields true for any non-null input. And the
1617 : : * input had better not be volatile, else the two evaluations might not
1618 : : * agree. If either condition doesn't hold, the clause is not a candidate
1619 : : * to be an equivalence, so we needn't worry about it getting replaced by
1620 : : * equivclass.c.
1621 : : */
1622 : 523 : set_opfuncid(opexpr);
1623 [ - + ]: 523 : if (!func_strict(opexpr->opfuncid))
45 tgl@sss.pgh.pa.us 1624 :UBC 0 : return qual;
45 tgl@sss.pgh.pa.us 1625 [ + + ]:CBC 523 : if (!op_mergejoinable(opexpr->opno, exprType(leftop)))
1626 : 5 : return qual;
1627 [ - + ]: 518 : if (contain_volatile_functions(leftop))
45 tgl@sss.pgh.pa.us 1628 :UBC 0 : return qual;
1629 : :
1630 : : /* OK, replace it */
45 tgl@sss.pgh.pa.us 1631 :CBC 518 : ntest = makeNode(NullTest);
1632 : 518 : ntest->arg = (Expr *) leftop;
1633 : 518 : ntest->nulltesttype = IS_NOT_NULL;
1634 : 518 : ntest->argisrow = false; /* correct even if composite arg */
1635 : 518 : ntest->location = -1;
1636 : 518 : return (Node *) ntest;
1637 : : }
1638 : :
1639 : : /*
1640 : : * split_selfjoin_quals
1641 : : * Processes 'joinquals' by building two lists: one containing the quals
1642 : : * where the columns/exprs are on either side of the join match and
1643 : : * another one containing the remaining quals.
1644 : : *
1645 : : * 'joinquals' must only contain quals for a RTE_RELATION being joined to
1646 : : * itself.
1647 : : */
1648 : : static void
606 akorotkov@postgresql 1649 : 1861 : split_selfjoin_quals(PlannerInfo *root, List *joinquals, List **selfjoinquals,
1650 : : List **otherjoinquals, int from, int to)
1651 : : {
1652 : 1861 : List *sjoinquals = NIL;
1653 : 1861 : List *ojoinquals = NIL;
1654 : :
1655 [ + - + + : 5783 : foreach_node(RestrictInfo, rinfo, joinquals)
+ + ]
1656 : : {
1657 : : OpExpr *expr;
1658 : : Node *leftexpr;
1659 : : Node *rightexpr;
1660 : :
1661 : : /*
1662 : : * Since the given joinquals all came from
1663 : : * generate_join_implied_equalities, they ought to look like equality
1664 : : * operators on single-relation expressions. But let's check that.
1665 : : * Anything that doesn't look like that can be dumped into ojoinquals.
1666 : : */
1667 [ + - + - ]: 4122 : if (!rinfo->mergeopfamilies ||
1668 [ + - ]: 4122 : bms_num_members(rinfo->clause_relids) != 2 ||
1669 [ - + ]: 4122 : bms_membership(rinfo->left_relids) != BMS_SINGLETON ||
1670 : 2061 : bms_membership(rinfo->right_relids) != BMS_SINGLETON)
1671 : : {
606 akorotkov@postgresql 1672 :UBC 0 : ojoinquals = lappend(ojoinquals, rinfo);
1673 : 0 : continue;
1674 : : }
1675 : :
606 akorotkov@postgresql 1676 :CBC 2061 : expr = (OpExpr *) rinfo->clause;
1677 : :
1678 [ + - - + ]: 2061 : if (!IsA(expr, OpExpr) || list_length(expr->args) != 2)
1679 : : {
606 akorotkov@postgresql 1680 :UBC 0 : ojoinquals = lappend(ojoinquals, rinfo);
1681 : 0 : continue;
1682 : : }
1683 : :
606 akorotkov@postgresql 1684 :CBC 2061 : leftexpr = get_leftop(rinfo->clause);
1685 : 2061 : rightexpr = copyObject(get_rightop(rinfo->clause));
1686 : :
1687 [ + - + + ]: 2061 : if (leftexpr && IsA(leftexpr, RelabelType))
1688 : 20 : leftexpr = (Node *) ((RelabelType *) leftexpr)->arg;
1689 [ + - + + ]: 2061 : if (rightexpr && IsA(rightexpr, RelabelType))
1690 : 15 : rightexpr = (Node *) ((RelabelType *) rightexpr)->arg;
1691 : :
1692 : : /*
1693 : : * Quite an expensive operation, narrowing the use case. For example,
1694 : : * when we have cast of the same var to different (but compatible)
1695 : : * types.
1696 : : */
45 tgl@sss.pgh.pa.us 1697 : 2061 : ChangeVarNodes(rightexpr,
1698 : 2061 : bms_singleton_member(rinfo->right_relids),
1699 : 2061 : bms_singleton_member(rinfo->left_relids), 0);
1700 : :
606 akorotkov@postgresql 1701 [ + + ]: 2061 : if (equal(leftexpr, rightexpr))
1702 : 1461 : sjoinquals = lappend(sjoinquals, rinfo);
1703 : : else
1704 : 600 : ojoinquals = lappend(ojoinquals, rinfo);
1705 : : }
1706 : :
1707 : 1861 : *selfjoinquals = sjoinquals;
1708 : 1861 : *otherjoinquals = ojoinquals;
1709 : 1861 : }
1710 : :
1711 : : /*
1712 : : * Check for a case when uniqueness is at least partly derived from a
1713 : : * baserestrictinfo clause. In this case, we have a chance to return only
1714 : : * one row (if such clauses on both sides of SJ are equal) or nothing (if they
1715 : : * are different).
1716 : : */
1717 : : static bool
1718 : 513 : match_unique_clauses(PlannerInfo *root, RelOptInfo *outer, List *uclauses,
1719 : : Index relid)
1720 : : {
1721 [ + + + + : 1041 : foreach_node(RestrictInfo, rinfo, uclauses)
+ + ]
1722 : : {
1723 : : Expr *clause;
1724 : : Node *iclause;
1725 : : Node *c1;
1726 : 125 : bool matched = false;
1727 : :
1728 [ + - - + ]: 125 : Assert(outer->relid > 0 && relid > 0);
1729 : :
1730 : : /* Only filters like f(R.x1,...,R.xN) == expr we should consider. */
1731 [ - + ]: 125 : Assert(bms_is_empty(rinfo->left_relids) ^
1732 : : bms_is_empty(rinfo->right_relids));
1733 : :
1734 : 125 : clause = (Expr *) copyObject(rinfo->clause);
45 tgl@sss.pgh.pa.us 1735 : 125 : ChangeVarNodes((Node *) clause, relid, outer->relid, 0);
1736 : :
606 akorotkov@postgresql 1737 [ + + ]: 125 : iclause = bms_is_empty(rinfo->left_relids) ? get_rightop(clause) :
1738 : 120 : get_leftop(clause);
1739 [ + + ]: 125 : c1 = bms_is_empty(rinfo->left_relids) ? get_leftop(clause) :
1740 : 120 : get_rightop(clause);
1741 : :
1742 : : /*
1743 : : * Compare these left and right sides with the corresponding sides of
1744 : : * the outer's filters. If no one is detected - return immediately.
1745 : : */
1746 [ + + + + : 330 : foreach_node(RestrictInfo, orinfo, outer->baserestrictinfo)
+ + ]
1747 : : {
1748 : : Node *oclause;
1749 : : Node *c2;
1750 : :
1751 [ + + ]: 150 : if (orinfo->mergeopfamilies == NIL)
1752 : : /* Don't consider clauses that aren't similar to 'F(X)=G(Y)' */
1753 : 40 : continue;
1754 : :
1755 [ - + ]: 110 : Assert(is_opclause(orinfo->clause));
1756 : :
1757 : 220 : oclause = bms_is_empty(orinfo->left_relids) ?
1758 [ + + ]: 110 : get_rightop(orinfo->clause) : get_leftop(orinfo->clause);
1759 : 220 : c2 = (bms_is_empty(orinfo->left_relids) ?
1760 [ + + ]: 110 : get_leftop(orinfo->clause) : get_rightop(orinfo->clause));
1761 : :
1762 [ + + + + ]: 110 : if (equal(iclause, oclause) && equal(c1, c2))
1763 : : {
1764 : 70 : matched = true;
1765 : 70 : break;
1766 : : }
1767 : : }
1768 : :
1769 [ + + ]: 125 : if (!matched)
1770 : 55 : return false;
1771 : : }
1772 : :
1773 : 458 : return true;
1774 : : }
1775 : :
1776 : : /*
1777 : : * Find and remove unique self-joins in a group of base relations that have
1778 : : * the same Oid.
1779 : : *
1780 : : * Return true if we removed any joins.
1781 : : *
1782 : : * After a removal, we continue searching for more removals, even though the
1783 : : * tests will be using derived data that is now partially stale. That is safe
1784 : : * because we are trying to prove that a candidate pair of relations must
1785 : : * match the same row, and the stale data can only omit quals, never invent
1786 : : * them. The removed relation's quals are moved onto the kept relation in
1787 : : * the jointree but not into its baserestrictinfo, and no other derived data
1788 : : * changes. A proof made from a subset of the applicable quals remains valid
1789 : : * when the rest are added, since extra quals can only remove rows from the
1790 : : * join. So a pass may miss a removal that a later pass will find, but it
1791 : : * cannot make one that isn't justified.
1792 : : */
1793 : : static bool
1794 : 8794 : remove_self_joins_one_group(PlannerInfo *root, Relids relids)
1795 : : {
45 tgl@sss.pgh.pa.us 1796 : 8794 : bool removed = false;
1797 : : int k; /* Index of kept relation */
606 akorotkov@postgresql 1798 : 8794 : int r = -1; /* Index of removed relation */
1799 : :
1800 [ + + ]: 27574 : while ((r = bms_next_member(relids, r)) > 0)
1801 : : {
412 1802 : 18780 : RelOptInfo *rrel = root->simple_rel_array[r];
1803 : :
1804 : : /* k iterates over the relids after r */
606 1805 : 18780 : k = r;
1806 [ + + ]: 29746 : while ((k = bms_next_member(relids, k)) > 0)
1807 : : {
1808 : 11424 : Relids joinrelids = NULL;
412 1809 : 11424 : RelOptInfo *krel = root->simple_rel_array[k];
1810 : : List *restrictlist;
1811 : : List *selfjoinquals;
1812 : : List *otherjoinquals;
1813 : : ListCell *lc;
606 1814 : 11424 : bool jinfo_check = true;
412 1815 : 11424 : PlanRowMark *kmark = NULL;
1816 : 11424 : PlanRowMark *rmark = NULL;
606 1817 : 11424 : List *uclauses = NIL;
1818 : :
1819 : : /* A sanity check: the relations have the same Oid. */
1820 [ - + ]: 11424 : Assert(root->simple_rte_array[k]->relid ==
1821 : : root->simple_rte_array[r]->relid);
1822 : :
1823 : : /*
1824 : : * It is impossible to eliminate the join of two relations if they
1825 : : * are not on the same side of every outer join. Otherwise, the
1826 : : * planner can't find any variants of the correct query plan.
1827 : : */
1828 [ + + + + : 14065 : foreach(lc, root->join_info_list)
+ + ]
1829 : : {
1830 : 9009 : SpecialJoinInfo *info = (SpecialJoinInfo *) lfirst(lc);
1831 : :
1832 [ + + ]: 18018 : if ((bms_is_member(k, info->syn_lefthand) ^
1833 [ + + ]: 12722 : bms_is_member(r, info->syn_lefthand)) ||
1834 : 3713 : (bms_is_member(k, info->syn_righthand) ^
1835 : 3713 : bms_is_member(r, info->syn_righthand)))
1836 : : {
1837 : 6368 : jinfo_check = false;
1838 : 6368 : break;
1839 : : }
1840 : : }
1841 [ + + ]: 11424 : if (!jinfo_check)
1842 : 10966 : continue;
1843 : :
1844 : : /*
1845 : : * Check Row Marks equivalence. We can't remove the join if the
1846 : : * relations have row marks of different strength (e.g., one is
1847 : : * locked FOR UPDATE, and another just has ROW_MARK_REFERENCE for
1848 : : * EvalPlanQual rechecking).
1849 : : */
1850 [ + + + - : 5167 : foreach(lc, root->rowMarks)
+ + ]
1851 : : {
1852 : 207 : PlanRowMark *rowMark = (PlanRowMark *) lfirst(lc);
1853 : :
414 1854 [ + + ]: 207 : if (rowMark->rti == r)
1855 : : {
412 1856 [ - + ]: 96 : Assert(rmark == NULL);
1857 : 96 : rmark = rowMark;
1858 : : }
414 1859 [ + + ]: 111 : else if (rowMark->rti == k)
1860 : : {
412 1861 [ - + ]: 96 : Assert(kmark == NULL);
1862 : 96 : kmark = rowMark;
1863 : : }
1864 : :
1865 [ + + + - ]: 207 : if (kmark && rmark)
606 1866 : 96 : break;
1867 : : }
412 1868 [ + + + - : 5056 : if (kmark && rmark && kmark->markType != rmark->markType)
+ + ]
606 1869 : 28 : continue;
1870 : :
1871 : : /*
1872 : : * We only deal with base rels here, so their relids bitset
1873 : : * contains only one member -- their relid.
1874 : : */
1875 : 5028 : joinrelids = bms_add_member(joinrelids, r);
1876 : 5028 : joinrelids = bms_add_member(joinrelids, k);
1877 : :
1878 : : /*
1879 : : * PHVs should not impose any constraints on removing self-joins.
1880 : : */
1881 : :
1882 : : /*
1883 : : * At this stage, joininfo lists of inner and outer can contain
1884 : : * only clauses required for a superior outer join that can't
1885 : : * influence this optimization. So, we can avoid to call the
1886 : : * build_joinrel_restrictlist() routine.
1887 : : */
1888 : 5028 : restrictlist = generate_join_implied_equalities(root, joinrelids,
1889 : : rrel->relids,
1890 : : krel, NULL);
1891 [ + + ]: 5028 : if (restrictlist == NIL)
1892 : 3167 : continue;
1893 : :
1894 : : /*
1895 : : * Process restrictlist to separate the self-join quals from the
1896 : : * other quals. e.g., "x = x" goes to selfjoinquals and "a = b" to
1897 : : * otherjoinquals.
1898 : : */
1899 : 1861 : split_selfjoin_quals(root, restrictlist, &selfjoinquals,
412 1900 : 1861 : &otherjoinquals, rrel->relid, krel->relid);
1901 : :
606 1902 [ - + ]: 1861 : Assert(list_length(restrictlist) ==
1903 : : (list_length(selfjoinquals) + list_length(otherjoinquals)));
1904 : :
1905 : : /*
1906 : : * To enable SJE for the only degenerate case without any self
1907 : : * join clauses at all, add baserestrictinfo to this list. The
1908 : : * degenerate case works only if both sides have the same clause.
1909 : : * So doesn't matter which side to add.
1910 : : */
412 1911 : 1861 : selfjoinquals = list_concat(selfjoinquals, krel->baserestrictinfo);
1912 : :
1913 : : /*
1914 : : * Determine if the rrel can duplicate outer rows. We must bypass
1915 : : * the unique rel cache here since we're possibly using a subset
1916 : : * of join quals. We can use 'force_cache' == true when all join
1917 : : * quals are self-join quals. Otherwise, we could end up putting
1918 : : * false negatives in the cache.
1919 : : */
1920 [ + + ]: 1861 : if (!innerrel_is_unique_ext(root, joinrelids, rrel->relids,
1921 : : krel, JOIN_INNER, selfjoinquals,
606 1922 : 1861 : list_length(otherjoinquals) == 0,
1923 : : &uclauses))
1924 : 1348 : continue;
1925 : :
1926 : : /*
1927 : : * 'uclauses' is the copy of outer->baserestrictinfo that are
1928 : : * associated with an index. We proved by matching selfjoinquals
1929 : : * to a unique index that the outer relation has at most one
1930 : : * matching row for each inner row. Sometimes that is not enough.
1931 : : * e.g. "WHERE s1.b = s2.b AND s1.a = 1 AND s2.a = 2" when the
1932 : : * unique index is (a,b). Having non-empty uclauses, we must
1933 : : * validate that the inner baserestrictinfo contains the same
1934 : : * expressions, or we won't match the same row on each side of the
1935 : : * join.
1936 : : */
412 1937 [ + + ]: 513 : if (!match_unique_clauses(root, rrel, uclauses, krel->relid))
606 1938 : 55 : continue;
1939 : :
1940 : : /* OK, remove rrel from the query */
45 tgl@sss.pgh.pa.us 1941 : 458 : remove_self_join_rel(root, krel, rrel, kmark, rmark);
1942 : 458 : removed = true;
1943 : :
1944 : : /*
1945 : : * Since relation r is now gone, we mustn't keep looking for
1946 : : * matches to it. But we can keep scanning later relids members
1947 : : * for additional join pairs.
1948 : : */
606 akorotkov@postgresql 1949 : 458 : break;
1950 : : }
1951 : : }
1952 : :
45 tgl@sss.pgh.pa.us 1953 : 8794 : return removed;
1954 : : }
1955 : :
1956 : : /*
1957 : : * Gather indexes of base relations from the joinlist and try to eliminate
1958 : : * self-joins.
1959 : : *
1960 : : * Return true if we removed any joins.
1961 : : */
1962 : : static bool
1963 : 81041 : remove_self_joins_recurse(PlannerInfo *root, List *joinlist)
1964 : : {
1965 : 81041 : bool removed = false;
1966 : : ListCell *jl;
606 akorotkov@postgresql 1967 : 81041 : Relids relids = NULL;
1968 : : SelfJoinCandidate *candidates;
1969 : : int i;
1970 : : int j;
1971 : : int numRels;
1972 : :
1973 : : /* Collect indexes of base relations of the join tree */
1974 [ + - + + : 271675 : foreach(jl, joinlist)
+ + ]
1975 : : {
1976 : 190634 : Node *jlnode = (Node *) lfirst(jl);
1977 : :
1978 [ + + ]: 190634 : if (IsA(jlnode, RangeTblRef))
1979 : : {
1980 : 187695 : int varno = ((RangeTblRef *) jlnode)->rtindex;
1981 : 187695 : RangeTblEntry *rte = root->simple_rte_array[varno];
1982 : :
1983 : : /*
1984 : : * We only consider ordinary relations as candidates to be
1985 : : * removed, and these relations should not have TABLESAMPLE
1986 : : * clauses specified. Removing a relation with TABLESAMPLE clause
1987 : : * could potentially change the semantics of the query. Because of
1988 : : * UPDATE/DELETE EPQ mechanism, currently Query->resultRelation or
1989 : : * Query->mergeTargetRelation associated rel cannot be eliminated.
1990 : : */
1991 [ + + ]: 187695 : if (rte->rtekind == RTE_RELATION &&
1992 [ + + ]: 165918 : rte->relkind == RELKIND_RELATION &&
1993 [ + + ]: 161391 : rte->tablesample == NULL &&
1994 [ + + ]: 161359 : varno != root->parse->resultRelation &&
1995 [ + - ]: 159839 : varno != root->parse->mergeTargetRelation)
1996 : : {
1997 [ - + ]: 159839 : Assert(!bms_is_member(varno, relids));
1998 : 159839 : relids = bms_add_member(relids, varno);
1999 : : }
2000 : : }
2001 [ + - ]: 2939 : else if (IsA(jlnode, List))
2002 : : {
2003 : : /* Recursively perform SJE within the sub-joinlist */
45 tgl@sss.pgh.pa.us 2004 : 2939 : removed |= remove_self_joins_recurse(root, (List *) jlnode);
2005 : : }
2006 : : else
606 akorotkov@postgresql 2007 [ # # ]:UBC 0 : elog(ERROR, "unrecognized joinlist node type: %d",
2008 : : (int) nodeTag(jlnode));
2009 : : }
2010 : :
606 akorotkov@postgresql 2011 :CBC 81041 : numRels = bms_num_members(relids);
2012 : :
2013 : : /* No work if not at least two relations at this level */
2014 [ + + ]: 81041 : if (numRels < 2)
45 tgl@sss.pgh.pa.us 2015 : 22507 : return removed; /* ... but don't fail to report sub-removals */
2016 : :
2017 : : /*
2018 : : * In order to find relations with the same reloid/useroid we first build
2019 : : * an array of candidates and then sort it by those oids.
2020 : : */
306 michael@paquier.xyz 2021 : 58534 : candidates = palloc_array(SelfJoinCandidate, numRels);
606 akorotkov@postgresql 2022 : 58534 : i = -1;
2023 : 58534 : j = 0;
2024 [ + + ]: 202540 : while ((i = bms_next_member(relids, i)) >= 0)
2025 : : {
13 tgl@sss.pgh.pa.us 2026 : 144006 : RangeTblEntry *rte = root->simple_rte_array[i];
2027 : :
606 akorotkov@postgresql 2028 : 144006 : candidates[j].relid = i;
13 tgl@sss.pgh.pa.us 2029 : 144006 : candidates[j].reloid = rte->relid;
2030 [ + - ]: 144006 : if (rte->perminfoindex != 0)
2031 : : {
2032 : : RTEPermissionInfo *perminfo;
2033 : :
2034 : 144006 : perminfo = getRTEPermissionInfo(root->parse->rteperminfos, rte);
2035 : 144006 : candidates[j].useroid = perminfo->checkAsUser;
2036 : : }
2037 : : else
13 tgl@sss.pgh.pa.us 2038 :UBC 0 : candidates[j].useroid = InvalidOid;
606 akorotkov@postgresql 2039 :CBC 144006 : j++;
2040 : : }
2041 : :
2042 : 58534 : qsort(candidates, numRels, sizeof(SelfJoinCandidate),
2043 : : self_join_candidates_cmp);
2044 : :
2045 : : /*
2046 : : * Iteratively form a group of relation indexes with the same oids and
2047 : : * launch the routine that detects self-joins in this group.
2048 : : *
2049 : : * We remove considered relations from relids as we scan, so that that set
2050 : : * should be empty at the end.
2051 : : */
2052 : 58534 : i = 0;
45 tgl@sss.pgh.pa.us 2053 [ + + ]: 202540 : for (j = 1; j <= numRels; j++)
2054 : : {
13 2055 [ + + ]: 144006 : if (j == numRels ||
2056 [ + + ]: 85472 : candidates[j].reloid != candidates[i].reloid ||
2057 [ + + ]: 10006 : candidates[j].useroid != candidates[i].useroid)
2058 : : {
606 akorotkov@postgresql 2059 [ + + ]: 134020 : if (j - i >= 2)
2060 : : {
2061 : : /* Create a group of relation indexes with the same oids */
2062 : 8794 : Relids group = NULL;
2063 : :
2064 [ + + ]: 27574 : while (i < j)
2065 : : {
2066 : 18780 : group = bms_add_member(group, candidates[i].relid);
2067 : 18780 : i++;
2068 : : }
2069 : 8794 : relids = bms_del_members(relids, group);
2070 : :
2071 : : /* Try to remove self-joins from the group */
45 tgl@sss.pgh.pa.us 2072 : 8794 : removed |= remove_self_joins_one_group(root, group);
606 akorotkov@postgresql 2073 : 8794 : bms_free(group);
2074 : : }
2075 : : else
2076 : : {
2077 : : /* Nothing to do with this group, just drop it from the set */
45 tgl@sss.pgh.pa.us 2078 [ + + ]: 250452 : while (i < j)
2079 : : {
2080 : 125226 : relids = bms_del_member(relids, candidates[i].relid);
2081 : 125226 : i++;
2082 : : }
2083 : : }
2084 : : }
2085 : : }
2086 : :
606 akorotkov@postgresql 2087 [ - + ]: 58534 : Assert(bms_is_empty(relids));
2088 : :
45 tgl@sss.pgh.pa.us 2089 : 58534 : return removed;
2090 : : }
2091 : :
2092 : : /*
2093 : : * Compare self-join candidates by their reloid and then useroid.
2094 : : */
2095 : : static int
606 akorotkov@postgresql 2096 : 104729 : self_join_candidates_cmp(const void *a, const void *b)
2097 : : {
2098 : 104729 : const SelfJoinCandidate *ca = (const SelfJoinCandidate *) a;
2099 : 104729 : const SelfJoinCandidate *cb = (const SelfJoinCandidate *) b;
2100 : :
2101 [ + + ]: 104729 : if (ca->reloid != cb->reloid)
2102 [ + + ]: 94678 : return (ca->reloid < cb->reloid ? -1 : 1);
13 tgl@sss.pgh.pa.us 2103 [ + + ]: 10051 : else if (ca->useroid != cb->useroid)
2104 [ + - ]: 20 : return (ca->useroid < cb->useroid ? -1 : 1);
2105 : : else
606 akorotkov@postgresql 2106 : 10031 : return 0;
2107 : : }
2108 : :
2109 : : /*
2110 : : * Find and remove useless self joins.
2111 : : *
2112 : : * Search for joins where a relation is joined to itself. If the join clause
2113 : : * for each tuple from one side of the join is proven to match the same
2114 : : * physical row (or nothing) on the other side, that self-join can be
2115 : : * eliminated from the query. Suitable join clauses are assumed to be in the
2116 : : * form of X = X, and can be replaced with NOT NULL clauses.
2117 : : *
2118 : : * For the sake of simplicity, we don't apply this optimization to special
2119 : : * joins. Here is a list of what we could do in some particular cases:
2120 : : * 'a a1 semi join a a2': is reduced to inner by reduce_unique_semijoins,
2121 : : * and then removed normally.
2122 : : * 'a a1 anti join a a2': could simplify to a scan with 'outer quals AND
2123 : : * (IS NULL on join columns OR NOT inner quals)'.
2124 : : * 'a a1 left join a a2': could simplify to a scan like inner but without
2125 : : * NOT NULL conditions on join columns.
2126 : : * 'a a1 left join (a a2 join b)': can't simplify this, because join to b
2127 : : * can both remove rows and introduce duplicates.
2128 : : *
2129 : : * To search for removable joins, we order all the relations on their Oid,
2130 : : * go over each set with the same Oid, and consider each pair of relations
2131 : : * in this set.
2132 : : *
2133 : : * To remove the join, we delete one of the participating relations from the
2134 : : * query's jointree and rewrite all references to it to point to the remaining
2135 : : * relation. We also have to modify their row marks.
2136 : : *
2137 : : * 'joinlist' is the top-level joinlist of the query; we use it to identify
2138 : : * groups of relations that could be joined to each other.
2139 : : *
2140 : : * We return true if we removed any self-joins. If so, the caller must
2141 : : * recompute everything that was derived from the jointree, and should then
2142 : : * try join simplifications again since we might have exposed opportunities
2143 : : * for additional simplifications.
2144 : : */
2145 : : bool
2146 : 245697 : remove_useless_self_joins(PlannerInfo *root, List *joinlist)
2147 : : {
2148 : : /* Skip if SJE is disabled, or if the joinlist has less than 2 members. */
2149 [ + - + - : 491394 : if (!enable_self_join_elimination || joinlist == NIL ||
+ + ]
2150 [ + + ]: 414032 : (list_length(joinlist) == 1 && !IsA(linitial(joinlist), List)))
45 tgl@sss.pgh.pa.us 2151 : 167595 : return false;
2152 : :
2153 : : /* Try to merge pairs of self-joined relations. */
2154 : 78102 : return remove_self_joins_recurse(root, joinlist);
2155 : : }
|
