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