1/*-------------------------------------------------------------------------
2 *
3 * relnode.c
4 * Relation-node lookup/construction routines
5 *
6 * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
8 *
9 *
10 * IDENTIFICATION
11 * src/backend/optimizer/util/relnode.c
12 *
13 *-------------------------------------------------------------------------
14 */
15#include "postgres.h"
16
17#include <limits.h>
18
19#include "miscadmin.h"
20#include "optimizer/appendinfo.h"
21#include "optimizer/clauses.h"
22#include "optimizer/cost.h"
23#include "optimizer/inherit.h"
24#include "optimizer/pathnode.h"
25#include "optimizer/paths.h"
26#include "optimizer/placeholder.h"
27#include "optimizer/plancat.h"
28#include "optimizer/restrictinfo.h"
29#include "optimizer/tlist.h"
30#include "partitioning/partbounds.h"
31#include "utils/hsearch.h"
32
33
34typedef struct JoinHashEntry
35{
36 Relids join_relids; /* hash key --- MUST BE FIRST */
37 RelOptInfo *join_rel;
38} JoinHashEntry;
39
40static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
41 RelOptInfo *input_rel);
42static List *build_joinrel_restrictlist(PlannerInfo *root,
43 RelOptInfo *joinrel,
44 RelOptInfo *outer_rel,
45 RelOptInfo *inner_rel);
46static void build_joinrel_joinlist(RelOptInfo *joinrel,
47 RelOptInfo *outer_rel,
48 RelOptInfo *inner_rel);
49static List *subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
50 List *joininfo_list,
51 List *new_restrictlist);
52static List *subbuild_joinrel_joinlist(RelOptInfo *joinrel,
53 List *joininfo_list,
54 List *new_joininfo);
55static void set_foreign_rel_properties(RelOptInfo *joinrel,
56 RelOptInfo *outer_rel, RelOptInfo *inner_rel);
57static void add_join_rel(PlannerInfo *root, RelOptInfo *joinrel);
58static void build_joinrel_partition_info(RelOptInfo *joinrel,
59 RelOptInfo *outer_rel, RelOptInfo *inner_rel,
60 List *restrictlist, JoinType jointype);
61static void build_child_join_reltarget(PlannerInfo *root,
62 RelOptInfo *parentrel,
63 RelOptInfo *childrel,
64 int nappinfos,
65 AppendRelInfo **appinfos);
66
67
68/*
69 * setup_simple_rel_arrays
70 * Prepare the arrays we use for quickly accessing base relations.
71 */
72void
73setup_simple_rel_arrays(PlannerInfo *root)
74{
75 Index rti;
76 ListCell *lc;
77
78 /* Arrays are accessed using RT indexes (1..N) */
79 root->simple_rel_array_size = list_length(root->parse->rtable) + 1;
80
81 /* simple_rel_array is initialized to all NULLs */
82 root->simple_rel_array = (RelOptInfo **)
83 palloc0(root->simple_rel_array_size * sizeof(RelOptInfo *));
84
85 /* simple_rte_array is an array equivalent of the rtable list */
86 root->simple_rte_array = (RangeTblEntry **)
87 palloc0(root->simple_rel_array_size * sizeof(RangeTblEntry *));
88 rti = 1;
89 foreach(lc, root->parse->rtable)
90 {
91 RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
92
93 root->simple_rte_array[rti++] = rte;
94 }
95}
96
97/*
98 * setup_append_rel_array
99 * Populate the append_rel_array to allow direct lookups of
100 * AppendRelInfos by child relid.
101 *
102 * The array remains unallocated if there are no AppendRelInfos.
103 */
104void
105setup_append_rel_array(PlannerInfo *root)
106{
107 ListCell *lc;
108 int size = list_length(root->parse->rtable) + 1;
109
110 if (root->append_rel_list == NIL)
111 {
112 root->append_rel_array = NULL;
113 return;
114 }
115
116 root->append_rel_array = (AppendRelInfo **)
117 palloc0(size * sizeof(AppendRelInfo *));
118
119 foreach(lc, root->append_rel_list)
120 {
121 AppendRelInfo *appinfo = lfirst_node(AppendRelInfo, lc);
122 int child_relid = appinfo->child_relid;
123
124 /* Sanity check */
125 Assert(child_relid < size);
126
127 if (root->append_rel_array[child_relid])
128 elog(ERROR, "child relation already exists");
129
130 root->append_rel_array[child_relid] = appinfo;
131 }
132}
133
134/*
135 * expand_planner_arrays
136 * Expand the PlannerInfo's per-RTE arrays by add_size members
137 * and initialize the newly added entries to NULLs
138 */
139void
140expand_planner_arrays(PlannerInfo *root, int add_size)
141{
142 int new_size;
143
144 Assert(add_size > 0);
145
146 new_size = root->simple_rel_array_size + add_size;
147
148 root->simple_rte_array = (RangeTblEntry **)
149 repalloc(root->simple_rte_array,
150 sizeof(RangeTblEntry *) * new_size);
151 MemSet(root->simple_rte_array + root->simple_rel_array_size,
152 0, sizeof(RangeTblEntry *) * add_size);
153
154 root->simple_rel_array = (RelOptInfo **)
155 repalloc(root->simple_rel_array,
156 sizeof(RelOptInfo *) * new_size);
157 MemSet(root->simple_rel_array + root->simple_rel_array_size,
158 0, sizeof(RelOptInfo *) * add_size);
159
160 if (root->append_rel_array)
161 {
162 root->append_rel_array = (AppendRelInfo **)
163 repalloc(root->append_rel_array,
164 sizeof(AppendRelInfo *) * new_size);
165 MemSet(root->append_rel_array + root->simple_rel_array_size,
166 0, sizeof(AppendRelInfo *) * add_size);
167 }
168 else
169 {
170 root->append_rel_array = (AppendRelInfo **)
171 palloc0(sizeof(AppendRelInfo *) * new_size);
172 }
173
174 root->simple_rel_array_size = new_size;
175}
176
177/*
178 * build_simple_rel
179 * Construct a new RelOptInfo for a base relation or 'other' relation.
180 */
181RelOptInfo *
182build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
183{
184 RelOptInfo *rel;
185 RangeTblEntry *rte;
186
187 /* Rel should not exist already */
188 Assert(relid > 0 && relid < root->simple_rel_array_size);
189 if (root->simple_rel_array[relid] != NULL)
190 elog(ERROR, "rel %d already exists", relid);
191
192 /* Fetch RTE for relation */
193 rte = root->simple_rte_array[relid];
194 Assert(rte != NULL);
195
196 rel = makeNode(RelOptInfo);
197 rel->reloptkind = parent ? RELOPT_OTHER_MEMBER_REL : RELOPT_BASEREL;
198 rel->relids = bms_make_singleton(relid);
199 rel->rows = 0;
200 /* cheap startup cost is interesting iff not all tuples to be retrieved */
201 rel->consider_startup = (root->tuple_fraction > 0);
202 rel->consider_param_startup = false; /* might get changed later */
203 rel->consider_parallel = false; /* might get changed later */
204 rel->reltarget = create_empty_pathtarget();
205 rel->pathlist = NIL;
206 rel->ppilist = NIL;
207 rel->partial_pathlist = NIL;
208 rel->cheapest_startup_path = NULL;
209 rel->cheapest_total_path = NULL;
210 rel->cheapest_unique_path = NULL;
211 rel->cheapest_parameterized_paths = NIL;
212 rel->relid = relid;
213 rel->rtekind = rte->rtekind;
214 /* min_attr, max_attr, attr_needed, attr_widths are set below */
215 rel->lateral_vars = NIL;
216 rel->indexlist = NIL;
217 rel->statlist = NIL;
218 rel->pages = 0;
219 rel->tuples = 0;
220 rel->allvisfrac = 0;
221 rel->subroot = NULL;
222 rel->subplan_params = NIL;
223 rel->rel_parallel_workers = -1; /* set up in get_relation_info */
224 rel->serverid = InvalidOid;
225 rel->userid = rte->checkAsUser;
226 rel->useridiscurrent = false;
227 rel->fdwroutine = NULL;
228 rel->fdw_private = NULL;
229 rel->unique_for_rels = NIL;
230 rel->non_unique_for_rels = NIL;
231 rel->baserestrictinfo = NIL;
232 rel->baserestrictcost.startup = 0;
233 rel->baserestrictcost.per_tuple = 0;
234 rel->baserestrict_min_security = UINT_MAX;
235 rel->joininfo = NIL;
236 rel->has_eclass_joins = false;
237 rel->consider_partitionwise_join = false; /* might get changed later */
238 rel->part_scheme = NULL;
239 rel->nparts = 0;
240 rel->boundinfo = NULL;
241 rel->partition_qual = NIL;
242 rel->part_rels = NULL;
243 rel->partexprs = NULL;
244 rel->nullable_partexprs = NULL;
245 rel->partitioned_child_rels = NIL;
246
247 /*
248 * Pass assorted information down the inheritance hierarchy.
249 */
250 if (parent)
251 {
252 /*
253 * Each direct or indirect child wants to know the relids of its
254 * topmost parent.
255 */
256 if (parent->top_parent_relids)
257 rel->top_parent_relids = parent->top_parent_relids;
258 else
259 rel->top_parent_relids = bms_copy(parent->relids);
260
261 /*
262 * Also propagate lateral-reference information from appendrel parent
263 * rels to their child rels. We intentionally give each child rel the
264 * same minimum parameterization, even though it's quite possible that
265 * some don't reference all the lateral rels. This is because any
266 * append path for the parent will have to have the same
267 * parameterization for every child anyway, and there's no value in
268 * forcing extra reparameterize_path() calls. Similarly, a lateral
269 * reference to the parent prevents use of otherwise-movable join rels
270 * for each child.
271 *
272 * It's possible for child rels to have their own children, in which
273 * case the topmost parent's lateral info propagates all the way down.
274 */
275 rel->direct_lateral_relids = parent->direct_lateral_relids;
276 rel->lateral_relids = parent->lateral_relids;
277 rel->lateral_referencers = parent->lateral_referencers;
278 }
279 else
280 {
281 rel->top_parent_relids = NULL;
282 rel->direct_lateral_relids = NULL;
283 rel->lateral_relids = NULL;
284 rel->lateral_referencers = NULL;
285 }
286
287 /* Check type of rtable entry */
288 switch (rte->rtekind)
289 {
290 case RTE_RELATION:
291 /* Table --- retrieve statistics from the system catalogs */
292 get_relation_info(root, rte->relid, rte->inh, rel);
293 break;
294 case RTE_SUBQUERY:
295 case RTE_FUNCTION:
296 case RTE_TABLEFUNC:
297 case RTE_VALUES:
298 case RTE_CTE:
299 case RTE_NAMEDTUPLESTORE:
300
301 /*
302 * Subquery, function, tablefunc, values list, CTE, or ENR --- set
303 * up attr range and arrays
304 *
305 * Note: 0 is included in range to support whole-row Vars
306 */
307 rel->min_attr = 0;
308 rel->max_attr = list_length(rte->eref->colnames);
309 rel->attr_needed = (Relids *)
310 palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(Relids));
311 rel->attr_widths = (int32 *)
312 palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(int32));
313 break;
314 case RTE_RESULT:
315 /* RTE_RESULT has no columns, nor could it have whole-row Var */
316 rel->min_attr = 0;
317 rel->max_attr = -1;
318 rel->attr_needed = NULL;
319 rel->attr_widths = NULL;
320 break;
321 default:
322 elog(ERROR, "unrecognized RTE kind: %d",
323 (int) rte->rtekind);
324 break;
325 }
326
327 /*
328 * Copy the parent's quals to the child, with appropriate substitution of
329 * variables. If any constant false or NULL clauses turn up, we can mark
330 * the child as dummy right away. (We must do this immediately so that
331 * pruning works correctly when recursing in expand_partitioned_rtentry.)
332 */
333 if (parent)
334 {
335 AppendRelInfo *appinfo = root->append_rel_array[relid];
336
337 Assert(appinfo != NULL);
338 if (!apply_child_basequals(root, parent, rel, rte, appinfo))
339 {
340 /*
341 * Some restriction clause reduced to constant FALSE or NULL after
342 * substitution, so this child need not be scanned.
343 */
344 mark_dummy_rel(rel);
345 }
346 }
347
348 /* Save the finished struct in the query's simple_rel_array */
349 root->simple_rel_array[relid] = rel;
350
351 return rel;
352}
353
354/*
355 * find_base_rel
356 * Find a base or other relation entry, which must already exist.
357 */
358RelOptInfo *
359find_base_rel(PlannerInfo *root, int relid)
360{
361 RelOptInfo *rel;
362
363 Assert(relid > 0);
364
365 if (relid < root->simple_rel_array_size)
366 {
367 rel = root->simple_rel_array[relid];
368 if (rel)
369 return rel;
370 }
371
372 elog(ERROR, "no relation entry for relid %d", relid);
373
374 return NULL; /* keep compiler quiet */
375}
376
377/*
378 * build_join_rel_hash
379 * Construct the auxiliary hash table for join relations.
380 */
381static void
382build_join_rel_hash(PlannerInfo *root)
383{
384 HTAB *hashtab;
385 HASHCTL hash_ctl;
386 ListCell *l;
387
388 /* Create the hash table */
389 MemSet(&hash_ctl, 0, sizeof(hash_ctl));
390 hash_ctl.keysize = sizeof(Relids);
391 hash_ctl.entrysize = sizeof(JoinHashEntry);
392 hash_ctl.hash = bitmap_hash;
393 hash_ctl.match = bitmap_match;
394 hash_ctl.hcxt = CurrentMemoryContext;
395 hashtab = hash_create("JoinRelHashTable",
396 256L,
397 &hash_ctl,
398 HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);
399
400 /* Insert all the already-existing joinrels */
401 foreach(l, root->join_rel_list)
402 {
403 RelOptInfo *rel = (RelOptInfo *) lfirst(l);
404 JoinHashEntry *hentry;
405 bool found;
406
407 hentry = (JoinHashEntry *) hash_search(hashtab,
408 &(rel->relids),
409 HASH_ENTER,
410 &found);
411 Assert(!found);
412 hentry->join_rel = rel;
413 }
414
415 root->join_rel_hash = hashtab;
416}
417
418/*
419 * find_join_rel
420 * Returns relation entry corresponding to 'relids' (a set of RT indexes),
421 * or NULL if none exists. This is for join relations.
422 */
423RelOptInfo *
424find_join_rel(PlannerInfo *root, Relids relids)
425{
426 /*
427 * Switch to using hash lookup when list grows "too long". The threshold
428 * is arbitrary and is known only here.
429 */
430 if (!root->join_rel_hash && list_length(root->join_rel_list) > 32)
431 build_join_rel_hash(root);
432
433 /*
434 * Use either hashtable lookup or linear search, as appropriate.
435 *
436 * Note: the seemingly redundant hashkey variable is used to avoid taking
437 * the address of relids; unless the compiler is exceedingly smart, doing
438 * so would force relids out of a register and thus probably slow down the
439 * list-search case.
440 */
441 if (root->join_rel_hash)
442 {
443 Relids hashkey = relids;
444 JoinHashEntry *hentry;
445
446 hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
447 &hashkey,
448 HASH_FIND,
449 NULL);
450 if (hentry)
451 return hentry->join_rel;
452 }
453 else
454 {
455 ListCell *l;
456
457 foreach(l, root->join_rel_list)
458 {
459 RelOptInfo *rel = (RelOptInfo *) lfirst(l);
460
461 if (bms_equal(rel->relids, relids))
462 return rel;
463 }
464 }
465
466 return NULL;
467}
468
469/*
470 * set_foreign_rel_properties
471 * Set up foreign-join fields if outer and inner relation are foreign
472 * tables (or joins) belonging to the same server and assigned to the same
473 * user to check access permissions as.
474 *
475 * In addition to an exact match of userid, we allow the case where one side
476 * has zero userid (implying current user) and the other side has explicit
477 * userid that happens to equal the current user; but in that case, pushdown of
478 * the join is only valid for the current user. The useridiscurrent field
479 * records whether we had to make such an assumption for this join or any
480 * sub-join.
481 *
482 * Otherwise these fields are left invalid, so GetForeignJoinPaths will not be
483 * called for the join relation.
484 *
485 */
486static void
487set_foreign_rel_properties(RelOptInfo *joinrel, RelOptInfo *outer_rel,
488 RelOptInfo *inner_rel)
489{
490 if (OidIsValid(outer_rel->serverid) &&
491 inner_rel->serverid == outer_rel->serverid)
492 {
493 if (inner_rel->userid == outer_rel->userid)
494 {
495 joinrel->serverid = outer_rel->serverid;
496 joinrel->userid = outer_rel->userid;
497 joinrel->useridiscurrent = outer_rel->useridiscurrent || inner_rel->useridiscurrent;
498 joinrel->fdwroutine = outer_rel->fdwroutine;
499 }
500 else if (!OidIsValid(inner_rel->userid) &&
501 outer_rel->userid == GetUserId())
502 {
503 joinrel->serverid = outer_rel->serverid;
504 joinrel->userid = outer_rel->userid;
505 joinrel->useridiscurrent = true;
506 joinrel->fdwroutine = outer_rel->fdwroutine;
507 }
508 else if (!OidIsValid(outer_rel->userid) &&
509 inner_rel->userid == GetUserId())
510 {
511 joinrel->serverid = outer_rel->serverid;
512 joinrel->userid = inner_rel->userid;
513 joinrel->useridiscurrent = true;
514 joinrel->fdwroutine = outer_rel->fdwroutine;
515 }
516 }
517}
518
519/*
520 * add_join_rel
521 * Add given join relation to the list of join relations in the given
522 * PlannerInfo. Also add it to the auxiliary hashtable if there is one.
523 */
524static void
525add_join_rel(PlannerInfo *root, RelOptInfo *joinrel)
526{
527 /* GEQO requires us to append the new joinrel to the end of the list! */
528 root->join_rel_list = lappend(root->join_rel_list, joinrel);
529
530 /* store it into the auxiliary hashtable if there is one. */
531 if (root->join_rel_hash)
532 {
533 JoinHashEntry *hentry;
534 bool found;
535
536 hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
537 &(joinrel->relids),
538 HASH_ENTER,
539 &found);
540 Assert(!found);
541 hentry->join_rel = joinrel;
542 }
543}
544
545/*
546 * build_join_rel
547 * Returns relation entry corresponding to the union of two given rels,
548 * creating a new relation entry if none already exists.
549 *
550 * 'joinrelids' is the Relids set that uniquely identifies the join
551 * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be
552 * joined
553 * 'sjinfo': join context info
554 * 'restrictlist_ptr': result variable. If not NULL, *restrictlist_ptr
555 * receives the list of RestrictInfo nodes that apply to this
556 * particular pair of joinable relations.
557 *
558 * restrictlist_ptr makes the routine's API a little grotty, but it saves
559 * duplicated calculation of the restrictlist...
560 */
561RelOptInfo *
562build_join_rel(PlannerInfo *root,
563 Relids joinrelids,
564 RelOptInfo *outer_rel,
565 RelOptInfo *inner_rel,
566 SpecialJoinInfo *sjinfo,
567 List **restrictlist_ptr)
568{
569 RelOptInfo *joinrel;
570 List *restrictlist;
571
572 /* This function should be used only for join between parents. */
573 Assert(!IS_OTHER_REL(outer_rel) && !IS_OTHER_REL(inner_rel));
574
575 /*
576 * See if we already have a joinrel for this set of base rels.
577 */
578 joinrel = find_join_rel(root, joinrelids);
579
580 if (joinrel)
581 {
582 /*
583 * Yes, so we only need to figure the restrictlist for this particular
584 * pair of component relations.
585 */
586 if (restrictlist_ptr)
587 *restrictlist_ptr = build_joinrel_restrictlist(root,
588 joinrel,
589 outer_rel,
590 inner_rel);
591 return joinrel;
592 }
593
594 /*
595 * Nope, so make one.
596 */
597 joinrel = makeNode(RelOptInfo);
598 joinrel->reloptkind = RELOPT_JOINREL;
599 joinrel->relids = bms_copy(joinrelids);
600 joinrel->rows = 0;
601 /* cheap startup cost is interesting iff not all tuples to be retrieved */
602 joinrel->consider_startup = (root->tuple_fraction > 0);
603 joinrel->consider_param_startup = false;
604 joinrel->consider_parallel = false;
605 joinrel->reltarget = create_empty_pathtarget();
606 joinrel->pathlist = NIL;
607 joinrel->ppilist = NIL;
608 joinrel->partial_pathlist = NIL;
609 joinrel->cheapest_startup_path = NULL;
610 joinrel->cheapest_total_path = NULL;
611 joinrel->cheapest_unique_path = NULL;
612 joinrel->cheapest_parameterized_paths = NIL;
613 /* init direct_lateral_relids from children; we'll finish it up below */
614 joinrel->direct_lateral_relids =
615 bms_union(outer_rel->direct_lateral_relids,
616 inner_rel->direct_lateral_relids);
617 joinrel->lateral_relids = min_join_parameterization(root, joinrel->relids,
618 outer_rel, inner_rel);
619 joinrel->relid = 0; /* indicates not a baserel */
620 joinrel->rtekind = RTE_JOIN;
621 joinrel->min_attr = 0;
622 joinrel->max_attr = 0;
623 joinrel->attr_needed = NULL;
624 joinrel->attr_widths = NULL;
625 joinrel->lateral_vars = NIL;
626 joinrel->lateral_referencers = NULL;
627 joinrel->indexlist = NIL;
628 joinrel->statlist = NIL;
629 joinrel->pages = 0;
630 joinrel->tuples = 0;
631 joinrel->allvisfrac = 0;
632 joinrel->subroot = NULL;
633 joinrel->subplan_params = NIL;
634 joinrel->rel_parallel_workers = -1;
635 joinrel->serverid = InvalidOid;
636 joinrel->userid = InvalidOid;
637 joinrel->useridiscurrent = false;
638 joinrel->fdwroutine = NULL;
639 joinrel->fdw_private = NULL;
640 joinrel->unique_for_rels = NIL;
641 joinrel->non_unique_for_rels = NIL;
642 joinrel->baserestrictinfo = NIL;
643 joinrel->baserestrictcost.startup = 0;
644 joinrel->baserestrictcost.per_tuple = 0;
645 joinrel->baserestrict_min_security = UINT_MAX;
646 joinrel->joininfo = NIL;
647 joinrel->has_eclass_joins = false;
648 joinrel->consider_partitionwise_join = false; /* might get changed later */
649 joinrel->top_parent_relids = NULL;
650 joinrel->part_scheme = NULL;
651 joinrel->nparts = 0;
652 joinrel->boundinfo = NULL;
653 joinrel->partition_qual = NIL;
654 joinrel->part_rels = NULL;
655 joinrel->partexprs = NULL;
656 joinrel->nullable_partexprs = NULL;
657 joinrel->partitioned_child_rels = NIL;
658
659 /* Compute information relevant to the foreign relations. */
660 set_foreign_rel_properties(joinrel, outer_rel, inner_rel);
661
662 /*
663 * Create a new tlist containing just the vars that need to be output from
664 * this join (ie, are needed for higher joinclauses or final output).
665 *
666 * NOTE: the tlist order for a join rel will depend on which pair of outer
667 * and inner rels we first try to build it from. But the contents should
668 * be the same regardless.
669 */
670 build_joinrel_tlist(root, joinrel, outer_rel);
671 build_joinrel_tlist(root, joinrel, inner_rel);
672 add_placeholders_to_joinrel(root, joinrel, outer_rel, inner_rel);
673
674 /*
675 * add_placeholders_to_joinrel also took care of adding the ph_lateral
676 * sets of any PlaceHolderVars computed here to direct_lateral_relids, so
677 * now we can finish computing that. This is much like the computation of
678 * the transitively-closed lateral_relids in min_join_parameterization,
679 * except that here we *do* have to consider the added PHVs.
680 */
681 joinrel->direct_lateral_relids =
682 bms_del_members(joinrel->direct_lateral_relids, joinrel->relids);
683 if (bms_is_empty(joinrel->direct_lateral_relids))
684 joinrel->direct_lateral_relids = NULL;
685
686 /*
687 * Construct restrict and join clause lists for the new joinrel. (The
688 * caller might or might not need the restrictlist, but I need it anyway
689 * for set_joinrel_size_estimates().)
690 */
691 restrictlist = build_joinrel_restrictlist(root, joinrel,
692 outer_rel, inner_rel);
693 if (restrictlist_ptr)
694 *restrictlist_ptr = restrictlist;
695 build_joinrel_joinlist(joinrel, outer_rel, inner_rel);
696
697 /*
698 * This is also the right place to check whether the joinrel has any
699 * pending EquivalenceClass joins.
700 */
701 joinrel->has_eclass_joins = has_relevant_eclass_joinclause(root, joinrel);
702
703 /* Store the partition information. */
704 build_joinrel_partition_info(joinrel, outer_rel, inner_rel, restrictlist,
705 sjinfo->jointype);
706
707 /*
708 * Set estimates of the joinrel's size.
709 */
710 set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel,
711 sjinfo, restrictlist);
712
713 /*
714 * Set the consider_parallel flag if this joinrel could potentially be
715 * scanned within a parallel worker. If this flag is false for either
716 * inner_rel or outer_rel, then it must be false for the joinrel also.
717 * Even if both are true, there might be parallel-restricted expressions
718 * in the targetlist or quals.
719 *
720 * Note that if there are more than two rels in this relation, they could
721 * be divided between inner_rel and outer_rel in any arbitrary way. We
722 * assume this doesn't matter, because we should hit all the same baserels
723 * and joinclauses while building up to this joinrel no matter which we
724 * take; therefore, we should make the same decision here however we get
725 * here.
726 */
727 if (inner_rel->consider_parallel && outer_rel->consider_parallel &&
728 is_parallel_safe(root, (Node *) restrictlist) &&
729 is_parallel_safe(root, (Node *) joinrel->reltarget->exprs))
730 joinrel->consider_parallel = true;
731
732 /* Add the joinrel to the PlannerInfo. */
733 add_join_rel(root, joinrel);
734
735 /*
736 * Also, if dynamic-programming join search is active, add the new joinrel
737 * to the appropriate sublist. Note: you might think the Assert on number
738 * of members should be for equality, but some of the level 1 rels might
739 * have been joinrels already, so we can only assert <=.
740 */
741 if (root->join_rel_level)
742 {
743 Assert(root->join_cur_level > 0);
744 Assert(root->join_cur_level <= bms_num_members(joinrel->relids));
745 root->join_rel_level[root->join_cur_level] =
746 lappend(root->join_rel_level[root->join_cur_level], joinrel);
747 }
748
749 return joinrel;
750}
751
752/*
753 * build_child_join_rel
754 * Builds RelOptInfo representing join between given two child relations.
755 *
756 * 'outer_rel' and 'inner_rel' are the RelOptInfos of child relations being
757 * joined
758 * 'parent_joinrel' is the RelOptInfo representing the join between parent
759 * relations. Some of the members of new RelOptInfo are produced by
760 * translating corresponding members of this RelOptInfo
761 * 'sjinfo': child-join context info
762 * 'restrictlist': list of RestrictInfo nodes that apply to this particular
763 * pair of joinable relations
764 * 'jointype' is the join type (inner, left, full, etc)
765 */
766RelOptInfo *
767build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel,
768 RelOptInfo *inner_rel, RelOptInfo *parent_joinrel,
769 List *restrictlist, SpecialJoinInfo *sjinfo,
770 JoinType jointype)
771{
772 RelOptInfo *joinrel = makeNode(RelOptInfo);
773 AppendRelInfo **appinfos;
774 int nappinfos;
775
776 /* Only joins between "other" relations land here. */
777 Assert(IS_OTHER_REL(outer_rel) && IS_OTHER_REL(inner_rel));
778
779 /* The parent joinrel should have consider_partitionwise_join set. */
780 Assert(parent_joinrel->consider_partitionwise_join);
781
782 joinrel->reloptkind = RELOPT_OTHER_JOINREL;
783 joinrel->relids = bms_union(outer_rel->relids, inner_rel->relids);
784 joinrel->rows = 0;
785 /* cheap startup cost is interesting iff not all tuples to be retrieved */
786 joinrel->consider_startup = (root->tuple_fraction > 0);
787 joinrel->consider_param_startup = false;
788 joinrel->consider_parallel = false;
789 joinrel->reltarget = create_empty_pathtarget();
790 joinrel->pathlist = NIL;
791 joinrel->ppilist = NIL;
792 joinrel->partial_pathlist = NIL;
793 joinrel->cheapest_startup_path = NULL;
794 joinrel->cheapest_total_path = NULL;
795 joinrel->cheapest_unique_path = NULL;
796 joinrel->cheapest_parameterized_paths = NIL;
797 joinrel->direct_lateral_relids = NULL;
798 joinrel->lateral_relids = NULL;
799 joinrel->relid = 0; /* indicates not a baserel */
800 joinrel->rtekind = RTE_JOIN;
801 joinrel->min_attr = 0;
802 joinrel->max_attr = 0;
803 joinrel->attr_needed = NULL;
804 joinrel->attr_widths = NULL;
805 joinrel->lateral_vars = NIL;
806 joinrel->lateral_referencers = NULL;
807 joinrel->indexlist = NIL;
808 joinrel->pages = 0;
809 joinrel->tuples = 0;
810 joinrel->allvisfrac = 0;
811 joinrel->subroot = NULL;
812 joinrel->subplan_params = NIL;
813 joinrel->serverid = InvalidOid;
814 joinrel->userid = InvalidOid;
815 joinrel->useridiscurrent = false;
816 joinrel->fdwroutine = NULL;
817 joinrel->fdw_private = NULL;
818 joinrel->baserestrictinfo = NIL;
819 joinrel->baserestrictcost.startup = 0;
820 joinrel->baserestrictcost.per_tuple = 0;
821 joinrel->joininfo = NIL;
822 joinrel->has_eclass_joins = false;
823 joinrel->consider_partitionwise_join = false; /* might get changed later */
824 joinrel->top_parent_relids = NULL;
825 joinrel->part_scheme = NULL;
826 joinrel->nparts = 0;
827 joinrel->boundinfo = NULL;
828 joinrel->partition_qual = NIL;
829 joinrel->part_rels = NULL;
830 joinrel->partexprs = NULL;
831 joinrel->nullable_partexprs = NULL;
832 joinrel->partitioned_child_rels = NIL;
833
834 joinrel->top_parent_relids = bms_union(outer_rel->top_parent_relids,
835 inner_rel->top_parent_relids);
836
837 /* Compute information relevant to foreign relations. */
838 set_foreign_rel_properties(joinrel, outer_rel, inner_rel);
839
840 appinfos = find_appinfos_by_relids(root, joinrel->relids, &nappinfos);
841
842 /* Set up reltarget struct */
843 build_child_join_reltarget(root, parent_joinrel, joinrel,
844 nappinfos, appinfos);
845
846 /* Construct joininfo list. */
847 joinrel->joininfo = (List *) adjust_appendrel_attrs(root,
848 (Node *) parent_joinrel->joininfo,
849 nappinfos,
850 appinfos);
851 pfree(appinfos);
852
853 /*
854 * Lateral relids referred in child join will be same as that referred in
855 * the parent relation. Throw any partial result computed while building
856 * the targetlist.
857 */
858 bms_free(joinrel->direct_lateral_relids);
859 bms_free(joinrel->lateral_relids);
860 joinrel->direct_lateral_relids = (Relids) bms_copy(parent_joinrel->direct_lateral_relids);
861 joinrel->lateral_relids = (Relids) bms_copy(parent_joinrel->lateral_relids);
862
863 /*
864 * If the parent joinrel has pending equivalence classes, so does the
865 * child.
866 */
867 joinrel->has_eclass_joins = parent_joinrel->has_eclass_joins;
868
869 /* Is the join between partitions itself partitioned? */
870 build_joinrel_partition_info(joinrel, outer_rel, inner_rel, restrictlist,
871 jointype);
872
873 /* Child joinrel is parallel safe if parent is parallel safe. */
874 joinrel->consider_parallel = parent_joinrel->consider_parallel;
875
876 /* Set estimates of the child-joinrel's size. */
877 set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel,
878 sjinfo, restrictlist);
879
880 /* We build the join only once. */
881 Assert(!find_join_rel(root, joinrel->relids));
882
883 /* Add the relation to the PlannerInfo. */
884 add_join_rel(root, joinrel);
885
886 return joinrel;
887}
888
889/*
890 * min_join_parameterization
891 *
892 * Determine the minimum possible parameterization of a joinrel, that is, the
893 * set of other rels it contains LATERAL references to. We save this value in
894 * the join's RelOptInfo. This function is split out of build_join_rel()
895 * because join_is_legal() needs the value to check a prospective join.
896 */
897Relids
898min_join_parameterization(PlannerInfo *root,
899 Relids joinrelids,
900 RelOptInfo *outer_rel,
901 RelOptInfo *inner_rel)
902{
903 Relids result;
904
905 /*
906 * Basically we just need the union of the inputs' lateral_relids, less
907 * whatever is already in the join.
908 *
909 * It's not immediately obvious that this is a valid way to compute the
910 * result, because it might seem that we're ignoring possible lateral refs
911 * of PlaceHolderVars that are due to be computed at the join but not in
912 * either input. However, because create_lateral_join_info() already
913 * charged all such PHV refs to each member baserel of the join, they'll
914 * be accounted for already in the inputs' lateral_relids. Likewise, we
915 * do not need to worry about doing transitive closure here, because that
916 * was already accounted for in the original baserel lateral_relids.
917 */
918 result = bms_union(outer_rel->lateral_relids, inner_rel->lateral_relids);
919 result = bms_del_members(result, joinrelids);
920
921 /* Maintain invariant that result is exactly NULL if empty */
922 if (bms_is_empty(result))
923 result = NULL;
924
925 return result;
926}
927
928/*
929 * build_joinrel_tlist
930 * Builds a join relation's target list from an input relation.
931 * (This is invoked twice to handle the two input relations.)
932 *
933 * The join's targetlist includes all Vars of its member relations that
934 * will still be needed above the join. This subroutine adds all such
935 * Vars from the specified input rel's tlist to the join rel's tlist.
936 *
937 * We also compute the expected width of the join's output, making use
938 * of data that was cached at the baserel level by set_rel_width().
939 */
940static void
941build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
942 RelOptInfo *input_rel)
943{
944 Relids relids = joinrel->relids;
945 ListCell *vars;
946
947 foreach(vars, input_rel->reltarget->exprs)
948 {
949 Var *var = (Var *) lfirst(vars);
950 RelOptInfo *baserel;
951 int ndx;
952
953 /*
954 * Ignore PlaceHolderVars in the input tlists; we'll make our own
955 * decisions about whether to copy them.
956 */
957 if (IsA(var, PlaceHolderVar))
958 continue;
959
960 /*
961 * Otherwise, anything in a baserel or joinrel targetlist ought to be
962 * a Var. (More general cases can only appear in appendrel child
963 * rels, which will never be seen here.)
964 */
965 if (!IsA(var, Var))
966 elog(ERROR, "unexpected node type in rel targetlist: %d",
967 (int) nodeTag(var));
968
969 /* Get the Var's original base rel */
970 baserel = find_base_rel(root, var->varno);
971
972 /* Is it still needed above this joinrel? */
973 ndx = var->varattno - baserel->min_attr;
974 if (bms_nonempty_difference(baserel->attr_needed[ndx], relids))
975 {
976 /* Yup, add it to the output */
977 joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs, var);
978 /* Vars have cost zero, so no need to adjust reltarget->cost */
979 joinrel->reltarget->width += baserel->attr_widths[ndx];
980 }
981 }
982}
983
984/*
985 * build_joinrel_restrictlist
986 * build_joinrel_joinlist
987 * These routines build lists of restriction and join clauses for a
988 * join relation from the joininfo lists of the relations it joins.
989 *
990 * These routines are separate because the restriction list must be
991 * built afresh for each pair of input sub-relations we consider, whereas
992 * the join list need only be computed once for any join RelOptInfo.
993 * The join list is fully determined by the set of rels making up the
994 * joinrel, so we should get the same results (up to ordering) from any
995 * candidate pair of sub-relations. But the restriction list is whatever
996 * is not handled in the sub-relations, so it depends on which
997 * sub-relations are considered.
998 *
999 * If a join clause from an input relation refers to base rels still not
1000 * present in the joinrel, then it is still a join clause for the joinrel;
1001 * we put it into the joininfo list for the joinrel. Otherwise,
1002 * the clause is now a restrict clause for the joined relation, and we
1003 * return it to the caller of build_joinrel_restrictlist() to be stored in
1004 * join paths made from this pair of sub-relations. (It will not need to
1005 * be considered further up the join tree.)
1006 *
1007 * In many case we will find the same RestrictInfos in both input
1008 * relations' joinlists, so be careful to eliminate duplicates.
1009 * Pointer equality should be a sufficient test for dups, since all
1010 * the various joinlist entries ultimately refer to RestrictInfos
1011 * pushed into them by distribute_restrictinfo_to_rels().
1012 *
1013 * 'joinrel' is a join relation node
1014 * 'outer_rel' and 'inner_rel' are a pair of relations that can be joined
1015 * to form joinrel.
1016 *
1017 * build_joinrel_restrictlist() returns a list of relevant restrictinfos,
1018 * whereas build_joinrel_joinlist() stores its results in the joinrel's
1019 * joininfo list. One or the other must accept each given clause!
1020 *
1021 * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass
1022 * up to the join relation. I believe this is no longer necessary, because
1023 * RestrictInfo nodes are no longer context-dependent. Instead, just include
1024 * the original nodes in the lists made for the join relation.
1025 */
1026static List *
1027build_joinrel_restrictlist(PlannerInfo *root,
1028 RelOptInfo *joinrel,
1029 RelOptInfo *outer_rel,
1030 RelOptInfo *inner_rel)
1031{
1032 List *result;
1033
1034 /*
1035 * Collect all the clauses that syntactically belong at this level,
1036 * eliminating any duplicates (important since we will see many of the
1037 * same clauses arriving from both input relations).
1038 */
1039 result = subbuild_joinrel_restrictlist(joinrel, outer_rel->joininfo, NIL);
1040 result = subbuild_joinrel_restrictlist(joinrel, inner_rel->joininfo, result);
1041
1042 /*
1043 * Add on any clauses derived from EquivalenceClasses. These cannot be
1044 * redundant with the clauses in the joininfo lists, so don't bother
1045 * checking.
1046 */
1047 result = list_concat(result,
1048 generate_join_implied_equalities(root,
1049 joinrel->relids,
1050 outer_rel->relids,
1051 inner_rel));
1052
1053 return result;
1054}
1055
1056static void
1057build_joinrel_joinlist(RelOptInfo *joinrel,
1058 RelOptInfo *outer_rel,
1059 RelOptInfo *inner_rel)
1060{
1061 List *result;
1062
1063 /*
1064 * Collect all the clauses that syntactically belong above this level,
1065 * eliminating any duplicates (important since we will see many of the
1066 * same clauses arriving from both input relations).
1067 */
1068 result = subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo, NIL);
1069 result = subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo, result);
1070
1071 joinrel->joininfo = result;
1072}
1073
1074static List *
1075subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
1076 List *joininfo_list,
1077 List *new_restrictlist)
1078{
1079 ListCell *l;
1080
1081 foreach(l, joininfo_list)
1082 {
1083 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
1084
1085 if (bms_is_subset(rinfo->required_relids, joinrel->relids))
1086 {
1087 /*
1088 * This clause becomes a restriction clause for the joinrel, since
1089 * it refers to no outside rels. Add it to the list, being
1090 * careful to eliminate duplicates. (Since RestrictInfo nodes in
1091 * different joinlists will have been multiply-linked rather than
1092 * copied, pointer equality should be a sufficient test.)
1093 */
1094 new_restrictlist = list_append_unique_ptr(new_restrictlist, rinfo);
1095 }
1096 else
1097 {
1098 /*
1099 * This clause is still a join clause at this level, so we ignore
1100 * it in this routine.
1101 */
1102 }
1103 }
1104
1105 return new_restrictlist;
1106}
1107
1108static List *
1109subbuild_joinrel_joinlist(RelOptInfo *joinrel,
1110 List *joininfo_list,
1111 List *new_joininfo)
1112{
1113 ListCell *l;
1114
1115 /* Expected to be called only for join between parent relations. */
1116 Assert(joinrel->reloptkind == RELOPT_JOINREL);
1117
1118 foreach(l, joininfo_list)
1119 {
1120 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
1121
1122 if (bms_is_subset(rinfo->required_relids, joinrel->relids))
1123 {
1124 /*
1125 * This clause becomes a restriction clause for the joinrel, since
1126 * it refers to no outside rels. So we can ignore it in this
1127 * routine.
1128 */
1129 }
1130 else
1131 {
1132 /*
1133 * This clause is still a join clause at this level, so add it to
1134 * the new joininfo list, being careful to eliminate duplicates.
1135 * (Since RestrictInfo nodes in different joinlists will have been
1136 * multiply-linked rather than copied, pointer equality should be
1137 * a sufficient test.)
1138 */
1139 new_joininfo = list_append_unique_ptr(new_joininfo, rinfo);
1140 }
1141 }
1142
1143 return new_joininfo;
1144}
1145
1146
1147/*
1148 * fetch_upper_rel
1149 * Build a RelOptInfo describing some post-scan/join query processing,
1150 * or return a pre-existing one if somebody already built it.
1151 *
1152 * An "upper" relation is identified by an UpperRelationKind and a Relids set.
1153 * The meaning of the Relids set is not specified here, and very likely will
1154 * vary for different relation kinds.
1155 *
1156 * Most of the fields in an upper-level RelOptInfo are not used and are not
1157 * set here (though makeNode should ensure they're zeroes). We basically only
1158 * care about fields that are of interest to add_path() and set_cheapest().
1159 */
1160RelOptInfo *
1161fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids)
1162{
1163 RelOptInfo *upperrel;
1164 ListCell *lc;
1165
1166 /*
1167 * For the moment, our indexing data structure is just a List for each
1168 * relation kind. If we ever get so many of one kind that this stops
1169 * working well, we can improve it. No code outside this function should
1170 * assume anything about how to find a particular upperrel.
1171 */
1172
1173 /* If we already made this upperrel for the query, return it */
1174 foreach(lc, root->upper_rels[kind])
1175 {
1176 upperrel = (RelOptInfo *) lfirst(lc);
1177
1178 if (bms_equal(upperrel->relids, relids))
1179 return upperrel;
1180 }
1181
1182 upperrel = makeNode(RelOptInfo);
1183 upperrel->reloptkind = RELOPT_UPPER_REL;
1184 upperrel->relids = bms_copy(relids);
1185
1186 /* cheap startup cost is interesting iff not all tuples to be retrieved */
1187 upperrel->consider_startup = (root->tuple_fraction > 0);
1188 upperrel->consider_param_startup = false;
1189 upperrel->consider_parallel = false; /* might get changed later */
1190 upperrel->reltarget = create_empty_pathtarget();
1191 upperrel->pathlist = NIL;
1192 upperrel->cheapest_startup_path = NULL;
1193 upperrel->cheapest_total_path = NULL;
1194 upperrel->cheapest_unique_path = NULL;
1195 upperrel->cheapest_parameterized_paths = NIL;
1196
1197 root->upper_rels[kind] = lappend(root->upper_rels[kind], upperrel);
1198
1199 return upperrel;
1200}
1201
1202
1203/*
1204 * find_childrel_parents
1205 * Compute the set of parent relids of an appendrel child rel.
1206 *
1207 * Since appendrels can be nested, a child could have multiple levels of
1208 * appendrel ancestors. This function computes a Relids set of all the
1209 * parent relation IDs.
1210 */
1211Relids
1212find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
1213{
1214 Relids result = NULL;
1215
1216 Assert(rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
1217 Assert(rel->relid > 0 && rel->relid < root->simple_rel_array_size);
1218
1219 do
1220 {
1221 AppendRelInfo *appinfo = root->append_rel_array[rel->relid];
1222 Index prelid = appinfo->parent_relid;
1223
1224 result = bms_add_member(result, prelid);
1225
1226 /* traverse up to the parent rel, loop if it's also a child rel */
1227 rel = find_base_rel(root, prelid);
1228 } while (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
1229
1230 Assert(rel->reloptkind == RELOPT_BASEREL);
1231
1232 return result;
1233}
1234
1235
1236/*
1237 * get_baserel_parampathinfo
1238 * Get the ParamPathInfo for a parameterized path for a base relation,
1239 * constructing one if we don't have one already.
1240 *
1241 * This centralizes estimating the rowcounts for parameterized paths.
1242 * We need to cache those to be sure we use the same rowcount for all paths
1243 * of the same parameterization for a given rel. This is also a convenient
1244 * place to determine which movable join clauses the parameterized path will
1245 * be responsible for evaluating.
1246 */
1247ParamPathInfo *
1248get_baserel_parampathinfo(PlannerInfo *root, RelOptInfo *baserel,
1249 Relids required_outer)
1250{
1251 ParamPathInfo *ppi;
1252 Relids joinrelids;
1253 List *pclauses;
1254 double rows;
1255 ListCell *lc;
1256
1257 /* If rel has LATERAL refs, every path for it should account for them */
1258 Assert(bms_is_subset(baserel->lateral_relids, required_outer));
1259
1260 /* Unparameterized paths have no ParamPathInfo */
1261 if (bms_is_empty(required_outer))
1262 return NULL;
1263
1264 Assert(!bms_overlap(baserel->relids, required_outer));
1265
1266 /* If we already have a PPI for this parameterization, just return it */
1267 if ((ppi = find_param_path_info(baserel, required_outer)))
1268 return ppi;
1269
1270 /*
1271 * Identify all joinclauses that are movable to this base rel given this
1272 * parameterization.
1273 */
1274 joinrelids = bms_union(baserel->relids, required_outer);
1275 pclauses = NIL;
1276 foreach(lc, baserel->joininfo)
1277 {
1278 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1279
1280 if (join_clause_is_movable_into(rinfo,
1281 baserel->relids,
1282 joinrelids))
1283 pclauses = lappend(pclauses, rinfo);
1284 }
1285
1286 /*
1287 * Add in joinclauses generated by EquivalenceClasses, too. (These
1288 * necessarily satisfy join_clause_is_movable_into.)
1289 */
1290 pclauses = list_concat(pclauses,
1291 generate_join_implied_equalities(root,
1292 joinrelids,
1293 required_outer,
1294 baserel));
1295
1296 /* Estimate the number of rows returned by the parameterized scan */
1297 rows = get_parameterized_baserel_size(root, baserel, pclauses);
1298
1299 /* And now we can build the ParamPathInfo */
1300 ppi = makeNode(ParamPathInfo);
1301 ppi->ppi_req_outer = required_outer;
1302 ppi->ppi_rows = rows;
1303 ppi->ppi_clauses = pclauses;
1304 baserel->ppilist = lappend(baserel->ppilist, ppi);
1305
1306 return ppi;
1307}
1308
1309/*
1310 * get_joinrel_parampathinfo
1311 * Get the ParamPathInfo for a parameterized path for a join relation,
1312 * constructing one if we don't have one already.
1313 *
1314 * This centralizes estimating the rowcounts for parameterized paths.
1315 * We need to cache those to be sure we use the same rowcount for all paths
1316 * of the same parameterization for a given rel. This is also a convenient
1317 * place to determine which movable join clauses the parameterized path will
1318 * be responsible for evaluating.
1319 *
1320 * outer_path and inner_path are a pair of input paths that can be used to
1321 * construct the join, and restrict_clauses is the list of regular join
1322 * clauses (including clauses derived from EquivalenceClasses) that must be
1323 * applied at the join node when using these inputs.
1324 *
1325 * Unlike the situation for base rels, the set of movable join clauses to be
1326 * enforced at a join varies with the selected pair of input paths, so we
1327 * must calculate that and pass it back, even if we already have a matching
1328 * ParamPathInfo. We handle this by adding any clauses moved down to this
1329 * join to *restrict_clauses, which is an in/out parameter. (The addition
1330 * is done in such a way as to not modify the passed-in List structure.)
1331 *
1332 * Note: when considering a nestloop join, the caller must have removed from
1333 * restrict_clauses any movable clauses that are themselves scheduled to be
1334 * pushed into the right-hand path. We do not do that here since it's
1335 * unnecessary for other join types.
1336 */
1337ParamPathInfo *
1338get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel,
1339 Path *outer_path,
1340 Path *inner_path,
1341 SpecialJoinInfo *sjinfo,
1342 Relids required_outer,
1343 List **restrict_clauses)
1344{
1345 ParamPathInfo *ppi;
1346 Relids join_and_req;
1347 Relids outer_and_req;
1348 Relids inner_and_req;
1349 List *pclauses;
1350 List *eclauses;
1351 List *dropped_ecs;
1352 double rows;
1353 ListCell *lc;
1354
1355 /* If rel has LATERAL refs, every path for it should account for them */
1356 Assert(bms_is_subset(joinrel->lateral_relids, required_outer));
1357
1358 /* Unparameterized paths have no ParamPathInfo or extra join clauses */
1359 if (bms_is_empty(required_outer))
1360 return NULL;
1361
1362 Assert(!bms_overlap(joinrel->relids, required_outer));
1363
1364 /*
1365 * Identify all joinclauses that are movable to this join rel given this
1366 * parameterization. These are the clauses that are movable into this
1367 * join, but not movable into either input path. Treat an unparameterized
1368 * input path as not accepting parameterized clauses (because it won't,
1369 * per the shortcut exit above), even though the joinclause movement rules
1370 * might allow the same clauses to be moved into a parameterized path for
1371 * that rel.
1372 */
1373 join_and_req = bms_union(joinrel->relids, required_outer);
1374 if (outer_path->param_info)
1375 outer_and_req = bms_union(outer_path->parent->relids,
1376 PATH_REQ_OUTER(outer_path));
1377 else
1378 outer_and_req = NULL; /* outer path does not accept parameters */
1379 if (inner_path->param_info)
1380 inner_and_req = bms_union(inner_path->parent->relids,
1381 PATH_REQ_OUTER(inner_path));
1382 else
1383 inner_and_req = NULL; /* inner path does not accept parameters */
1384
1385 pclauses = NIL;
1386 foreach(lc, joinrel->joininfo)
1387 {
1388 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1389
1390 if (join_clause_is_movable_into(rinfo,
1391 joinrel->relids,
1392 join_and_req) &&
1393 !join_clause_is_movable_into(rinfo,
1394 outer_path->parent->relids,
1395 outer_and_req) &&
1396 !join_clause_is_movable_into(rinfo,
1397 inner_path->parent->relids,
1398 inner_and_req))
1399 pclauses = lappend(pclauses, rinfo);
1400 }
1401
1402 /* Consider joinclauses generated by EquivalenceClasses, too */
1403 eclauses = generate_join_implied_equalities(root,
1404 join_and_req,
1405 required_outer,
1406 joinrel);
1407 /* We only want ones that aren't movable to lower levels */
1408 dropped_ecs = NIL;
1409 foreach(lc, eclauses)
1410 {
1411 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1412
1413 /*
1414 * In principle, join_clause_is_movable_into() should accept anything
1415 * returned by generate_join_implied_equalities(); but because its
1416 * analysis is only approximate, sometimes it doesn't. So we
1417 * currently cannot use this Assert; instead just assume it's okay to
1418 * apply the joinclause at this level.
1419 */
1420#ifdef NOT_USED
1421 Assert(join_clause_is_movable_into(rinfo,
1422 joinrel->relids,
1423 join_and_req));
1424#endif
1425 if (join_clause_is_movable_into(rinfo,
1426 outer_path->parent->relids,
1427 outer_and_req))
1428 continue; /* drop if movable into LHS */
1429 if (join_clause_is_movable_into(rinfo,
1430 inner_path->parent->relids,
1431 inner_and_req))
1432 {
1433 /* drop if movable into RHS, but remember EC for use below */
1434 Assert(rinfo->left_ec == rinfo->right_ec);
1435 dropped_ecs = lappend(dropped_ecs, rinfo->left_ec);
1436 continue;
1437 }
1438 pclauses = lappend(pclauses, rinfo);
1439 }
1440
1441 /*
1442 * EquivalenceClasses are harder to deal with than we could wish, because
1443 * of the fact that a given EC can generate different clauses depending on
1444 * context. Suppose we have an EC {X.X, Y.Y, Z.Z} where X and Y are the
1445 * LHS and RHS of the current join and Z is in required_outer, and further
1446 * suppose that the inner_path is parameterized by both X and Z. The code
1447 * above will have produced either Z.Z = X.X or Z.Z = Y.Y from that EC,
1448 * and in the latter case will have discarded it as being movable into the
1449 * RHS. However, the EC machinery might have produced either Y.Y = X.X or
1450 * Y.Y = Z.Z as the EC enforcement clause within the inner_path; it will
1451 * not have produced both, and we can't readily tell from here which one
1452 * it did pick. If we add no clause to this join, we'll end up with
1453 * insufficient enforcement of the EC; either Z.Z or X.X will fail to be
1454 * constrained to be equal to the other members of the EC. (When we come
1455 * to join Z to this X/Y path, we will certainly drop whichever EC clause
1456 * is generated at that join, so this omission won't get fixed later.)
1457 *
1458 * To handle this, for each EC we discarded such a clause from, try to
1459 * generate a clause connecting the required_outer rels to the join's LHS
1460 * ("Z.Z = X.X" in the terms of the above example). If successful, and if
1461 * the clause can't be moved to the LHS, add it to the current join's
1462 * restriction clauses. (If an EC cannot generate such a clause then it
1463 * has nothing that needs to be enforced here, while if the clause can be
1464 * moved into the LHS then it should have been enforced within that path.)
1465 *
1466 * Note that we don't need similar processing for ECs whose clause was
1467 * considered to be movable into the LHS, because the LHS can't refer to
1468 * the RHS so there is no comparable ambiguity about what it might
1469 * actually be enforcing internally.
1470 */
1471 if (dropped_ecs)
1472 {
1473 Relids real_outer_and_req;
1474
1475 real_outer_and_req = bms_union(outer_path->parent->relids,
1476 required_outer);
1477 eclauses =
1478 generate_join_implied_equalities_for_ecs(root,
1479 dropped_ecs,
1480 real_outer_and_req,
1481 required_outer,
1482 outer_path->parent);
1483 foreach(lc, eclauses)
1484 {
1485 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1486
1487 /* As above, can't quite assert this here */
1488#ifdef NOT_USED
1489 Assert(join_clause_is_movable_into(rinfo,
1490 outer_path->parent->relids,
1491 real_outer_and_req));
1492#endif
1493 if (!join_clause_is_movable_into(rinfo,
1494 outer_path->parent->relids,
1495 outer_and_req))
1496 pclauses = lappend(pclauses, rinfo);
1497 }
1498 }
1499
1500 /*
1501 * Now, attach the identified moved-down clauses to the caller's
1502 * restrict_clauses list. By using list_concat in this order, we leave
1503 * the original list structure of restrict_clauses undamaged.
1504 */
1505 *restrict_clauses = list_concat(pclauses, *restrict_clauses);
1506
1507 /* If we already have a PPI for this parameterization, just return it */
1508 if ((ppi = find_param_path_info(joinrel, required_outer)))
1509 return ppi;
1510
1511 /* Estimate the number of rows returned by the parameterized join */
1512 rows = get_parameterized_joinrel_size(root, joinrel,
1513 outer_path,
1514 inner_path,
1515 sjinfo,
1516 *restrict_clauses);
1517
1518 /*
1519 * And now we can build the ParamPathInfo. No point in saving the
1520 * input-pair-dependent clause list, though.
1521 *
1522 * Note: in GEQO mode, we'll be called in a temporary memory context, but
1523 * the joinrel structure is there too, so no problem.
1524 */
1525 ppi = makeNode(ParamPathInfo);
1526 ppi->ppi_req_outer = required_outer;
1527 ppi->ppi_rows = rows;
1528 ppi->ppi_clauses = NIL;
1529 joinrel->ppilist = lappend(joinrel->ppilist, ppi);
1530
1531 return ppi;
1532}
1533
1534/*
1535 * get_appendrel_parampathinfo
1536 * Get the ParamPathInfo for a parameterized path for an append relation.
1537 *
1538 * For an append relation, the rowcount estimate will just be the sum of
1539 * the estimates for its children. However, we still need a ParamPathInfo
1540 * to flag the fact that the path requires parameters. So this just creates
1541 * a suitable struct with zero ppi_rows (and no ppi_clauses either, since
1542 * the Append node isn't responsible for checking quals).
1543 */
1544ParamPathInfo *
1545get_appendrel_parampathinfo(RelOptInfo *appendrel, Relids required_outer)
1546{
1547 ParamPathInfo *ppi;
1548
1549 /* If rel has LATERAL refs, every path for it should account for them */
1550 Assert(bms_is_subset(appendrel->lateral_relids, required_outer));
1551
1552 /* Unparameterized paths have no ParamPathInfo */
1553 if (bms_is_empty(required_outer))
1554 return NULL;
1555
1556 Assert(!bms_overlap(appendrel->relids, required_outer));
1557
1558 /* If we already have a PPI for this parameterization, just return it */
1559 if ((ppi = find_param_path_info(appendrel, required_outer)))
1560 return ppi;
1561
1562 /* Else build the ParamPathInfo */
1563 ppi = makeNode(ParamPathInfo);
1564 ppi->ppi_req_outer = required_outer;
1565 ppi->ppi_rows = 0;
1566 ppi->ppi_clauses = NIL;
1567 appendrel->ppilist = lappend(appendrel->ppilist, ppi);
1568
1569 return ppi;
1570}
1571
1572/*
1573 * Returns a ParamPathInfo for the parameterization given by required_outer, if
1574 * already available in the given rel. Returns NULL otherwise.
1575 */
1576ParamPathInfo *
1577find_param_path_info(RelOptInfo *rel, Relids required_outer)
1578{
1579 ListCell *lc;
1580
1581 foreach(lc, rel->ppilist)
1582 {
1583 ParamPathInfo *ppi = (ParamPathInfo *) lfirst(lc);
1584
1585 if (bms_equal(ppi->ppi_req_outer, required_outer))
1586 return ppi;
1587 }
1588
1589 return NULL;
1590}
1591
1592/*
1593 * build_joinrel_partition_info
1594 * If the two relations have same partitioning scheme, their join may be
1595 * partitioned and will follow the same partitioning scheme as the joining
1596 * relations. Set the partition scheme and partition key expressions in
1597 * the join relation.
1598 */
1599static void
1600build_joinrel_partition_info(RelOptInfo *joinrel, RelOptInfo *outer_rel,
1601 RelOptInfo *inner_rel, List *restrictlist,
1602 JoinType jointype)
1603{
1604 int partnatts;
1605 int cnt;
1606 PartitionScheme part_scheme;
1607
1608 /* Nothing to do if partitionwise join technique is disabled. */
1609 if (!enable_partitionwise_join)
1610 {
1611 Assert(!IS_PARTITIONED_REL(joinrel));
1612 return;
1613 }
1614
1615 /*
1616 * We can only consider this join as an input to further partitionwise
1617 * joins if (a) the input relations are partitioned and have
1618 * consider_partitionwise_join=true, (b) the partition schemes match, and
1619 * (c) we can identify an equi-join between the partition keys. Note that
1620 * if it were possible for have_partkey_equi_join to return different
1621 * answers for the same joinrel depending on which join ordering we try
1622 * first, this logic would break. That shouldn't happen, though, because
1623 * of the way the query planner deduces implied equalities and reorders
1624 * the joins. Please see optimizer/README for details.
1625 */
1626 if (!IS_PARTITIONED_REL(outer_rel) || !IS_PARTITIONED_REL(inner_rel) ||
1627 !outer_rel->consider_partitionwise_join ||
1628 !inner_rel->consider_partitionwise_join ||
1629 outer_rel->part_scheme != inner_rel->part_scheme ||
1630 !have_partkey_equi_join(joinrel, outer_rel, inner_rel,
1631 jointype, restrictlist))
1632 {
1633 Assert(!IS_PARTITIONED_REL(joinrel));
1634 return;
1635 }
1636
1637 part_scheme = outer_rel->part_scheme;
1638
1639 Assert(REL_HAS_ALL_PART_PROPS(outer_rel) &&
1640 REL_HAS_ALL_PART_PROPS(inner_rel));
1641
1642 /*
1643 * For now, our partition matching algorithm can match partitions only
1644 * when the partition bounds of the joining relations are exactly same.
1645 * So, bail out otherwise.
1646 */
1647 if (outer_rel->nparts != inner_rel->nparts ||
1648 !partition_bounds_equal(part_scheme->partnatts,
1649 part_scheme->parttyplen,
1650 part_scheme->parttypbyval,
1651 outer_rel->boundinfo, inner_rel->boundinfo))
1652 {
1653 Assert(!IS_PARTITIONED_REL(joinrel));
1654 return;
1655 }
1656
1657 /*
1658 * This function will be called only once for each joinrel, hence it
1659 * should not have partition scheme, partition bounds, partition key
1660 * expressions and array for storing child relations set.
1661 */
1662 Assert(!joinrel->part_scheme && !joinrel->partexprs &&
1663 !joinrel->nullable_partexprs && !joinrel->part_rels &&
1664 !joinrel->boundinfo);
1665
1666 /*
1667 * Join relation is partitioned using the same partitioning scheme as the
1668 * joining relations and has same bounds.
1669 */
1670 joinrel->part_scheme = part_scheme;
1671 joinrel->boundinfo = outer_rel->boundinfo;
1672 partnatts = joinrel->part_scheme->partnatts;
1673 joinrel->partexprs = (List **) palloc0(sizeof(List *) * partnatts);
1674 joinrel->nullable_partexprs =
1675 (List **) palloc0(sizeof(List *) * partnatts);
1676 joinrel->nparts = outer_rel->nparts;
1677 joinrel->part_rels =
1678 (RelOptInfo **) palloc0(sizeof(RelOptInfo *) * joinrel->nparts);
1679
1680 /*
1681 * Set the consider_partitionwise_join flag.
1682 */
1683 Assert(outer_rel->consider_partitionwise_join);
1684 Assert(inner_rel->consider_partitionwise_join);
1685 joinrel->consider_partitionwise_join = true;
1686
1687 /*
1688 * Construct partition keys for the join.
1689 *
1690 * An INNER join between two partitioned relations can be regarded as
1691 * partitioned by either key expression. For example, A INNER JOIN B ON
1692 * A.a = B.b can be regarded as partitioned on A.a or on B.b; they are
1693 * equivalent.
1694 *
1695 * For a SEMI or ANTI join, the result can only be regarded as being
1696 * partitioned in the same manner as the outer side, since the inner
1697 * columns are not retained.
1698 *
1699 * An OUTER join like (A LEFT JOIN B ON A.a = B.b) may produce rows with
1700 * B.b NULL. These rows may not fit the partitioning conditions imposed on
1701 * B.b. Hence, strictly speaking, the join is not partitioned by B.b and
1702 * thus partition keys of an OUTER join should include partition key
1703 * expressions from the OUTER side only. However, because all
1704 * commonly-used comparison operators are strict, the presence of nulls on
1705 * the outer side doesn't cause any problem; they can't match anything at
1706 * future join levels anyway. Therefore, we track two sets of
1707 * expressions: those that authentically partition the relation
1708 * (partexprs) and those that partition the relation with the exception
1709 * that extra nulls may be present (nullable_partexprs). When the
1710 * comparison operator is strict, the latter is just as good as the
1711 * former.
1712 */
1713 for (cnt = 0; cnt < partnatts; cnt++)
1714 {
1715 List *outer_expr;
1716 List *outer_null_expr;
1717 List *inner_expr;
1718 List *inner_null_expr;
1719 List *partexpr = NIL;
1720 List *nullable_partexpr = NIL;
1721
1722 outer_expr = list_copy(outer_rel->partexprs[cnt]);
1723 outer_null_expr = list_copy(outer_rel->nullable_partexprs[cnt]);
1724 inner_expr = list_copy(inner_rel->partexprs[cnt]);
1725 inner_null_expr = list_copy(inner_rel->nullable_partexprs[cnt]);
1726
1727 switch (jointype)
1728 {
1729 case JOIN_INNER:
1730 partexpr = list_concat(outer_expr, inner_expr);
1731 nullable_partexpr = list_concat(outer_null_expr,
1732 inner_null_expr);
1733 break;
1734
1735 case JOIN_SEMI:
1736 case JOIN_ANTI:
1737 partexpr = outer_expr;
1738 nullable_partexpr = outer_null_expr;
1739 break;
1740
1741 case JOIN_LEFT:
1742 partexpr = outer_expr;
1743 nullable_partexpr = list_concat(inner_expr,
1744 outer_null_expr);
1745 nullable_partexpr = list_concat(nullable_partexpr,
1746 inner_null_expr);
1747 break;
1748
1749 case JOIN_FULL:
1750 nullable_partexpr = list_concat(outer_expr,
1751 inner_expr);
1752 nullable_partexpr = list_concat(nullable_partexpr,
1753 outer_null_expr);
1754 nullable_partexpr = list_concat(nullable_partexpr,
1755 inner_null_expr);
1756 break;
1757
1758 default:
1759 elog(ERROR, "unrecognized join type: %d", (int) jointype);
1760
1761 }
1762
1763 joinrel->partexprs[cnt] = partexpr;
1764 joinrel->nullable_partexprs[cnt] = nullable_partexpr;
1765 }
1766}
1767
1768/*
1769 * build_child_join_reltarget
1770 * Set up a child-join relation's reltarget from a parent-join relation.
1771 */
1772static void
1773build_child_join_reltarget(PlannerInfo *root,
1774 RelOptInfo *parentrel,
1775 RelOptInfo *childrel,
1776 int nappinfos,
1777 AppendRelInfo **appinfos)
1778{
1779 /* Build the targetlist */
1780 childrel->reltarget->exprs = (List *)
1781 adjust_appendrel_attrs(root,
1782 (Node *) parentrel->reltarget->exprs,
1783 nappinfos, appinfos);
1784
1785 /* Set the cost and width fields */
1786 childrel->reltarget->cost.startup = parentrel->reltarget->cost.startup;
1787 childrel->reltarget->cost.per_tuple = parentrel->reltarget->cost.per_tuple;
1788 childrel->reltarget->width = parentrel->reltarget->width;
1789}
1790