1 /*-------------------------------------------------------------------------
2 *
3 * analyzejoins.c
4 * Routines for simplifying joins after initial query analysis
5 *
6 * While we do a great deal of join simplification in prep/prepjointree.c,
7 * certain optimizations cannot be performed at that stage for lack of
8 * detailed information about the query. The routines here are invoked
9 * after initsplan.c has done its work, and can do additional join removal
10 * and simplification steps based on the information extracted. The penalty
11 * is that we have to work harder to clean up after ourselves when we modify
12 * the query, since the derived data structures have to be updated too.
13 *
14 * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
15 * Portions Copyright (c) 1994, Regents of the University of California
16 *
17 *
18 * IDENTIFICATION
19 * src/backend/optimizer/plan/analyzejoins.c
20 *
21 *-------------------------------------------------------------------------
22 */
23 #include "postgres.h"
24
25 #include "nodes/nodeFuncs.h"
26 #include "optimizer/clauses.h"
27 #include "optimizer/joininfo.h"
28 #include "optimizer/optimizer.h"
29 #include "optimizer/pathnode.h"
30 #include "optimizer/paths.h"
31 #include "optimizer/planmain.h"
32 #include "optimizer/tlist.h"
33 #include "utils/lsyscache.h"
34
35 /* source-code-compatibility hacks for pull_varnos() API change */
36 #define pull_varnos(a,b) pull_varnos_new(a,b)
37
38 /* local functions */
39 static bool join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo);
40 static void remove_rel_from_query(PlannerInfo *root, int relid,
41 Relids joinrelids);
42 static List *remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved);
43 static bool rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel);
44 static bool rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel,
45 List *clause_list);
46 static Oid distinct_col_search(int colno, List *colnos, List *opids);
47 static bool is_innerrel_unique_for(PlannerInfo *root,
48 Relids joinrelids,
49 Relids outerrelids,
50 RelOptInfo *innerrel,
51 JoinType jointype,
52 List *restrictlist);
53
54
55 /*
56 * remove_useless_joins
57 * Check for relations that don't actually need to be joined at all,
58 * and remove them from the query.
59 *
60 * We are passed the current joinlist and return the updated list. Other
61 * data structures that have to be updated are accessible via "root".
62 */
63 List *
remove_useless_joins(PlannerInfo * root,List * joinlist)64 remove_useless_joins(PlannerInfo *root, List *joinlist)
65 {
66 ListCell *lc;
67
68 /*
69 * We are only interested in relations that are left-joined to, so we can
70 * scan the join_info_list to find them easily.
71 */
72 restart:
73 foreach(lc, root->join_info_list)
74 {
75 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
76 int innerrelid;
77 int nremoved;
78
79 /* Skip if not removable */
80 if (!join_is_removable(root, sjinfo))
81 continue;
82
83 /*
84 * Currently, join_is_removable can only succeed when the sjinfo's
85 * righthand is a single baserel. Remove that rel from the query and
86 * joinlist.
87 */
88 innerrelid = bms_singleton_member(sjinfo->min_righthand);
89
90 remove_rel_from_query(root, innerrelid,
91 bms_union(sjinfo->min_lefthand,
92 sjinfo->min_righthand));
93
94 /* We verify that exactly one reference gets removed from joinlist */
95 nremoved = 0;
96 joinlist = remove_rel_from_joinlist(joinlist, innerrelid, &nremoved);
97 if (nremoved != 1)
98 elog(ERROR, "failed to find relation %d in joinlist", innerrelid);
99
100 /*
101 * We can delete this SpecialJoinInfo from the list too, since it's no
102 * longer of interest.
103 */
104 root->join_info_list = list_delete_ptr(root->join_info_list, sjinfo);
105
106 /*
107 * Restart the scan. This is necessary to ensure we find all
108 * removable joins independently of ordering of the join_info_list
109 * (note that removal of attr_needed bits may make a join appear
110 * removable that did not before). Also, since we just deleted the
111 * current list cell, we'd have to have some kluge to continue the
112 * list scan anyway.
113 */
114 goto restart;
115 }
116
117 return joinlist;
118 }
119
120 /*
121 * clause_sides_match_join
122 * Determine whether a join clause is of the right form to use in this join.
123 *
124 * We already know that the clause is a binary opclause referencing only the
125 * rels in the current join. The point here is to check whether it has the
126 * form "outerrel_expr op innerrel_expr" or "innerrel_expr op outerrel_expr",
127 * rather than mixing outer and inner vars on either side. If it matches,
128 * we set the transient flag outer_is_left to identify which side is which.
129 */
130 static inline bool
clause_sides_match_join(RestrictInfo * rinfo,Relids outerrelids,Relids innerrelids)131 clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids,
132 Relids innerrelids)
133 {
134 if (bms_is_subset(rinfo->left_relids, outerrelids) &&
135 bms_is_subset(rinfo->right_relids, innerrelids))
136 {
137 /* lefthand side is outer */
138 rinfo->outer_is_left = true;
139 return true;
140 }
141 else if (bms_is_subset(rinfo->left_relids, innerrelids) &&
142 bms_is_subset(rinfo->right_relids, outerrelids))
143 {
144 /* righthand side is outer */
145 rinfo->outer_is_left = false;
146 return true;
147 }
148 return false; /* no good for these input relations */
149 }
150
151 /*
152 * join_is_removable
153 * Check whether we need not perform this special join at all, because
154 * it will just duplicate its left input.
155 *
156 * This is true for a left join for which the join condition cannot match
157 * more than one inner-side row. (There are other possibly interesting
158 * cases, but we don't have the infrastructure to prove them.) We also
159 * have to check that the inner side doesn't generate any variables needed
160 * above the join.
161 */
162 static bool
join_is_removable(PlannerInfo * root,SpecialJoinInfo * sjinfo)163 join_is_removable(PlannerInfo *root, SpecialJoinInfo *sjinfo)
164 {
165 int innerrelid;
166 RelOptInfo *innerrel;
167 Relids joinrelids;
168 List *clause_list = NIL;
169 ListCell *l;
170 int attroff;
171
172 /*
173 * Must be a non-delaying left join to a single baserel, else we aren't
174 * going to be able to do anything with it.
175 */
176 if (sjinfo->jointype != JOIN_LEFT ||
177 sjinfo->delay_upper_joins)
178 return false;
179
180 if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
181 return false;
182
183 innerrel = find_base_rel(root, innerrelid);
184
185 /*
186 * Before we go to the effort of checking whether any innerrel variables
187 * are needed above the join, make a quick check to eliminate cases in
188 * which we will surely be unable to prove uniqueness of the innerrel.
189 */
190 if (!rel_supports_distinctness(root, innerrel))
191 return false;
192
193 /* Compute the relid set for the join we are considering */
194 joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
195
196 /*
197 * We can't remove the join if any inner-rel attributes are used above the
198 * join.
199 *
200 * Note that this test only detects use of inner-rel attributes in higher
201 * join conditions and the target list. There might be such attributes in
202 * pushed-down conditions at this join, too. We check that case below.
203 *
204 * As a micro-optimization, it seems better to start with max_attr and
205 * count down rather than starting with min_attr and counting up, on the
206 * theory that the system attributes are somewhat less likely to be wanted
207 * and should be tested last.
208 */
209 for (attroff = innerrel->max_attr - innerrel->min_attr;
210 attroff >= 0;
211 attroff--)
212 {
213 if (!bms_is_subset(innerrel->attr_needed[attroff], joinrelids))
214 return false;
215 }
216
217 /*
218 * Similarly check that the inner rel isn't needed by any PlaceHolderVars
219 * that will be used above the join. We only need to fail if such a PHV
220 * actually references some inner-rel attributes; but the correct check
221 * for that is relatively expensive, so we first check against ph_eval_at,
222 * which must mention the inner rel if the PHV uses any inner-rel attrs as
223 * non-lateral references. Note that if the PHV's syntactic scope is just
224 * the inner rel, we can't drop the rel even if the PHV is variable-free.
225 */
226 foreach(l, root->placeholder_list)
227 {
228 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
229
230 if (bms_overlap(phinfo->ph_lateral, innerrel->relids))
231 return false; /* it references innerrel laterally */
232 if (bms_is_subset(phinfo->ph_needed, joinrelids))
233 continue; /* PHV is not used above the join */
234 if (!bms_overlap(phinfo->ph_eval_at, innerrel->relids))
235 continue; /* it definitely doesn't reference innerrel */
236 if (bms_is_subset(phinfo->ph_eval_at, innerrel->relids))
237 return false; /* there isn't any other place to eval PHV */
238 if (bms_overlap(pull_varnos(root, (Node *) phinfo->ph_var->phexpr),
239 innerrel->relids))
240 return false; /* it does reference innerrel */
241 }
242
243 /*
244 * Search for mergejoinable clauses that constrain the inner rel against
245 * either the outer rel or a pseudoconstant. If an operator is
246 * mergejoinable then it behaves like equality for some btree opclass, so
247 * it's what we want. The mergejoinability test also eliminates clauses
248 * containing volatile functions, which we couldn't depend on.
249 */
250 foreach(l, innerrel->joininfo)
251 {
252 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
253
254 /*
255 * If it's not a join clause for this outer join, we can't use it.
256 * Note that if the clause is pushed-down, then it is logically from
257 * above the outer join, even if it references no other rels (it might
258 * be from WHERE, for example).
259 */
260 if (RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
261 {
262 /*
263 * If such a clause actually references the inner rel then join
264 * removal has to be disallowed. We have to check this despite
265 * the previous attr_needed checks because of the possibility of
266 * pushed-down clauses referencing the rel.
267 */
268 if (bms_is_member(innerrelid, restrictinfo->clause_relids))
269 return false;
270 continue; /* else, ignore; not useful here */
271 }
272
273 /* Ignore if it's not a mergejoinable clause */
274 if (!restrictinfo->can_join ||
275 restrictinfo->mergeopfamilies == NIL)
276 continue; /* not mergejoinable */
277
278 /*
279 * Check if clause has the form "outer op inner" or "inner op outer",
280 * and if so mark which side is inner.
281 */
282 if (!clause_sides_match_join(restrictinfo, sjinfo->min_lefthand,
283 innerrel->relids))
284 continue; /* no good for these input relations */
285
286 /* OK, add to list */
287 clause_list = lappend(clause_list, restrictinfo);
288 }
289
290 /*
291 * Now that we have the relevant equality join clauses, try to prove the
292 * innerrel distinct.
293 */
294 if (rel_is_distinct_for(root, innerrel, clause_list))
295 return true;
296
297 /*
298 * Some day it would be nice to check for other methods of establishing
299 * distinctness.
300 */
301 return false;
302 }
303
304
305 /*
306 * Remove the target relid from the planner's data structures, having
307 * determined that there is no need to include it in the query.
308 *
309 * We are not terribly thorough here. We must make sure that the rel is
310 * no longer treated as a baserel, and that attributes of other baserels
311 * are no longer marked as being needed at joins involving this rel.
312 * Also, join quals involving the rel have to be removed from the joininfo
313 * lists, but only if they belong to the outer join identified by joinrelids.
314 */
315 static void
remove_rel_from_query(PlannerInfo * root,int relid,Relids joinrelids)316 remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids)
317 {
318 RelOptInfo *rel = find_base_rel(root, relid);
319 List *joininfos;
320 Index rti;
321 ListCell *l;
322 ListCell *nextl;
323
324 /*
325 * Mark the rel as "dead" to show it is no longer part of the join tree.
326 * (Removing it from the baserel array altogether seems too risky.)
327 */
328 rel->reloptkind = RELOPT_DEADREL;
329
330 /*
331 * Remove references to the rel from other baserels' attr_needed arrays.
332 */
333 for (rti = 1; rti < root->simple_rel_array_size; rti++)
334 {
335 RelOptInfo *otherrel = root->simple_rel_array[rti];
336 int attroff;
337
338 /* there may be empty slots corresponding to non-baserel RTEs */
339 if (otherrel == NULL)
340 continue;
341
342 Assert(otherrel->relid == rti); /* sanity check on array */
343
344 /* no point in processing target rel itself */
345 if (otherrel == rel)
346 continue;
347
348 for (attroff = otherrel->max_attr - otherrel->min_attr;
349 attroff >= 0;
350 attroff--)
351 {
352 otherrel->attr_needed[attroff] =
353 bms_del_member(otherrel->attr_needed[attroff], relid);
354 }
355 }
356
357 /*
358 * Likewise remove references from SpecialJoinInfo data structures.
359 *
360 * This is relevant in case the outer join we're deleting is nested inside
361 * other outer joins: the upper joins' relid sets have to be adjusted. The
362 * RHS of the target outer join will be made empty here, but that's OK
363 * since caller will delete that SpecialJoinInfo entirely.
364 */
365 foreach(l, root->join_info_list)
366 {
367 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
368
369 sjinfo->min_lefthand = bms_del_member(sjinfo->min_lefthand, relid);
370 sjinfo->min_righthand = bms_del_member(sjinfo->min_righthand, relid);
371 sjinfo->syn_lefthand = bms_del_member(sjinfo->syn_lefthand, relid);
372 sjinfo->syn_righthand = bms_del_member(sjinfo->syn_righthand, relid);
373 }
374
375 /*
376 * Likewise remove references from PlaceHolderVar data structures,
377 * removing any no-longer-needed placeholders entirely.
378 *
379 * Removal is a bit tricker than it might seem: we can remove PHVs that
380 * are used at the target rel and/or in the join qual, but not those that
381 * are used at join partner rels or above the join. It's not that easy to
382 * distinguish PHVs used at partner rels from those used in the join qual,
383 * since they will both have ph_needed sets that are subsets of
384 * joinrelids. However, a PHV used at a partner rel could not have the
385 * target rel in ph_eval_at, so we check that while deciding whether to
386 * remove or just update the PHV. There is no corresponding test in
387 * join_is_removable because it doesn't need to distinguish those cases.
388 */
389 for (l = list_head(root->placeholder_list); l != NULL; l = nextl)
390 {
391 PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
392
393 nextl = lnext(l);
394 Assert(!bms_is_member(relid, phinfo->ph_lateral));
395 if (bms_is_subset(phinfo->ph_needed, joinrelids) &&
396 bms_is_member(relid, phinfo->ph_eval_at))
397 root->placeholder_list = list_delete_ptr(root->placeholder_list,
398 phinfo);
399 else
400 {
401 phinfo->ph_eval_at = bms_del_member(phinfo->ph_eval_at, relid);
402 Assert(!bms_is_empty(phinfo->ph_eval_at));
403 phinfo->ph_needed = bms_del_member(phinfo->ph_needed, relid);
404 }
405 }
406
407 /*
408 * Remove any joinquals referencing the rel from the joininfo lists.
409 *
410 * In some cases, a joinqual has to be put back after deleting its
411 * reference to the target rel. This can occur for pseudoconstant and
412 * outerjoin-delayed quals, which can get marked as requiring the rel in
413 * order to force them to be evaluated at or above the join. We can't
414 * just discard them, though. Only quals that logically belonged to the
415 * outer join being discarded should be removed from the query.
416 *
417 * We must make a copy of the rel's old joininfo list before starting the
418 * loop, because otherwise remove_join_clause_from_rels would destroy the
419 * list while we're scanning it.
420 */
421 joininfos = list_copy(rel->joininfo);
422 foreach(l, joininfos)
423 {
424 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
425
426 remove_join_clause_from_rels(root, rinfo, rinfo->required_relids);
427
428 if (RINFO_IS_PUSHED_DOWN(rinfo, joinrelids))
429 {
430 /* Recheck that qual doesn't actually reference the target rel */
431 Assert(!bms_is_member(relid, rinfo->clause_relids));
432
433 /*
434 * The required_relids probably aren't shared with anything else,
435 * but let's copy them just to be sure.
436 */
437 rinfo->required_relids = bms_copy(rinfo->required_relids);
438 rinfo->required_relids = bms_del_member(rinfo->required_relids,
439 relid);
440 distribute_restrictinfo_to_rels(root, rinfo);
441 }
442 }
443
444 /*
445 * There may be references to the rel in root->fkey_list, but if so,
446 * match_foreign_keys_to_quals() will get rid of them.
447 */
448 }
449
450 /*
451 * Remove any occurrences of the target relid from a joinlist structure.
452 *
453 * It's easiest to build a whole new list structure, so we handle it that
454 * way. Efficiency is not a big deal here.
455 *
456 * *nremoved is incremented by the number of occurrences removed (there
457 * should be exactly one, but the caller checks that).
458 */
459 static List *
remove_rel_from_joinlist(List * joinlist,int relid,int * nremoved)460 remove_rel_from_joinlist(List *joinlist, int relid, int *nremoved)
461 {
462 List *result = NIL;
463 ListCell *jl;
464
465 foreach(jl, joinlist)
466 {
467 Node *jlnode = (Node *) lfirst(jl);
468
469 if (IsA(jlnode, RangeTblRef))
470 {
471 int varno = ((RangeTblRef *) jlnode)->rtindex;
472
473 if (varno == relid)
474 (*nremoved)++;
475 else
476 result = lappend(result, jlnode);
477 }
478 else if (IsA(jlnode, List))
479 {
480 /* Recurse to handle subproblem */
481 List *sublist;
482
483 sublist = remove_rel_from_joinlist((List *) jlnode,
484 relid, nremoved);
485 /* Avoid including empty sub-lists in the result */
486 if (sublist)
487 result = lappend(result, sublist);
488 }
489 else
490 {
491 elog(ERROR, "unrecognized joinlist node type: %d",
492 (int) nodeTag(jlnode));
493 }
494 }
495
496 return result;
497 }
498
499
500 /*
501 * reduce_unique_semijoins
502 * Check for semijoins that can be simplified to plain inner joins
503 * because the inner relation is provably unique for the join clauses.
504 *
505 * Ideally this would happen during reduce_outer_joins, but we don't have
506 * enough information at that point.
507 *
508 * To perform the strength reduction when applicable, we need only delete
509 * the semijoin's SpecialJoinInfo from root->join_info_list. (We don't
510 * bother fixing the join type attributed to it in the query jointree,
511 * since that won't be consulted again.)
512 */
513 void
reduce_unique_semijoins(PlannerInfo * root)514 reduce_unique_semijoins(PlannerInfo *root)
515 {
516 ListCell *lc;
517 ListCell *next;
518
519 /*
520 * Scan the join_info_list to find semijoins. We can't use foreach
521 * because we may delete the current cell.
522 */
523 for (lc = list_head(root->join_info_list); lc != NULL; lc = next)
524 {
525 SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
526 int innerrelid;
527 RelOptInfo *innerrel;
528 Relids joinrelids;
529 List *restrictlist;
530
531 next = lnext(lc);
532
533 /*
534 * Must be a non-delaying semijoin to a single baserel, else we aren't
535 * going to be able to do anything with it. (It's probably not
536 * possible for delay_upper_joins to be set on a semijoin, but we
537 * might as well check.)
538 */
539 if (sjinfo->jointype != JOIN_SEMI ||
540 sjinfo->delay_upper_joins)
541 continue;
542
543 if (!bms_get_singleton_member(sjinfo->min_righthand, &innerrelid))
544 continue;
545
546 innerrel = find_base_rel(root, innerrelid);
547
548 /*
549 * Before we trouble to run generate_join_implied_equalities, make a
550 * quick check to eliminate cases in which we will surely be unable to
551 * prove uniqueness of the innerrel.
552 */
553 if (!rel_supports_distinctness(root, innerrel))
554 continue;
555
556 /* Compute the relid set for the join we are considering */
557 joinrelids = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
558
559 /*
560 * Since we're only considering a single-rel RHS, any join clauses it
561 * has must be clauses linking it to the semijoin's min_lefthand. We
562 * can also consider EC-derived join clauses.
563 */
564 restrictlist =
565 list_concat(generate_join_implied_equalities(root,
566 joinrelids,
567 sjinfo->min_lefthand,
568 innerrel),
569 innerrel->joininfo);
570
571 /* Test whether the innerrel is unique for those clauses. */
572 if (!innerrel_is_unique(root,
573 joinrelids, sjinfo->min_lefthand, innerrel,
574 JOIN_SEMI, restrictlist, true))
575 continue;
576
577 /* OK, remove the SpecialJoinInfo from the list. */
578 root->join_info_list = list_delete_ptr(root->join_info_list, sjinfo);
579 }
580 }
581
582
583 /*
584 * rel_supports_distinctness
585 * Could the relation possibly be proven distinct on some set of columns?
586 *
587 * This is effectively a pre-checking function for rel_is_distinct_for().
588 * It must return true if rel_is_distinct_for() could possibly return true
589 * with this rel, but it should not expend a lot of cycles. The idea is
590 * that callers can avoid doing possibly-expensive processing to compute
591 * rel_is_distinct_for()'s argument lists if the call could not possibly
592 * succeed.
593 */
594 static bool
rel_supports_distinctness(PlannerInfo * root,RelOptInfo * rel)595 rel_supports_distinctness(PlannerInfo *root, RelOptInfo *rel)
596 {
597 /* We only know about baserels ... */
598 if (rel->reloptkind != RELOPT_BASEREL)
599 return false;
600 if (rel->rtekind == RTE_RELATION)
601 {
602 /*
603 * For a plain relation, we only know how to prove uniqueness by
604 * reference to unique indexes. Make sure there's at least one
605 * suitable unique index. It must be immediately enforced, and if
606 * it's a partial index, it must match the query. (Keep these
607 * conditions in sync with relation_has_unique_index_for!)
608 */
609 ListCell *lc;
610
611 foreach(lc, rel->indexlist)
612 {
613 IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc);
614
615 if (ind->unique && ind->immediate &&
616 (ind->indpred == NIL || ind->predOK))
617 return true;
618 }
619 }
620 else if (rel->rtekind == RTE_SUBQUERY)
621 {
622 Query *subquery = root->simple_rte_array[rel->relid]->subquery;
623
624 /* Check if the subquery has any qualities that support distinctness */
625 if (query_supports_distinctness(subquery))
626 return true;
627 }
628 /* We have no proof rules for any other rtekinds. */
629 return false;
630 }
631
632 /*
633 * rel_is_distinct_for
634 * Does the relation return only distinct rows according to clause_list?
635 *
636 * clause_list is a list of join restriction clauses involving this rel and
637 * some other one. Return true if no two rows emitted by this rel could
638 * possibly join to the same row of the other rel.
639 *
640 * The caller must have already determined that each condition is a
641 * mergejoinable equality with an expression in this relation on one side, and
642 * an expression not involving this relation on the other. The transient
643 * outer_is_left flag is used to identify which side references this relation:
644 * left side if outer_is_left is false, right side if it is true.
645 *
646 * Note that the passed-in clause_list may be destructively modified! This
647 * is OK for current uses, because the clause_list is built by the caller for
648 * the sole purpose of passing to this function.
649 */
650 static bool
rel_is_distinct_for(PlannerInfo * root,RelOptInfo * rel,List * clause_list)651 rel_is_distinct_for(PlannerInfo *root, RelOptInfo *rel, List *clause_list)
652 {
653 /*
654 * We could skip a couple of tests here if we assume all callers checked
655 * rel_supports_distinctness first, but it doesn't seem worth taking any
656 * risk for.
657 */
658 if (rel->reloptkind != RELOPT_BASEREL)
659 return false;
660 if (rel->rtekind == RTE_RELATION)
661 {
662 /*
663 * Examine the indexes to see if we have a matching unique index.
664 * relation_has_unique_index_for automatically adds any usable
665 * restriction clauses for the rel, so we needn't do that here.
666 */
667 if (relation_has_unique_index_for(root, rel, clause_list, NIL, NIL))
668 return true;
669 }
670 else if (rel->rtekind == RTE_SUBQUERY)
671 {
672 Index relid = rel->relid;
673 Query *subquery = root->simple_rte_array[relid]->subquery;
674 List *colnos = NIL;
675 List *opids = NIL;
676 ListCell *l;
677
678 /*
679 * Build the argument lists for query_is_distinct_for: a list of
680 * output column numbers that the query needs to be distinct over, and
681 * a list of equality operators that the output columns need to be
682 * distinct according to.
683 *
684 * (XXX we are not considering restriction clauses attached to the
685 * subquery; is that worth doing?)
686 */
687 foreach(l, clause_list)
688 {
689 RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
690 Oid op;
691 Var *var;
692
693 /*
694 * Get the equality operator we need uniqueness according to.
695 * (This might be a cross-type operator and thus not exactly the
696 * same operator the subquery would consider; that's all right
697 * since query_is_distinct_for can resolve such cases.) The
698 * caller's mergejoinability test should have selected only
699 * OpExprs.
700 */
701 op = castNode(OpExpr, rinfo->clause)->opno;
702
703 /* caller identified the inner side for us */
704 if (rinfo->outer_is_left)
705 var = (Var *) get_rightop(rinfo->clause);
706 else
707 var = (Var *) get_leftop(rinfo->clause);
708
709 /*
710 * We may ignore any RelabelType node above the operand. (There
711 * won't be more than one, since eval_const_expressions() has been
712 * applied already.)
713 */
714 if (var && IsA(var, RelabelType))
715 var = (Var *) ((RelabelType *) var)->arg;
716
717 /*
718 * If inner side isn't a Var referencing a subquery output column,
719 * this clause doesn't help us.
720 */
721 if (!var || !IsA(var, Var) ||
722 var->varno != relid || var->varlevelsup != 0)
723 continue;
724
725 colnos = lappend_int(colnos, var->varattno);
726 opids = lappend_oid(opids, op);
727 }
728
729 if (query_is_distinct_for(subquery, colnos, opids))
730 return true;
731 }
732 return false;
733 }
734
735
736 /*
737 * query_supports_distinctness - could the query possibly be proven distinct
738 * on some set of output columns?
739 *
740 * This is effectively a pre-checking function for query_is_distinct_for().
741 * It must return true if query_is_distinct_for() could possibly return true
742 * with this query, but it should not expend a lot of cycles. The idea is
743 * that callers can avoid doing possibly-expensive processing to compute
744 * query_is_distinct_for()'s argument lists if the call could not possibly
745 * succeed.
746 */
747 bool
query_supports_distinctness(Query * query)748 query_supports_distinctness(Query *query)
749 {
750 /* SRFs break distinctness except with DISTINCT, see below */
751 if (query->hasTargetSRFs && query->distinctClause == NIL)
752 return false;
753
754 /* check for features we can prove distinctness with */
755 if (query->distinctClause != NIL ||
756 query->groupClause != NIL ||
757 query->groupingSets != NIL ||
758 query->hasAggs ||
759 query->havingQual ||
760 query->setOperations)
761 return true;
762
763 return false;
764 }
765
766 /*
767 * query_is_distinct_for - does query never return duplicates of the
768 * specified columns?
769 *
770 * query is a not-yet-planned subquery (in current usage, it's always from
771 * a subquery RTE, which the planner avoids scribbling on).
772 *
773 * colnos is an integer list of output column numbers (resno's). We are
774 * interested in whether rows consisting of just these columns are certain
775 * to be distinct. "Distinctness" is defined according to whether the
776 * corresponding upper-level equality operators listed in opids would think
777 * the values are distinct. (Note: the opids entries could be cross-type
778 * operators, and thus not exactly the equality operators that the subquery
779 * would use itself. We use equality_ops_are_compatible() to check
780 * compatibility. That looks at btree or hash opfamily membership, and so
781 * should give trustworthy answers for all operators that we might need
782 * to deal with here.)
783 */
784 bool
query_is_distinct_for(Query * query,List * colnos,List * opids)785 query_is_distinct_for(Query *query, List *colnos, List *opids)
786 {
787 ListCell *l;
788 Oid opid;
789
790 Assert(list_length(colnos) == list_length(opids));
791
792 /*
793 * DISTINCT (including DISTINCT ON) guarantees uniqueness if all the
794 * columns in the DISTINCT clause appear in colnos and operator semantics
795 * match. This is true even if there are SRFs in the DISTINCT columns or
796 * elsewhere in the tlist.
797 */
798 if (query->distinctClause)
799 {
800 foreach(l, query->distinctClause)
801 {
802 SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
803 TargetEntry *tle = get_sortgroupclause_tle(sgc,
804 query->targetList);
805
806 opid = distinct_col_search(tle->resno, colnos, opids);
807 if (!OidIsValid(opid) ||
808 !equality_ops_are_compatible(opid, sgc->eqop))
809 break; /* exit early if no match */
810 }
811 if (l == NULL) /* had matches for all? */
812 return true;
813 }
814
815 /*
816 * Otherwise, a set-returning function in the query's targetlist can
817 * result in returning duplicate rows, despite any grouping that might
818 * occur before tlist evaluation. (If all tlist SRFs are within GROUP BY
819 * columns, it would be safe because they'd be expanded before grouping.
820 * But it doesn't currently seem worth the effort to check for that.)
821 */
822 if (query->hasTargetSRFs)
823 return false;
824
825 /*
826 * Similarly, GROUP BY without GROUPING SETS guarantees uniqueness if all
827 * the grouped columns appear in colnos and operator semantics match.
828 */
829 if (query->groupClause && !query->groupingSets)
830 {
831 foreach(l, query->groupClause)
832 {
833 SortGroupClause *sgc = (SortGroupClause *) lfirst(l);
834 TargetEntry *tle = get_sortgroupclause_tle(sgc,
835 query->targetList);
836
837 opid = distinct_col_search(tle->resno, colnos, opids);
838 if (!OidIsValid(opid) ||
839 !equality_ops_are_compatible(opid, sgc->eqop))
840 break; /* exit early if no match */
841 }
842 if (l == NULL) /* had matches for all? */
843 return true;
844 }
845 else if (query->groupingSets)
846 {
847 /*
848 * If we have grouping sets with expressions, we probably don't have
849 * uniqueness and analysis would be hard. Punt.
850 */
851 if (query->groupClause)
852 return false;
853
854 /*
855 * If we have no groupClause (therefore no grouping expressions), we
856 * might have one or many empty grouping sets. If there's just one,
857 * then we're returning only one row and are certainly unique. But
858 * otherwise, we know we're certainly not unique.
859 */
860 if (list_length(query->groupingSets) == 1 &&
861 ((GroupingSet *) linitial(query->groupingSets))->kind == GROUPING_SET_EMPTY)
862 return true;
863 else
864 return false;
865 }
866 else
867 {
868 /*
869 * If we have no GROUP BY, but do have aggregates or HAVING, then the
870 * result is at most one row so it's surely unique, for any operators.
871 */
872 if (query->hasAggs || query->havingQual)
873 return true;
874 }
875
876 /*
877 * UNION, INTERSECT, EXCEPT guarantee uniqueness of the whole output row,
878 * except with ALL.
879 */
880 if (query->setOperations)
881 {
882 SetOperationStmt *topop = castNode(SetOperationStmt, query->setOperations);
883
884 Assert(topop->op != SETOP_NONE);
885
886 if (!topop->all)
887 {
888 ListCell *lg;
889
890 /* We're good if all the nonjunk output columns are in colnos */
891 lg = list_head(topop->groupClauses);
892 foreach(l, query->targetList)
893 {
894 TargetEntry *tle = (TargetEntry *) lfirst(l);
895 SortGroupClause *sgc;
896
897 if (tle->resjunk)
898 continue; /* ignore resjunk columns */
899
900 /* non-resjunk columns should have grouping clauses */
901 Assert(lg != NULL);
902 sgc = (SortGroupClause *) lfirst(lg);
903 lg = lnext(lg);
904
905 opid = distinct_col_search(tle->resno, colnos, opids);
906 if (!OidIsValid(opid) ||
907 !equality_ops_are_compatible(opid, sgc->eqop))
908 break; /* exit early if no match */
909 }
910 if (l == NULL) /* had matches for all? */
911 return true;
912 }
913 }
914
915 /*
916 * XXX Are there any other cases in which we can easily see the result
917 * must be distinct?
918 *
919 * If you do add more smarts to this function, be sure to update
920 * query_supports_distinctness() to match.
921 */
922
923 return false;
924 }
925
926 /*
927 * distinct_col_search - subroutine for query_is_distinct_for
928 *
929 * If colno is in colnos, return the corresponding element of opids,
930 * else return InvalidOid. (Ordinarily colnos would not contain duplicates,
931 * but if it does, we arbitrarily select the first match.)
932 */
933 static Oid
distinct_col_search(int colno,List * colnos,List * opids)934 distinct_col_search(int colno, List *colnos, List *opids)
935 {
936 ListCell *lc1,
937 *lc2;
938
939 forboth(lc1, colnos, lc2, opids)
940 {
941 if (colno == lfirst_int(lc1))
942 return lfirst_oid(lc2);
943 }
944 return InvalidOid;
945 }
946
947
948 /*
949 * innerrel_is_unique
950 * Check if the innerrel provably contains at most one tuple matching any
951 * tuple from the outerrel, based on join clauses in the 'restrictlist'.
952 *
953 * We need an actual RelOptInfo for the innerrel, but it's sufficient to
954 * identify the outerrel by its Relids. This asymmetry supports use of this
955 * function before joinrels have been built. (The caller is expected to
956 * also supply the joinrelids, just to save recalculating that.)
957 *
958 * The proof must be made based only on clauses that will be "joinquals"
959 * rather than "otherquals" at execution. For an inner join there's no
960 * difference; but if the join is outer, we must ignore pushed-down quals,
961 * as those will become "otherquals". Note that this means the answer might
962 * vary depending on whether IS_OUTER_JOIN(jointype); since we cache the
963 * answer without regard to that, callers must take care not to call this
964 * with jointypes that would be classified differently by IS_OUTER_JOIN().
965 *
966 * The actual proof is undertaken by is_innerrel_unique_for(); this function
967 * is a frontend that is mainly concerned with caching the answers.
968 * In particular, the force_cache argument allows overriding the internal
969 * heuristic about whether to cache negative answers; it should be "true"
970 * if making an inquiry that is not part of the normal bottom-up join search
971 * sequence.
972 */
973 bool
innerrel_is_unique(PlannerInfo * root,Relids joinrelids,Relids outerrelids,RelOptInfo * innerrel,JoinType jointype,List * restrictlist,bool force_cache)974 innerrel_is_unique(PlannerInfo *root,
975 Relids joinrelids,
976 Relids outerrelids,
977 RelOptInfo *innerrel,
978 JoinType jointype,
979 List *restrictlist,
980 bool force_cache)
981 {
982 MemoryContext old_context;
983 ListCell *lc;
984
985 /* Certainly can't prove uniqueness when there are no joinclauses */
986 if (restrictlist == NIL)
987 return false;
988
989 /*
990 * Make a quick check to eliminate cases in which we will surely be unable
991 * to prove uniqueness of the innerrel.
992 */
993 if (!rel_supports_distinctness(root, innerrel))
994 return false;
995
996 /*
997 * Query the cache to see if we've managed to prove that innerrel is
998 * unique for any subset of this outerrel. We don't need an exact match,
999 * as extra outerrels can't make the innerrel any less unique (or more
1000 * formally, the restrictlist for a join to a superset outerrel must be a
1001 * superset of the conditions we successfully used before).
1002 */
1003 foreach(lc, innerrel->unique_for_rels)
1004 {
1005 Relids unique_for_rels = (Relids) lfirst(lc);
1006
1007 if (bms_is_subset(unique_for_rels, outerrelids))
1008 return true; /* Success! */
1009 }
1010
1011 /*
1012 * Conversely, we may have already determined that this outerrel, or some
1013 * superset thereof, cannot prove this innerrel to be unique.
1014 */
1015 foreach(lc, innerrel->non_unique_for_rels)
1016 {
1017 Relids unique_for_rels = (Relids) lfirst(lc);
1018
1019 if (bms_is_subset(outerrelids, unique_for_rels))
1020 return false;
1021 }
1022
1023 /* No cached information, so try to make the proof. */
1024 if (is_innerrel_unique_for(root, joinrelids, outerrelids, innerrel,
1025 jointype, restrictlist))
1026 {
1027 /*
1028 * Cache the positive result for future probes, being sure to keep it
1029 * in the planner_cxt even if we are working in GEQO.
1030 *
1031 * Note: one might consider trying to isolate the minimal subset of
1032 * the outerrels that proved the innerrel unique. But it's not worth
1033 * the trouble, because the planner builds up joinrels incrementally
1034 * and so we'll see the minimally sufficient outerrels before any
1035 * supersets of them anyway.
1036 */
1037 old_context = MemoryContextSwitchTo(root->planner_cxt);
1038 innerrel->unique_for_rels = lappend(innerrel->unique_for_rels,
1039 bms_copy(outerrelids));
1040 MemoryContextSwitchTo(old_context);
1041
1042 return true; /* Success! */
1043 }
1044 else
1045 {
1046 /*
1047 * None of the join conditions for outerrel proved innerrel unique, so
1048 * we can safely reject this outerrel or any subset of it in future
1049 * checks.
1050 *
1051 * However, in normal planning mode, caching this knowledge is totally
1052 * pointless; it won't be queried again, because we build up joinrels
1053 * from smaller to larger. It is useful in GEQO mode, where the
1054 * knowledge can be carried across successive planning attempts; and
1055 * it's likely to be useful when using join-search plugins, too. Hence
1056 * cache when join_search_private is non-NULL. (Yeah, that's a hack,
1057 * but it seems reasonable.)
1058 *
1059 * Also, allow callers to override that heuristic and force caching;
1060 * that's useful for reduce_unique_semijoins, which calls here before
1061 * the normal join search starts.
1062 */
1063 if (force_cache || root->join_search_private)
1064 {
1065 old_context = MemoryContextSwitchTo(root->planner_cxt);
1066 innerrel->non_unique_for_rels =
1067 lappend(innerrel->non_unique_for_rels,
1068 bms_copy(outerrelids));
1069 MemoryContextSwitchTo(old_context);
1070 }
1071
1072 return false;
1073 }
1074 }
1075
1076 /*
1077 * is_innerrel_unique_for
1078 * Check if the innerrel provably contains at most one tuple matching any
1079 * tuple from the outerrel, based on join clauses in the 'restrictlist'.
1080 */
1081 static bool
is_innerrel_unique_for(PlannerInfo * root,Relids joinrelids,Relids outerrelids,RelOptInfo * innerrel,JoinType jointype,List * restrictlist)1082 is_innerrel_unique_for(PlannerInfo *root,
1083 Relids joinrelids,
1084 Relids outerrelids,
1085 RelOptInfo *innerrel,
1086 JoinType jointype,
1087 List *restrictlist)
1088 {
1089 List *clause_list = NIL;
1090 ListCell *lc;
1091
1092 /*
1093 * Search for mergejoinable clauses that constrain the inner rel against
1094 * the outer rel. If an operator is mergejoinable then it behaves like
1095 * equality for some btree opclass, so it's what we want. The
1096 * mergejoinability test also eliminates clauses containing volatile
1097 * functions, which we couldn't depend on.
1098 */
1099 foreach(lc, restrictlist)
1100 {
1101 RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc);
1102
1103 /*
1104 * As noted above, if it's a pushed-down clause and we're at an outer
1105 * join, we can't use it.
1106 */
1107 if (IS_OUTER_JOIN(jointype) &&
1108 RINFO_IS_PUSHED_DOWN(restrictinfo, joinrelids))
1109 continue;
1110
1111 /* Ignore if it's not a mergejoinable clause */
1112 if (!restrictinfo->can_join ||
1113 restrictinfo->mergeopfamilies == NIL)
1114 continue; /* not mergejoinable */
1115
1116 /*
1117 * Check if clause has the form "outer op inner" or "inner op outer",
1118 * and if so mark which side is inner.
1119 */
1120 if (!clause_sides_match_join(restrictinfo, outerrelids,
1121 innerrel->relids))
1122 continue; /* no good for these input relations */
1123
1124 /* OK, add to list */
1125 clause_list = lappend(clause_list, restrictinfo);
1126 }
1127
1128 /* Let rel_is_distinct_for() do the hard work */
1129 return rel_is_distinct_for(root, innerrel, clause_list);
1130 }
1131