1 /*-------------------------------------------------------------------------
2 *
3 * relnode.c
4 * Relation-node lookup/construction routines
5 *
6 * Portions Copyright (c) 1996-2017, 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/clauses.h"
21 #include "optimizer/cost.h"
22 #include "optimizer/pathnode.h"
23 #include "optimizer/paths.h"
24 #include "optimizer/placeholder.h"
25 #include "optimizer/plancat.h"
26 #include "optimizer/restrictinfo.h"
27 #include "optimizer/tlist.h"
28 #include "utils/hsearch.h"
29
30
31 typedef struct JoinHashEntry
32 {
33 Relids join_relids; /* hash key --- MUST BE FIRST */
34 RelOptInfo *join_rel;
35 } JoinHashEntry;
36
37 static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
38 RelOptInfo *input_rel);
39 static List *build_joinrel_restrictlist(PlannerInfo *root,
40 RelOptInfo *joinrel,
41 RelOptInfo *outer_rel,
42 RelOptInfo *inner_rel);
43 static void build_joinrel_joinlist(RelOptInfo *joinrel,
44 RelOptInfo *outer_rel,
45 RelOptInfo *inner_rel);
46 static List *subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
47 List *joininfo_list,
48 List *new_restrictlist);
49 static List *subbuild_joinrel_joinlist(RelOptInfo *joinrel,
50 List *joininfo_list,
51 List *new_joininfo);
52 static void set_foreign_rel_properties(RelOptInfo *joinrel,
53 RelOptInfo *outer_rel, RelOptInfo *inner_rel);
54 static void add_join_rel(PlannerInfo *root, RelOptInfo *joinrel);
55
56
57 /*
58 * setup_simple_rel_arrays
59 * Prepare the arrays we use for quickly accessing base relations.
60 */
61 void
setup_simple_rel_arrays(PlannerInfo * root)62 setup_simple_rel_arrays(PlannerInfo *root)
63 {
64 Index rti;
65 ListCell *lc;
66
67 /* Arrays are accessed using RT indexes (1..N) */
68 root->simple_rel_array_size = list_length(root->parse->rtable) + 1;
69
70 /* simple_rel_array is initialized to all NULLs */
71 root->simple_rel_array = (RelOptInfo **)
72 palloc0(root->simple_rel_array_size * sizeof(RelOptInfo *));
73
74 /* simple_rte_array is an array equivalent of the rtable list */
75 root->simple_rte_array = (RangeTblEntry **)
76 palloc0(root->simple_rel_array_size * sizeof(RangeTblEntry *));
77 rti = 1;
78 foreach(lc, root->parse->rtable)
79 {
80 RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
81
82 root->simple_rte_array[rti++] = rte;
83 }
84 }
85
86 /*
87 * build_simple_rel
88 * Construct a new RelOptInfo for a base relation or 'other' relation.
89 */
90 RelOptInfo *
build_simple_rel(PlannerInfo * root,int relid,RelOptInfo * parent)91 build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
92 {
93 RelOptInfo *rel;
94 RangeTblEntry *rte;
95
96 /* Rel should not exist already */
97 Assert(relid > 0 && relid < root->simple_rel_array_size);
98 if (root->simple_rel_array[relid] != NULL)
99 elog(ERROR, "rel %d already exists", relid);
100
101 /* Fetch RTE for relation */
102 rte = root->simple_rte_array[relid];
103 Assert(rte != NULL);
104
105 rel = makeNode(RelOptInfo);
106 rel->reloptkind = parent ? RELOPT_OTHER_MEMBER_REL : RELOPT_BASEREL;
107 rel->relids = bms_make_singleton(relid);
108 rel->rows = 0;
109 /* cheap startup cost is interesting iff not all tuples to be retrieved */
110 rel->consider_startup = (root->tuple_fraction > 0);
111 rel->consider_param_startup = false; /* might get changed later */
112 rel->consider_parallel = false; /* might get changed later */
113 rel->reltarget = create_empty_pathtarget();
114 rel->pathlist = NIL;
115 rel->ppilist = NIL;
116 rel->partial_pathlist = NIL;
117 rel->cheapest_startup_path = NULL;
118 rel->cheapest_total_path = NULL;
119 rel->cheapest_unique_path = NULL;
120 rel->cheapest_parameterized_paths = NIL;
121 rel->direct_lateral_relids = NULL;
122 rel->lateral_relids = NULL;
123 rel->relid = relid;
124 rel->rtekind = rte->rtekind;
125 /* min_attr, max_attr, attr_needed, attr_widths are set below */
126 rel->lateral_vars = NIL;
127 rel->lateral_referencers = NULL;
128 rel->indexlist = NIL;
129 rel->statlist = NIL;
130 rel->pages = 0;
131 rel->tuples = 0;
132 rel->allvisfrac = 0;
133 rel->subroot = NULL;
134 rel->subplan_params = NIL;
135 rel->rel_parallel_workers = -1; /* set up in get_relation_info */
136 rel->serverid = InvalidOid;
137 rel->userid = rte->checkAsUser;
138 rel->useridiscurrent = false;
139 rel->fdwroutine = NULL;
140 rel->fdw_private = NULL;
141 rel->unique_for_rels = NIL;
142 rel->non_unique_for_rels = NIL;
143 rel->baserestrictinfo = NIL;
144 rel->baserestrictcost.startup = 0;
145 rel->baserestrictcost.per_tuple = 0;
146 rel->baserestrict_min_security = UINT_MAX;
147 rel->joininfo = NIL;
148 rel->has_eclass_joins = false;
149
150 /*
151 * Pass top parent's relids down the inheritance hierarchy. If the parent
152 * has top_parent_relids set, it's a direct or an indirect child of the
153 * top parent indicated by top_parent_relids. By extension this child is
154 * also an indirect child of that parent.
155 */
156 if (parent)
157 {
158 if (parent->top_parent_relids)
159 rel->top_parent_relids = parent->top_parent_relids;
160 else
161 rel->top_parent_relids = bms_copy(parent->relids);
162 }
163 else
164 rel->top_parent_relids = NULL;
165
166 /* Check type of rtable entry */
167 switch (rte->rtekind)
168 {
169 case RTE_RELATION:
170 /* Table --- retrieve statistics from the system catalogs */
171 get_relation_info(root, rte->relid, rte->inh, rel);
172 break;
173 case RTE_SUBQUERY:
174 case RTE_FUNCTION:
175 case RTE_TABLEFUNC:
176 case RTE_VALUES:
177 case RTE_CTE:
178 case RTE_NAMEDTUPLESTORE:
179
180 /*
181 * Subquery, function, tablefunc, values list, CTE, or ENR --- set
182 * up attr range and arrays
183 *
184 * Note: 0 is included in range to support whole-row Vars
185 */
186 rel->min_attr = 0;
187 rel->max_attr = list_length(rte->eref->colnames);
188 rel->attr_needed = (Relids *)
189 palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(Relids));
190 rel->attr_widths = (int32 *)
191 palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(int32));
192 break;
193 default:
194 elog(ERROR, "unrecognized RTE kind: %d",
195 (int) rte->rtekind);
196 break;
197 }
198
199 /* Save the finished struct in the query's simple_rel_array */
200 root->simple_rel_array[relid] = rel;
201
202 /*
203 * This is a convenient spot at which to note whether rels participating
204 * in the query have any securityQuals attached. If so, increase
205 * root->qual_security_level to ensure it's larger than the maximum
206 * security level needed for securityQuals.
207 */
208 if (rte->securityQuals)
209 root->qual_security_level = Max(root->qual_security_level,
210 list_length(rte->securityQuals));
211
212 /*
213 * If this rel is an appendrel parent, recurse to build "other rel"
214 * RelOptInfos for its children. They are "other rels" because they are
215 * not in the main join tree, but we will need RelOptInfos to plan access
216 * to them.
217 */
218 if (rte->inh)
219 {
220 ListCell *l;
221
222 foreach(l, root->append_rel_list)
223 {
224 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
225
226 /* append_rel_list contains all append rels; ignore others */
227 if (appinfo->parent_relid != relid)
228 continue;
229
230 (void) build_simple_rel(root, appinfo->child_relid,
231 rel);
232 }
233 }
234
235 return rel;
236 }
237
238 /*
239 * find_base_rel
240 * Find a base or other relation entry, which must already exist.
241 */
242 RelOptInfo *
find_base_rel(PlannerInfo * root,int relid)243 find_base_rel(PlannerInfo *root, int relid)
244 {
245 RelOptInfo *rel;
246
247 Assert(relid > 0);
248
249 if (relid < root->simple_rel_array_size)
250 {
251 rel = root->simple_rel_array[relid];
252 if (rel)
253 return rel;
254 }
255
256 elog(ERROR, "no relation entry for relid %d", relid);
257
258 return NULL; /* keep compiler quiet */
259 }
260
261 /*
262 * build_join_rel_hash
263 * Construct the auxiliary hash table for join relations.
264 */
265 static void
build_join_rel_hash(PlannerInfo * root)266 build_join_rel_hash(PlannerInfo *root)
267 {
268 HTAB *hashtab;
269 HASHCTL hash_ctl;
270 ListCell *l;
271
272 /* Create the hash table */
273 MemSet(&hash_ctl, 0, sizeof(hash_ctl));
274 hash_ctl.keysize = sizeof(Relids);
275 hash_ctl.entrysize = sizeof(JoinHashEntry);
276 hash_ctl.hash = bitmap_hash;
277 hash_ctl.match = bitmap_match;
278 hash_ctl.hcxt = CurrentMemoryContext;
279 hashtab = hash_create("JoinRelHashTable",
280 256L,
281 &hash_ctl,
282 HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);
283
284 /* Insert all the already-existing joinrels */
285 foreach(l, root->join_rel_list)
286 {
287 RelOptInfo *rel = (RelOptInfo *) lfirst(l);
288 JoinHashEntry *hentry;
289 bool found;
290
291 hentry = (JoinHashEntry *) hash_search(hashtab,
292 &(rel->relids),
293 HASH_ENTER,
294 &found);
295 Assert(!found);
296 hentry->join_rel = rel;
297 }
298
299 root->join_rel_hash = hashtab;
300 }
301
302 /*
303 * find_join_rel
304 * Returns relation entry corresponding to 'relids' (a set of RT indexes),
305 * or NULL if none exists. This is for join relations.
306 */
307 RelOptInfo *
find_join_rel(PlannerInfo * root,Relids relids)308 find_join_rel(PlannerInfo *root, Relids relids)
309 {
310 /*
311 * Switch to using hash lookup when list grows "too long". The threshold
312 * is arbitrary and is known only here.
313 */
314 if (!root->join_rel_hash && list_length(root->join_rel_list) > 32)
315 build_join_rel_hash(root);
316
317 /*
318 * Use either hashtable lookup or linear search, as appropriate.
319 *
320 * Note: the seemingly redundant hashkey variable is used to avoid taking
321 * the address of relids; unless the compiler is exceedingly smart, doing
322 * so would force relids out of a register and thus probably slow down the
323 * list-search case.
324 */
325 if (root->join_rel_hash)
326 {
327 Relids hashkey = relids;
328 JoinHashEntry *hentry;
329
330 hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
331 &hashkey,
332 HASH_FIND,
333 NULL);
334 if (hentry)
335 return hentry->join_rel;
336 }
337 else
338 {
339 ListCell *l;
340
341 foreach(l, root->join_rel_list)
342 {
343 RelOptInfo *rel = (RelOptInfo *) lfirst(l);
344
345 if (bms_equal(rel->relids, relids))
346 return rel;
347 }
348 }
349
350 return NULL;
351 }
352
353 /*
354 * set_foreign_rel_properties
355 * Set up foreign-join fields if outer and inner relation are foreign
356 * tables (or joins) belonging to the same server and assigned to the same
357 * user to check access permissions as.
358 *
359 * In addition to an exact match of userid, we allow the case where one side
360 * has zero userid (implying current user) and the other side has explicit
361 * userid that happens to equal the current user; but in that case, pushdown of
362 * the join is only valid for the current user. The useridiscurrent field
363 * records whether we had to make such an assumption for this join or any
364 * sub-join.
365 *
366 * Otherwise these fields are left invalid, so GetForeignJoinPaths will not be
367 * called for the join relation.
368 *
369 */
370 static void
set_foreign_rel_properties(RelOptInfo * joinrel,RelOptInfo * outer_rel,RelOptInfo * inner_rel)371 set_foreign_rel_properties(RelOptInfo *joinrel, RelOptInfo *outer_rel,
372 RelOptInfo *inner_rel)
373 {
374 if (OidIsValid(outer_rel->serverid) &&
375 inner_rel->serverid == outer_rel->serverid)
376 {
377 if (inner_rel->userid == outer_rel->userid)
378 {
379 joinrel->serverid = outer_rel->serverid;
380 joinrel->userid = outer_rel->userid;
381 joinrel->useridiscurrent = outer_rel->useridiscurrent || inner_rel->useridiscurrent;
382 joinrel->fdwroutine = outer_rel->fdwroutine;
383 }
384 else if (!OidIsValid(inner_rel->userid) &&
385 outer_rel->userid == GetUserId())
386 {
387 joinrel->serverid = outer_rel->serverid;
388 joinrel->userid = outer_rel->userid;
389 joinrel->useridiscurrent = true;
390 joinrel->fdwroutine = outer_rel->fdwroutine;
391 }
392 else if (!OidIsValid(outer_rel->userid) &&
393 inner_rel->userid == GetUserId())
394 {
395 joinrel->serverid = outer_rel->serverid;
396 joinrel->userid = inner_rel->userid;
397 joinrel->useridiscurrent = true;
398 joinrel->fdwroutine = outer_rel->fdwroutine;
399 }
400 }
401 }
402
403 /*
404 * add_join_rel
405 * Add given join relation to the list of join relations in the given
406 * PlannerInfo. Also add it to the auxiliary hashtable if there is one.
407 */
408 static void
add_join_rel(PlannerInfo * root,RelOptInfo * joinrel)409 add_join_rel(PlannerInfo *root, RelOptInfo *joinrel)
410 {
411 /* GEQO requires us to append the new joinrel to the end of the list! */
412 root->join_rel_list = lappend(root->join_rel_list, joinrel);
413
414 /* store it into the auxiliary hashtable if there is one. */
415 if (root->join_rel_hash)
416 {
417 JoinHashEntry *hentry;
418 bool found;
419
420 hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
421 &(joinrel->relids),
422 HASH_ENTER,
423 &found);
424 Assert(!found);
425 hentry->join_rel = joinrel;
426 }
427 }
428
429 /*
430 * build_join_rel
431 * Returns relation entry corresponding to the union of two given rels,
432 * creating a new relation entry if none already exists.
433 *
434 * 'joinrelids' is the Relids set that uniquely identifies the join
435 * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be
436 * joined
437 * 'sjinfo': join context info
438 * 'restrictlist_ptr': result variable. If not NULL, *restrictlist_ptr
439 * receives the list of RestrictInfo nodes that apply to this
440 * particular pair of joinable relations.
441 *
442 * restrictlist_ptr makes the routine's API a little grotty, but it saves
443 * duplicated calculation of the restrictlist...
444 */
445 RelOptInfo *
build_join_rel(PlannerInfo * root,Relids joinrelids,RelOptInfo * outer_rel,RelOptInfo * inner_rel,SpecialJoinInfo * sjinfo,List ** restrictlist_ptr)446 build_join_rel(PlannerInfo *root,
447 Relids joinrelids,
448 RelOptInfo *outer_rel,
449 RelOptInfo *inner_rel,
450 SpecialJoinInfo *sjinfo,
451 List **restrictlist_ptr)
452 {
453 RelOptInfo *joinrel;
454 List *restrictlist;
455
456 /*
457 * See if we already have a joinrel for this set of base rels.
458 */
459 joinrel = find_join_rel(root, joinrelids);
460
461 if (joinrel)
462 {
463 /*
464 * Yes, so we only need to figure the restrictlist for this particular
465 * pair of component relations.
466 */
467 if (restrictlist_ptr)
468 *restrictlist_ptr = build_joinrel_restrictlist(root,
469 joinrel,
470 outer_rel,
471 inner_rel);
472 return joinrel;
473 }
474
475 /*
476 * Nope, so make one.
477 */
478 joinrel = makeNode(RelOptInfo);
479 joinrel->reloptkind = RELOPT_JOINREL;
480 joinrel->relids = bms_copy(joinrelids);
481 joinrel->rows = 0;
482 /* cheap startup cost is interesting iff not all tuples to be retrieved */
483 joinrel->consider_startup = (root->tuple_fraction > 0);
484 joinrel->consider_param_startup = false;
485 joinrel->consider_parallel = false;
486 joinrel->reltarget = create_empty_pathtarget();
487 joinrel->pathlist = NIL;
488 joinrel->ppilist = NIL;
489 joinrel->partial_pathlist = NIL;
490 joinrel->cheapest_startup_path = NULL;
491 joinrel->cheapest_total_path = NULL;
492 joinrel->cheapest_unique_path = NULL;
493 joinrel->cheapest_parameterized_paths = NIL;
494 /* init direct_lateral_relids from children; we'll finish it up below */
495 joinrel->direct_lateral_relids =
496 bms_union(outer_rel->direct_lateral_relids,
497 inner_rel->direct_lateral_relids);
498 joinrel->lateral_relids = min_join_parameterization(root, joinrel->relids,
499 outer_rel, inner_rel);
500 joinrel->relid = 0; /* indicates not a baserel */
501 joinrel->rtekind = RTE_JOIN;
502 joinrel->min_attr = 0;
503 joinrel->max_attr = 0;
504 joinrel->attr_needed = NULL;
505 joinrel->attr_widths = NULL;
506 joinrel->lateral_vars = NIL;
507 joinrel->lateral_referencers = NULL;
508 joinrel->indexlist = NIL;
509 joinrel->statlist = NIL;
510 joinrel->pages = 0;
511 joinrel->tuples = 0;
512 joinrel->allvisfrac = 0;
513 joinrel->subroot = NULL;
514 joinrel->subplan_params = NIL;
515 joinrel->rel_parallel_workers = -1;
516 joinrel->serverid = InvalidOid;
517 joinrel->userid = InvalidOid;
518 joinrel->useridiscurrent = false;
519 joinrel->fdwroutine = NULL;
520 joinrel->fdw_private = NULL;
521 joinrel->unique_for_rels = NIL;
522 joinrel->non_unique_for_rels = NIL;
523 joinrel->baserestrictinfo = NIL;
524 joinrel->baserestrictcost.startup = 0;
525 joinrel->baserestrictcost.per_tuple = 0;
526 joinrel->baserestrict_min_security = UINT_MAX;
527 joinrel->joininfo = NIL;
528 joinrel->has_eclass_joins = false;
529 joinrel->top_parent_relids = NULL;
530
531 /* Compute information relevant to the foreign relations. */
532 set_foreign_rel_properties(joinrel, outer_rel, inner_rel);
533
534 /*
535 * Create a new tlist containing just the vars that need to be output from
536 * this join (ie, are needed for higher joinclauses or final output).
537 *
538 * NOTE: the tlist order for a join rel will depend on which pair of outer
539 * and inner rels we first try to build it from. But the contents should
540 * be the same regardless.
541 */
542 build_joinrel_tlist(root, joinrel, outer_rel);
543 build_joinrel_tlist(root, joinrel, inner_rel);
544 add_placeholders_to_joinrel(root, joinrel, outer_rel, inner_rel);
545
546 /*
547 * add_placeholders_to_joinrel also took care of adding the ph_lateral
548 * sets of any PlaceHolderVars computed here to direct_lateral_relids, so
549 * now we can finish computing that. This is much like the computation of
550 * the transitively-closed lateral_relids in min_join_parameterization,
551 * except that here we *do* have to consider the added PHVs.
552 */
553 joinrel->direct_lateral_relids =
554 bms_del_members(joinrel->direct_lateral_relids, joinrel->relids);
555 if (bms_is_empty(joinrel->direct_lateral_relids))
556 joinrel->direct_lateral_relids = NULL;
557
558 /*
559 * Construct restrict and join clause lists for the new joinrel. (The
560 * caller might or might not need the restrictlist, but I need it anyway
561 * for set_joinrel_size_estimates().)
562 */
563 restrictlist = build_joinrel_restrictlist(root, joinrel,
564 outer_rel, inner_rel);
565 if (restrictlist_ptr)
566 *restrictlist_ptr = restrictlist;
567 build_joinrel_joinlist(joinrel, outer_rel, inner_rel);
568
569 /*
570 * This is also the right place to check whether the joinrel has any
571 * pending EquivalenceClass joins.
572 */
573 joinrel->has_eclass_joins = has_relevant_eclass_joinclause(root, joinrel);
574
575 /*
576 * Set estimates of the joinrel's size.
577 */
578 set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel,
579 sjinfo, restrictlist);
580
581 /*
582 * Set the consider_parallel flag if this joinrel could potentially be
583 * scanned within a parallel worker. If this flag is false for either
584 * inner_rel or outer_rel, then it must be false for the joinrel also.
585 * Even if both are true, there might be parallel-restricted expressions
586 * in the targetlist or quals.
587 *
588 * Note that if there are more than two rels in this relation, they could
589 * be divided between inner_rel and outer_rel in any arbitrary way. We
590 * assume this doesn't matter, because we should hit all the same baserels
591 * and joinclauses while building up to this joinrel no matter which we
592 * take; therefore, we should make the same decision here however we get
593 * here.
594 */
595 if (inner_rel->consider_parallel && outer_rel->consider_parallel &&
596 is_parallel_safe(root, (Node *) restrictlist) &&
597 is_parallel_safe(root, (Node *) joinrel->reltarget->exprs))
598 joinrel->consider_parallel = true;
599
600 /* Add the joinrel to the PlannerInfo. */
601 add_join_rel(root, joinrel);
602
603 /*
604 * Also, if dynamic-programming join search is active, add the new joinrel
605 * to the appropriate sublist. Note: you might think the Assert on number
606 * of members should be for equality, but some of the level 1 rels might
607 * have been joinrels already, so we can only assert <=.
608 */
609 if (root->join_rel_level)
610 {
611 Assert(root->join_cur_level > 0);
612 Assert(root->join_cur_level <= bms_num_members(joinrel->relids));
613 root->join_rel_level[root->join_cur_level] =
614 lappend(root->join_rel_level[root->join_cur_level], joinrel);
615 }
616
617 return joinrel;
618 }
619
620 /*
621 * min_join_parameterization
622 *
623 * Determine the minimum possible parameterization of a joinrel, that is, the
624 * set of other rels it contains LATERAL references to. We save this value in
625 * the join's RelOptInfo. This function is split out of build_join_rel()
626 * because join_is_legal() needs the value to check a prospective join.
627 */
628 Relids
min_join_parameterization(PlannerInfo * root,Relids joinrelids,RelOptInfo * outer_rel,RelOptInfo * inner_rel)629 min_join_parameterization(PlannerInfo *root,
630 Relids joinrelids,
631 RelOptInfo *outer_rel,
632 RelOptInfo *inner_rel)
633 {
634 Relids result;
635
636 /*
637 * Basically we just need the union of the inputs' lateral_relids, less
638 * whatever is already in the join.
639 *
640 * It's not immediately obvious that this is a valid way to compute the
641 * result, because it might seem that we're ignoring possible lateral refs
642 * of PlaceHolderVars that are due to be computed at the join but not in
643 * either input. However, because create_lateral_join_info() already
644 * charged all such PHV refs to each member baserel of the join, they'll
645 * be accounted for already in the inputs' lateral_relids. Likewise, we
646 * do not need to worry about doing transitive closure here, because that
647 * was already accounted for in the original baserel lateral_relids.
648 */
649 result = bms_union(outer_rel->lateral_relids, inner_rel->lateral_relids);
650 result = bms_del_members(result, joinrelids);
651
652 /* Maintain invariant that result is exactly NULL if empty */
653 if (bms_is_empty(result))
654 result = NULL;
655
656 return result;
657 }
658
659 /*
660 * build_joinrel_tlist
661 * Builds a join relation's target list from an input relation.
662 * (This is invoked twice to handle the two input relations.)
663 *
664 * The join's targetlist includes all Vars of its member relations that
665 * will still be needed above the join. This subroutine adds all such
666 * Vars from the specified input rel's tlist to the join rel's tlist.
667 *
668 * We also compute the expected width of the join's output, making use
669 * of data that was cached at the baserel level by set_rel_width().
670 */
671 static void
build_joinrel_tlist(PlannerInfo * root,RelOptInfo * joinrel,RelOptInfo * input_rel)672 build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
673 RelOptInfo *input_rel)
674 {
675 Relids relids = joinrel->relids;
676 ListCell *vars;
677
678 foreach(vars, input_rel->reltarget->exprs)
679 {
680 Var *var = (Var *) lfirst(vars);
681 RelOptInfo *baserel;
682 int ndx;
683
684 /*
685 * Ignore PlaceHolderVars in the input tlists; we'll make our own
686 * decisions about whether to copy them.
687 */
688 if (IsA(var, PlaceHolderVar))
689 continue;
690
691 /*
692 * Otherwise, anything in a baserel or joinrel targetlist ought to be
693 * a Var. (More general cases can only appear in appendrel child
694 * rels, which will never be seen here.)
695 */
696 if (!IsA(var, Var))
697 elog(ERROR, "unexpected node type in rel targetlist: %d",
698 (int) nodeTag(var));
699
700 /* Get the Var's original base rel */
701 baserel = find_base_rel(root, var->varno);
702
703 /* Is it still needed above this joinrel? */
704 ndx = var->varattno - baserel->min_attr;
705 if (bms_nonempty_difference(baserel->attr_needed[ndx], relids))
706 {
707 /* Yup, add it to the output */
708 joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs, var);
709 /* Vars have cost zero, so no need to adjust reltarget->cost */
710 joinrel->reltarget->width += baserel->attr_widths[ndx];
711 }
712 }
713 }
714
715 /*
716 * build_joinrel_restrictlist
717 * build_joinrel_joinlist
718 * These routines build lists of restriction and join clauses for a
719 * join relation from the joininfo lists of the relations it joins.
720 *
721 * These routines are separate because the restriction list must be
722 * built afresh for each pair of input sub-relations we consider, whereas
723 * the join list need only be computed once for any join RelOptInfo.
724 * The join list is fully determined by the set of rels making up the
725 * joinrel, so we should get the same results (up to ordering) from any
726 * candidate pair of sub-relations. But the restriction list is whatever
727 * is not handled in the sub-relations, so it depends on which
728 * sub-relations are considered.
729 *
730 * If a join clause from an input relation refers to base rels still not
731 * present in the joinrel, then it is still a join clause for the joinrel;
732 * we put it into the joininfo list for the joinrel. Otherwise,
733 * the clause is now a restrict clause for the joined relation, and we
734 * return it to the caller of build_joinrel_restrictlist() to be stored in
735 * join paths made from this pair of sub-relations. (It will not need to
736 * be considered further up the join tree.)
737 *
738 * In many cases we will find the same RestrictInfos in both input
739 * relations' joinlists, so be careful to eliminate duplicates.
740 * Pointer equality should be a sufficient test for dups, since all
741 * the various joinlist entries ultimately refer to RestrictInfos
742 * pushed into them by distribute_restrictinfo_to_rels().
743 *
744 * 'joinrel' is a join relation node
745 * 'outer_rel' and 'inner_rel' are a pair of relations that can be joined
746 * to form joinrel.
747 *
748 * build_joinrel_restrictlist() returns a list of relevant restrictinfos,
749 * whereas build_joinrel_joinlist() stores its results in the joinrel's
750 * joininfo list. One or the other must accept each given clause!
751 *
752 * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass
753 * up to the join relation. I believe this is no longer necessary, because
754 * RestrictInfo nodes are no longer context-dependent. Instead, just include
755 * the original nodes in the lists made for the join relation.
756 */
757 static List *
build_joinrel_restrictlist(PlannerInfo * root,RelOptInfo * joinrel,RelOptInfo * outer_rel,RelOptInfo * inner_rel)758 build_joinrel_restrictlist(PlannerInfo *root,
759 RelOptInfo *joinrel,
760 RelOptInfo *outer_rel,
761 RelOptInfo *inner_rel)
762 {
763 List *result;
764
765 /*
766 * Collect all the clauses that syntactically belong at this level,
767 * eliminating any duplicates (important since we will see many of the
768 * same clauses arriving from both input relations).
769 */
770 result = subbuild_joinrel_restrictlist(joinrel, outer_rel->joininfo, NIL);
771 result = subbuild_joinrel_restrictlist(joinrel, inner_rel->joininfo, result);
772
773 /*
774 * Add on any clauses derived from EquivalenceClasses. These cannot be
775 * redundant with the clauses in the joininfo lists, so don't bother
776 * checking.
777 */
778 result = list_concat(result,
779 generate_join_implied_equalities(root,
780 joinrel->relids,
781 outer_rel->relids,
782 inner_rel));
783
784 return result;
785 }
786
787 static void
build_joinrel_joinlist(RelOptInfo * joinrel,RelOptInfo * outer_rel,RelOptInfo * inner_rel)788 build_joinrel_joinlist(RelOptInfo *joinrel,
789 RelOptInfo *outer_rel,
790 RelOptInfo *inner_rel)
791 {
792 List *result;
793
794 /*
795 * Collect all the clauses that syntactically belong above this level,
796 * eliminating any duplicates (important since we will see many of the
797 * same clauses arriving from both input relations).
798 */
799 result = subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo, NIL);
800 result = subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo, result);
801
802 joinrel->joininfo = result;
803 }
804
805 static List *
subbuild_joinrel_restrictlist(RelOptInfo * joinrel,List * joininfo_list,List * new_restrictlist)806 subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
807 List *joininfo_list,
808 List *new_restrictlist)
809 {
810 ListCell *l;
811
812 foreach(l, joininfo_list)
813 {
814 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
815
816 if (bms_is_subset(rinfo->required_relids, joinrel->relids))
817 {
818 /*
819 * This clause becomes a restriction clause for the joinrel, since
820 * it refers to no outside rels. Add it to the list, being
821 * careful to eliminate duplicates. (Since RestrictInfo nodes in
822 * different joinlists will have been multiply-linked rather than
823 * copied, pointer equality should be a sufficient test.)
824 */
825 new_restrictlist = list_append_unique_ptr(new_restrictlist, rinfo);
826 }
827 else
828 {
829 /*
830 * This clause is still a join clause at this level, so we ignore
831 * it in this routine.
832 */
833 }
834 }
835
836 return new_restrictlist;
837 }
838
839 static List *
subbuild_joinrel_joinlist(RelOptInfo * joinrel,List * joininfo_list,List * new_joininfo)840 subbuild_joinrel_joinlist(RelOptInfo *joinrel,
841 List *joininfo_list,
842 List *new_joininfo)
843 {
844 ListCell *l;
845
846 foreach(l, joininfo_list)
847 {
848 RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
849
850 if (bms_is_subset(rinfo->required_relids, joinrel->relids))
851 {
852 /*
853 * This clause becomes a restriction clause for the joinrel, since
854 * it refers to no outside rels. So we can ignore it in this
855 * routine.
856 */
857 }
858 else
859 {
860 /*
861 * This clause is still a join clause at this level, so add it to
862 * the new joininfo list, being careful to eliminate duplicates.
863 * (Since RestrictInfo nodes in different joinlists will have been
864 * multiply-linked rather than copied, pointer equality should be
865 * a sufficient test.)
866 */
867 new_joininfo = list_append_unique_ptr(new_joininfo, rinfo);
868 }
869 }
870
871 return new_joininfo;
872 }
873
874
875 /*
876 * build_empty_join_rel
877 * Build a dummy join relation describing an empty set of base rels.
878 *
879 * This is used for queries with empty FROM clauses, such as "SELECT 2+2" or
880 * "INSERT INTO foo VALUES(...)". We don't try very hard to make the empty
881 * joinrel completely valid, since no real planning will be done with it ---
882 * we just need it to carry a simple Result path out of query_planner().
883 */
884 RelOptInfo *
build_empty_join_rel(PlannerInfo * root)885 build_empty_join_rel(PlannerInfo *root)
886 {
887 RelOptInfo *joinrel;
888
889 /* The dummy join relation should be the only one ... */
890 Assert(root->join_rel_list == NIL);
891
892 joinrel = makeNode(RelOptInfo);
893 joinrel->reloptkind = RELOPT_JOINREL;
894 joinrel->relids = NULL; /* empty set */
895 joinrel->rows = 1; /* we produce one row for such cases */
896 joinrel->rtekind = RTE_JOIN;
897 joinrel->reltarget = create_empty_pathtarget();
898
899 root->join_rel_list = lappend(root->join_rel_list, joinrel);
900
901 return joinrel;
902 }
903
904
905 /*
906 * fetch_upper_rel
907 * Build a RelOptInfo describing some post-scan/join query processing,
908 * or return a pre-existing one if somebody already built it.
909 *
910 * An "upper" relation is identified by an UpperRelationKind and a Relids set.
911 * The meaning of the Relids set is not specified here, and very likely will
912 * vary for different relation kinds.
913 *
914 * Most of the fields in an upper-level RelOptInfo are not used and are not
915 * set here (though makeNode should ensure they're zeroes). We basically only
916 * care about fields that are of interest to add_path() and set_cheapest().
917 */
918 RelOptInfo *
fetch_upper_rel(PlannerInfo * root,UpperRelationKind kind,Relids relids)919 fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids)
920 {
921 RelOptInfo *upperrel;
922 ListCell *lc;
923
924 /*
925 * For the moment, our indexing data structure is just a List for each
926 * relation kind. If we ever get so many of one kind that this stops
927 * working well, we can improve it. No code outside this function should
928 * assume anything about how to find a particular upperrel.
929 */
930
931 /* If we already made this upperrel for the query, return it */
932 foreach(lc, root->upper_rels[kind])
933 {
934 upperrel = (RelOptInfo *) lfirst(lc);
935
936 if (bms_equal(upperrel->relids, relids))
937 return upperrel;
938 }
939
940 upperrel = makeNode(RelOptInfo);
941 upperrel->reloptkind = RELOPT_UPPER_REL;
942 upperrel->relids = bms_copy(relids);
943
944 /* cheap startup cost is interesting iff not all tuples to be retrieved */
945 upperrel->consider_startup = (root->tuple_fraction > 0);
946 upperrel->consider_param_startup = false;
947 upperrel->consider_parallel = false; /* might get changed later */
948 upperrel->reltarget = create_empty_pathtarget();
949 upperrel->pathlist = NIL;
950 upperrel->cheapest_startup_path = NULL;
951 upperrel->cheapest_total_path = NULL;
952 upperrel->cheapest_unique_path = NULL;
953 upperrel->cheapest_parameterized_paths = NIL;
954
955 root->upper_rels[kind] = lappend(root->upper_rels[kind], upperrel);
956
957 return upperrel;
958 }
959
960
961 /*
962 * find_childrel_appendrelinfo
963 * Get the AppendRelInfo associated with an appendrel child rel.
964 *
965 * This search could be eliminated by storing a link in child RelOptInfos,
966 * but for now it doesn't seem performance-critical. (Also, it might be
967 * difficult to maintain such a link during mutation of the append_rel_list.)
968 */
969 AppendRelInfo *
find_childrel_appendrelinfo(PlannerInfo * root,RelOptInfo * rel)970 find_childrel_appendrelinfo(PlannerInfo *root, RelOptInfo *rel)
971 {
972 Index relid = rel->relid;
973 ListCell *lc;
974
975 /* Should only be called on child rels */
976 Assert(rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
977
978 foreach(lc, root->append_rel_list)
979 {
980 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
981
982 if (appinfo->child_relid == relid)
983 return appinfo;
984 }
985 /* should have found the entry ... */
986 elog(ERROR, "child rel %d not found in append_rel_list", relid);
987 return NULL; /* not reached */
988 }
989
990
991 /*
992 * find_childrel_parents
993 * Compute the set of parent relids of an appendrel child rel.
994 *
995 * Since appendrels can be nested, a child could have multiple levels of
996 * appendrel ancestors. This function computes a Relids set of all the
997 * parent relation IDs.
998 */
999 Relids
find_childrel_parents(PlannerInfo * root,RelOptInfo * rel)1000 find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
1001 {
1002 Relids result = NULL;
1003
1004 Assert(rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
1005
1006 do
1007 {
1008 AppendRelInfo *appinfo = find_childrel_appendrelinfo(root, rel);
1009 Index prelid = appinfo->parent_relid;
1010
1011 result = bms_add_member(result, prelid);
1012
1013 /* traverse up to the parent rel, loop if it's also a child rel */
1014 rel = find_base_rel(root, prelid);
1015 } while (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
1016
1017 Assert(rel->reloptkind == RELOPT_BASEREL);
1018
1019 return result;
1020 }
1021
1022
1023 /*
1024 * get_baserel_parampathinfo
1025 * Get the ParamPathInfo for a parameterized path for a base relation,
1026 * constructing one if we don't have one already.
1027 *
1028 * This centralizes estimating the rowcounts for parameterized paths.
1029 * We need to cache those to be sure we use the same rowcount for all paths
1030 * of the same parameterization for a given rel. This is also a convenient
1031 * place to determine which movable join clauses the parameterized path will
1032 * be responsible for evaluating.
1033 */
1034 ParamPathInfo *
get_baserel_parampathinfo(PlannerInfo * root,RelOptInfo * baserel,Relids required_outer)1035 get_baserel_parampathinfo(PlannerInfo *root, RelOptInfo *baserel,
1036 Relids required_outer)
1037 {
1038 ParamPathInfo *ppi;
1039 Relids joinrelids;
1040 List *pclauses;
1041 double rows;
1042 ListCell *lc;
1043
1044 /* If rel has LATERAL refs, every path for it should account for them */
1045 Assert(bms_is_subset(baserel->lateral_relids, required_outer));
1046
1047 /* Unparameterized paths have no ParamPathInfo */
1048 if (bms_is_empty(required_outer))
1049 return NULL;
1050
1051 Assert(!bms_overlap(baserel->relids, required_outer));
1052
1053 /* If we already have a PPI for this parameterization, just return it */
1054 foreach(lc, baserel->ppilist)
1055 {
1056 ppi = (ParamPathInfo *) lfirst(lc);
1057 if (bms_equal(ppi->ppi_req_outer, required_outer))
1058 return ppi;
1059 }
1060
1061 /*
1062 * Identify all joinclauses that are movable to this base rel given this
1063 * parameterization.
1064 */
1065 joinrelids = bms_union(baserel->relids, required_outer);
1066 pclauses = NIL;
1067 foreach(lc, baserel->joininfo)
1068 {
1069 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1070
1071 if (join_clause_is_movable_into(rinfo,
1072 baserel->relids,
1073 joinrelids))
1074 pclauses = lappend(pclauses, rinfo);
1075 }
1076
1077 /*
1078 * Add in joinclauses generated by EquivalenceClasses, too. (These
1079 * necessarily satisfy join_clause_is_movable_into.)
1080 */
1081 pclauses = list_concat(pclauses,
1082 generate_join_implied_equalities(root,
1083 joinrelids,
1084 required_outer,
1085 baserel));
1086
1087 /* Estimate the number of rows returned by the parameterized scan */
1088 rows = get_parameterized_baserel_size(root, baserel, pclauses);
1089
1090 /* And now we can build the ParamPathInfo */
1091 ppi = makeNode(ParamPathInfo);
1092 ppi->ppi_req_outer = required_outer;
1093 ppi->ppi_rows = rows;
1094 ppi->ppi_clauses = pclauses;
1095 baserel->ppilist = lappend(baserel->ppilist, ppi);
1096
1097 return ppi;
1098 }
1099
1100 /*
1101 * get_joinrel_parampathinfo
1102 * Get the ParamPathInfo for a parameterized path for a join relation,
1103 * constructing one if we don't have one already.
1104 *
1105 * This centralizes estimating the rowcounts for parameterized paths.
1106 * We need to cache those to be sure we use the same rowcount for all paths
1107 * of the same parameterization for a given rel. This is also a convenient
1108 * place to determine which movable join clauses the parameterized path will
1109 * be responsible for evaluating.
1110 *
1111 * outer_path and inner_path are a pair of input paths that can be used to
1112 * construct the join, and restrict_clauses is the list of regular join
1113 * clauses (including clauses derived from EquivalenceClasses) that must be
1114 * applied at the join node when using these inputs.
1115 *
1116 * Unlike the situation for base rels, the set of movable join clauses to be
1117 * enforced at a join varies with the selected pair of input paths, so we
1118 * must calculate that and pass it back, even if we already have a matching
1119 * ParamPathInfo. We handle this by adding any clauses moved down to this
1120 * join to *restrict_clauses, which is an in/out parameter. (The addition
1121 * is done in such a way as to not modify the passed-in List structure.)
1122 *
1123 * Note: when considering a nestloop join, the caller must have removed from
1124 * restrict_clauses any movable clauses that are themselves scheduled to be
1125 * pushed into the right-hand path. We do not do that here since it's
1126 * unnecessary for other join types.
1127 */
1128 ParamPathInfo *
get_joinrel_parampathinfo(PlannerInfo * root,RelOptInfo * joinrel,Path * outer_path,Path * inner_path,SpecialJoinInfo * sjinfo,Relids required_outer,List ** restrict_clauses)1129 get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel,
1130 Path *outer_path,
1131 Path *inner_path,
1132 SpecialJoinInfo *sjinfo,
1133 Relids required_outer,
1134 List **restrict_clauses)
1135 {
1136 ParamPathInfo *ppi;
1137 Relids join_and_req;
1138 Relids outer_and_req;
1139 Relids inner_and_req;
1140 List *pclauses;
1141 List *eclauses;
1142 List *dropped_ecs;
1143 double rows;
1144 ListCell *lc;
1145
1146 /* If rel has LATERAL refs, every path for it should account for them */
1147 Assert(bms_is_subset(joinrel->lateral_relids, required_outer));
1148
1149 /* Unparameterized paths have no ParamPathInfo or extra join clauses */
1150 if (bms_is_empty(required_outer))
1151 return NULL;
1152
1153 Assert(!bms_overlap(joinrel->relids, required_outer));
1154
1155 /*
1156 * Identify all joinclauses that are movable to this join rel given this
1157 * parameterization. These are the clauses that are movable into this
1158 * join, but not movable into either input path. Treat an unparameterized
1159 * input path as not accepting parameterized clauses (because it won't,
1160 * per the shortcut exit above), even though the joinclause movement rules
1161 * might allow the same clauses to be moved into a parameterized path for
1162 * that rel.
1163 */
1164 join_and_req = bms_union(joinrel->relids, required_outer);
1165 if (outer_path->param_info)
1166 outer_and_req = bms_union(outer_path->parent->relids,
1167 PATH_REQ_OUTER(outer_path));
1168 else
1169 outer_and_req = NULL; /* outer path does not accept parameters */
1170 if (inner_path->param_info)
1171 inner_and_req = bms_union(inner_path->parent->relids,
1172 PATH_REQ_OUTER(inner_path));
1173 else
1174 inner_and_req = NULL; /* inner path does not accept parameters */
1175
1176 pclauses = NIL;
1177 foreach(lc, joinrel->joininfo)
1178 {
1179 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1180
1181 if (join_clause_is_movable_into(rinfo,
1182 joinrel->relids,
1183 join_and_req) &&
1184 !join_clause_is_movable_into(rinfo,
1185 outer_path->parent->relids,
1186 outer_and_req) &&
1187 !join_clause_is_movable_into(rinfo,
1188 inner_path->parent->relids,
1189 inner_and_req))
1190 pclauses = lappend(pclauses, rinfo);
1191 }
1192
1193 /* Consider joinclauses generated by EquivalenceClasses, too */
1194 eclauses = generate_join_implied_equalities(root,
1195 join_and_req,
1196 required_outer,
1197 joinrel);
1198 /* We only want ones that aren't movable to lower levels */
1199 dropped_ecs = NIL;
1200 foreach(lc, eclauses)
1201 {
1202 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1203
1204 /*
1205 * In principle, join_clause_is_movable_into() should accept anything
1206 * returned by generate_join_implied_equalities(); but because its
1207 * analysis is only approximate, sometimes it doesn't. So we
1208 * currently cannot use this Assert; instead just assume it's okay to
1209 * apply the joinclause at this level.
1210 */
1211 #ifdef NOT_USED
1212 Assert(join_clause_is_movable_into(rinfo,
1213 joinrel->relids,
1214 join_and_req));
1215 #endif
1216 if (join_clause_is_movable_into(rinfo,
1217 outer_path->parent->relids,
1218 outer_and_req))
1219 continue; /* drop if movable into LHS */
1220 if (join_clause_is_movable_into(rinfo,
1221 inner_path->parent->relids,
1222 inner_and_req))
1223 {
1224 /* drop if movable into RHS, but remember EC for use below */
1225 Assert(rinfo->left_ec == rinfo->right_ec);
1226 dropped_ecs = lappend(dropped_ecs, rinfo->left_ec);
1227 continue;
1228 }
1229 pclauses = lappend(pclauses, rinfo);
1230 }
1231
1232 /*
1233 * EquivalenceClasses are harder to deal with than we could wish, because
1234 * of the fact that a given EC can generate different clauses depending on
1235 * context. Suppose we have an EC {X.X, Y.Y, Z.Z} where X and Y are the
1236 * LHS and RHS of the current join and Z is in required_outer, and further
1237 * suppose that the inner_path is parameterized by both X and Z. The code
1238 * above will have produced either Z.Z = X.X or Z.Z = Y.Y from that EC,
1239 * and in the latter case will have discarded it as being movable into the
1240 * RHS. However, the EC machinery might have produced either Y.Y = X.X or
1241 * Y.Y = Z.Z as the EC enforcement clause within the inner_path; it will
1242 * not have produced both, and we can't readily tell from here which one
1243 * it did pick. If we add no clause to this join, we'll end up with
1244 * insufficient enforcement of the EC; either Z.Z or X.X will fail to be
1245 * constrained to be equal to the other members of the EC. (When we come
1246 * to join Z to this X/Y path, we will certainly drop whichever EC clause
1247 * is generated at that join, so this omission won't get fixed later.)
1248 *
1249 * To handle this, for each EC we discarded such a clause from, try to
1250 * generate a clause connecting the required_outer rels to the join's LHS
1251 * ("Z.Z = X.X" in the terms of the above example). If successful, and if
1252 * the clause can't be moved to the LHS, add it to the current join's
1253 * restriction clauses. (If an EC cannot generate such a clause then it
1254 * has nothing that needs to be enforced here, while if the clause can be
1255 * moved into the LHS then it should have been enforced within that path.)
1256 *
1257 * Note that we don't need similar processing for ECs whose clause was
1258 * considered to be movable into the LHS, because the LHS can't refer to
1259 * the RHS so there is no comparable ambiguity about what it might
1260 * actually be enforcing internally.
1261 */
1262 if (dropped_ecs)
1263 {
1264 Relids real_outer_and_req;
1265
1266 real_outer_and_req = bms_union(outer_path->parent->relids,
1267 required_outer);
1268 eclauses =
1269 generate_join_implied_equalities_for_ecs(root,
1270 dropped_ecs,
1271 real_outer_and_req,
1272 required_outer,
1273 outer_path->parent);
1274 foreach(lc, eclauses)
1275 {
1276 RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1277
1278 /* As above, can't quite assert this here */
1279 #ifdef NOT_USED
1280 Assert(join_clause_is_movable_into(rinfo,
1281 outer_path->parent->relids,
1282 real_outer_and_req));
1283 #endif
1284 if (!join_clause_is_movable_into(rinfo,
1285 outer_path->parent->relids,
1286 outer_and_req))
1287 pclauses = lappend(pclauses, rinfo);
1288 }
1289 }
1290
1291 /*
1292 * Now, attach the identified moved-down clauses to the caller's
1293 * restrict_clauses list. By using list_concat in this order, we leave
1294 * the original list structure of restrict_clauses undamaged.
1295 */
1296 *restrict_clauses = list_concat(pclauses, *restrict_clauses);
1297
1298 /* If we already have a PPI for this parameterization, just return it */
1299 foreach(lc, joinrel->ppilist)
1300 {
1301 ppi = (ParamPathInfo *) lfirst(lc);
1302 if (bms_equal(ppi->ppi_req_outer, required_outer))
1303 return ppi;
1304 }
1305
1306 /* Estimate the number of rows returned by the parameterized join */
1307 rows = get_parameterized_joinrel_size(root, joinrel,
1308 outer_path,
1309 inner_path,
1310 sjinfo,
1311 *restrict_clauses);
1312
1313 /*
1314 * And now we can build the ParamPathInfo. No point in saving the
1315 * input-pair-dependent clause list, though.
1316 *
1317 * Note: in GEQO mode, we'll be called in a temporary memory context, but
1318 * the joinrel structure is there too, so no problem.
1319 */
1320 ppi = makeNode(ParamPathInfo);
1321 ppi->ppi_req_outer = required_outer;
1322 ppi->ppi_rows = rows;
1323 ppi->ppi_clauses = NIL;
1324 joinrel->ppilist = lappend(joinrel->ppilist, ppi);
1325
1326 return ppi;
1327 }
1328
1329 /*
1330 * get_appendrel_parampathinfo
1331 * Get the ParamPathInfo for a parameterized path for an append relation.
1332 *
1333 * For an append relation, the rowcount estimate will just be the sum of
1334 * the estimates for its children. However, we still need a ParamPathInfo
1335 * to flag the fact that the path requires parameters. So this just creates
1336 * a suitable struct with zero ppi_rows (and no ppi_clauses either, since
1337 * the Append node isn't responsible for checking quals).
1338 */
1339 ParamPathInfo *
get_appendrel_parampathinfo(RelOptInfo * appendrel,Relids required_outer)1340 get_appendrel_parampathinfo(RelOptInfo *appendrel, Relids required_outer)
1341 {
1342 ParamPathInfo *ppi;
1343 ListCell *lc;
1344
1345 /* If rel has LATERAL refs, every path for it should account for them */
1346 Assert(bms_is_subset(appendrel->lateral_relids, required_outer));
1347
1348 /* Unparameterized paths have no ParamPathInfo */
1349 if (bms_is_empty(required_outer))
1350 return NULL;
1351
1352 Assert(!bms_overlap(appendrel->relids, required_outer));
1353
1354 /* If we already have a PPI for this parameterization, just return it */
1355 foreach(lc, appendrel->ppilist)
1356 {
1357 ppi = (ParamPathInfo *) lfirst(lc);
1358 if (bms_equal(ppi->ppi_req_outer, required_outer))
1359 return ppi;
1360 }
1361
1362 /* Else build the ParamPathInfo */
1363 ppi = makeNode(ParamPathInfo);
1364 ppi->ppi_req_outer = required_outer;
1365 ppi->ppi_rows = 0;
1366 ppi->ppi_clauses = NIL;
1367 appendrel->ppilist = lappend(appendrel->ppilist, ppi);
1368
1369 return ppi;
1370 }
1371