Line data Source code
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
62 13914 : setup_simple_rel_arrays(PlannerInfo *root)
63 : {
64 : Index rti;
65 : ListCell *lc;
66 :
67 : /* Arrays are accessed using RT indexes (1..N) */
68 13914 : root->simple_rel_array_size = list_length(root->parse->rtable) + 1;
69 :
70 : /* simple_rel_array is initialized to all NULLs */
71 13914 : root->simple_rel_array = (RelOptInfo **)
72 13914 : palloc0(root->simple_rel_array_size * sizeof(RelOptInfo *));
73 :
74 : /* simple_rte_array is an array equivalent of the rtable list */
75 13914 : root->simple_rte_array = (RangeTblEntry **)
76 13914 : palloc0(root->simple_rel_array_size * sizeof(RangeTblEntry *));
77 13914 : rti = 1;
78 41192 : foreach(lc, root->parse->rtable)
79 : {
80 27278 : RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
81 :
82 27278 : root->simple_rte_array[rti++] = rte;
83 : }
84 13914 : }
85 :
86 : /*
87 : * build_simple_rel
88 : * Construct a new RelOptInfo for a base relation or 'other' relation.
89 : */
90 : RelOptInfo *
91 19764 : build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
92 : {
93 : RelOptInfo *rel;
94 : RangeTblEntry *rte;
95 :
96 : /* Rel should not exist already */
97 19764 : Assert(relid > 0 && relid < root->simple_rel_array_size);
98 19764 : if (root->simple_rel_array[relid] != NULL)
99 0 : elog(ERROR, "rel %d already exists", relid);
100 :
101 : /* Fetch RTE for relation */
102 19764 : rte = root->simple_rte_array[relid];
103 19764 : Assert(rte != NULL);
104 :
105 19764 : rel = makeNode(RelOptInfo);
106 19764 : rel->reloptkind = parent ? RELOPT_OTHER_MEMBER_REL : RELOPT_BASEREL;
107 19764 : rel->relids = bms_make_singleton(relid);
108 19764 : rel->rows = 0;
109 : /* cheap startup cost is interesting iff not all tuples to be retrieved */
110 19764 : rel->consider_startup = (root->tuple_fraction > 0);
111 19764 : rel->consider_param_startup = false; /* might get changed later */
112 19764 : rel->consider_parallel = false; /* might get changed later */
113 19764 : rel->reltarget = create_empty_pathtarget();
114 19764 : rel->pathlist = NIL;
115 19764 : rel->ppilist = NIL;
116 19764 : rel->partial_pathlist = NIL;
117 19764 : rel->cheapest_startup_path = NULL;
118 19764 : rel->cheapest_total_path = NULL;
119 19764 : rel->cheapest_unique_path = NULL;
120 19764 : rel->cheapest_parameterized_paths = NIL;
121 19764 : rel->direct_lateral_relids = NULL;
122 19764 : rel->lateral_relids = NULL;
123 19764 : rel->relid = relid;
124 19764 : rel->rtekind = rte->rtekind;
125 : /* min_attr, max_attr, attr_needed, attr_widths are set below */
126 19764 : rel->lateral_vars = NIL;
127 19764 : rel->lateral_referencers = NULL;
128 19764 : rel->indexlist = NIL;
129 19764 : rel->statlist = NIL;
130 19764 : rel->pages = 0;
131 19764 : rel->tuples = 0;
132 19764 : rel->allvisfrac = 0;
133 19764 : rel->subroot = NULL;
134 19764 : rel->subplan_params = NIL;
135 19764 : rel->rel_parallel_workers = -1; /* set up in get_relation_info */
136 19764 : rel->serverid = InvalidOid;
137 19764 : rel->userid = rte->checkAsUser;
138 19764 : rel->useridiscurrent = false;
139 19764 : rel->fdwroutine = NULL;
140 19764 : rel->fdw_private = NULL;
141 19764 : rel->unique_for_rels = NIL;
142 19764 : rel->non_unique_for_rels = NIL;
143 19764 : rel->baserestrictinfo = NIL;
144 19764 : rel->baserestrictcost.startup = 0;
145 19764 : rel->baserestrictcost.per_tuple = 0;
146 19764 : rel->baserestrict_min_security = UINT_MAX;
147 19764 : rel->joininfo = NIL;
148 19764 : 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 19764 : if (parent)
157 : {
158 1571 : if (parent->top_parent_relids)
159 68 : rel->top_parent_relids = parent->top_parent_relids;
160 : else
161 1503 : rel->top_parent_relids = bms_copy(parent->relids);
162 : }
163 : else
164 18193 : rel->top_parent_relids = NULL;
165 :
166 : /* Check type of rtable entry */
167 19764 : switch (rte->rtekind)
168 : {
169 : case RTE_RELATION:
170 : /* Table --- retrieve statistics from the system catalogs */
171 16360 : get_relation_info(root, rte->relid, rte->inh, rel);
172 16358 : 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, or values list --- set up attr
182 : * range and arrays
183 : *
184 : * Note: 0 is included in range to support whole-row Vars
185 : */
186 3404 : rel->min_attr = 0;
187 3404 : rel->max_attr = list_length(rte->eref->colnames);
188 3404 : rel->attr_needed = (Relids *)
189 3404 : palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(Relids));
190 3404 : rel->attr_widths = (int32 *)
191 3404 : palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(int32));
192 3404 : break;
193 : default:
194 0 : 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 19762 : 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 19762 : if (rte->securityQuals)
209 306 : 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 19762 : if (rte->inh)
219 : {
220 : ListCell *l;
221 :
222 2502 : foreach(l, root->append_rel_list)
223 : {
224 1911 : AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(l);
225 :
226 : /* append_rel_list contains all append rels; ignore others */
227 1911 : if (appinfo->parent_relid != relid)
228 340 : continue;
229 :
230 1571 : (void) build_simple_rel(root, appinfo->child_relid,
231 : rel);
232 : }
233 : }
234 :
235 19762 : return rel;
236 : }
237 :
238 : /*
239 : * find_base_rel
240 : * Find a base or other relation entry, which must already exist.
241 : */
242 : RelOptInfo *
243 177593 : find_base_rel(PlannerInfo *root, int relid)
244 : {
245 : RelOptInfo *rel;
246 :
247 177593 : Assert(relid > 0);
248 :
249 177593 : if (relid < root->simple_rel_array_size)
250 : {
251 177593 : rel = root->simple_rel_array[relid];
252 177593 : if (rel)
253 177593 : return rel;
254 : }
255 :
256 0 : 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
266 2 : build_join_rel_hash(PlannerInfo *root)
267 : {
268 : HTAB *hashtab;
269 : HASHCTL hash_ctl;
270 : ListCell *l;
271 :
272 : /* Create the hash table */
273 2 : MemSet(&hash_ctl, 0, sizeof(hash_ctl));
274 2 : hash_ctl.keysize = sizeof(Relids);
275 2 : hash_ctl.entrysize = sizeof(JoinHashEntry);
276 2 : hash_ctl.hash = bitmap_hash;
277 2 : hash_ctl.match = bitmap_match;
278 2 : hash_ctl.hcxt = CurrentMemoryContext;
279 2 : 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 68 : foreach(l, root->join_rel_list)
286 : {
287 66 : RelOptInfo *rel = (RelOptInfo *) lfirst(l);
288 : JoinHashEntry *hentry;
289 : bool found;
290 :
291 66 : hentry = (JoinHashEntry *) hash_search(hashtab,
292 66 : &(rel->relids),
293 : HASH_ENTER,
294 : &found);
295 66 : Assert(!found);
296 66 : hentry->join_rel = rel;
297 : }
298 :
299 2 : root->join_rel_hash = hashtab;
300 2 : }
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 *
308 7735 : 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 7735 : if (!root->join_rel_hash && list_length(root->join_rel_list) > 32)
315 2 : 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 7735 : if (root->join_rel_hash)
326 : {
327 147 : Relids hashkey = relids;
328 : JoinHashEntry *hentry;
329 :
330 147 : hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
331 : &hashkey,
332 : HASH_FIND,
333 : NULL);
334 147 : if (hentry)
335 120 : return hentry->join_rel;
336 : }
337 : else
338 : {
339 : ListCell *l;
340 :
341 36854 : foreach(l, root->join_rel_list)
342 : {
343 31473 : RelOptInfo *rel = (RelOptInfo *) lfirst(l);
344 :
345 31473 : if (bms_equal(rel->relids, relids))
346 2207 : return rel;
347 : }
348 : }
349 :
350 5408 : 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
371 5351 : set_foreign_rel_properties(RelOptInfo *joinrel, RelOptInfo *outer_rel,
372 : RelOptInfo *inner_rel)
373 : {
374 5351 : if (OidIsValid(outer_rel->serverid) &&
375 0 : inner_rel->serverid == outer_rel->serverid)
376 : {
377 0 : if (inner_rel->userid == outer_rel->userid)
378 : {
379 0 : joinrel->serverid = outer_rel->serverid;
380 0 : joinrel->userid = outer_rel->userid;
381 0 : joinrel->useridiscurrent = outer_rel->useridiscurrent || inner_rel->useridiscurrent;
382 0 : joinrel->fdwroutine = outer_rel->fdwroutine;
383 : }
384 0 : else if (!OidIsValid(inner_rel->userid) &&
385 0 : outer_rel->userid == GetUserId())
386 : {
387 0 : joinrel->serverid = outer_rel->serverid;
388 0 : joinrel->userid = outer_rel->userid;
389 0 : joinrel->useridiscurrent = true;
390 0 : joinrel->fdwroutine = outer_rel->fdwroutine;
391 : }
392 0 : else if (!OidIsValid(outer_rel->userid) &&
393 0 : inner_rel->userid == GetUserId())
394 : {
395 0 : joinrel->serverid = outer_rel->serverid;
396 0 : joinrel->userid = inner_rel->userid;
397 0 : joinrel->useridiscurrent = true;
398 0 : joinrel->fdwroutine = outer_rel->fdwroutine;
399 : }
400 : }
401 5351 : }
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
409 5351 : add_join_rel(PlannerInfo *root, RelOptInfo *joinrel)
410 : {
411 : /* GEQO requires us to append the new joinrel to the end of the list! */
412 5351 : root->join_rel_list = lappend(root->join_rel_list, joinrel);
413 :
414 : /* store it into the auxiliary hashtable if there is one. */
415 5351 : if (root->join_rel_hash)
416 : {
417 : JoinHashEntry *hentry;
418 : bool found;
419 :
420 27 : hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
421 27 : &(joinrel->relids),
422 : HASH_ENTER,
423 : &found);
424 27 : Assert(!found);
425 27 : hentry->join_rel = joinrel;
426 : }
427 5351 : }
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 *
446 7501 : 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 7501 : joinrel = find_join_rel(root, joinrelids);
460 :
461 7501 : if (joinrel)
462 : {
463 : /*
464 : * Yes, so we only need to figure the restrictlist for this particular
465 : * pair of component relations.
466 : */
467 2150 : if (restrictlist_ptr)
468 2150 : *restrictlist_ptr = build_joinrel_restrictlist(root,
469 : joinrel,
470 : outer_rel,
471 : inner_rel);
472 2150 : return joinrel;
473 : }
474 :
475 : /*
476 : * Nope, so make one.
477 : */
478 5351 : joinrel = makeNode(RelOptInfo);
479 5351 : joinrel->reloptkind = RELOPT_JOINREL;
480 5351 : joinrel->relids = bms_copy(joinrelids);
481 5351 : joinrel->rows = 0;
482 : /* cheap startup cost is interesting iff not all tuples to be retrieved */
483 5351 : joinrel->consider_startup = (root->tuple_fraction > 0);
484 5351 : joinrel->consider_param_startup = false;
485 5351 : joinrel->consider_parallel = false;
486 5351 : joinrel->reltarget = create_empty_pathtarget();
487 5351 : joinrel->pathlist = NIL;
488 5351 : joinrel->ppilist = NIL;
489 5351 : joinrel->partial_pathlist = NIL;
490 5351 : joinrel->cheapest_startup_path = NULL;
491 5351 : joinrel->cheapest_total_path = NULL;
492 5351 : joinrel->cheapest_unique_path = NULL;
493 5351 : joinrel->cheapest_parameterized_paths = NIL;
494 : /* init direct_lateral_relids from children; we'll finish it up below */
495 5351 : joinrel->direct_lateral_relids =
496 5351 : bms_union(outer_rel->direct_lateral_relids,
497 5351 : inner_rel->direct_lateral_relids);
498 5351 : joinrel->lateral_relids = min_join_parameterization(root, joinrel->relids,
499 : outer_rel, inner_rel);
500 5351 : joinrel->relid = 0; /* indicates not a baserel */
501 5351 : joinrel->rtekind = RTE_JOIN;
502 5351 : joinrel->min_attr = 0;
503 5351 : joinrel->max_attr = 0;
504 5351 : joinrel->attr_needed = NULL;
505 5351 : joinrel->attr_widths = NULL;
506 5351 : joinrel->lateral_vars = NIL;
507 5351 : joinrel->lateral_referencers = NULL;
508 5351 : joinrel->indexlist = NIL;
509 5351 : joinrel->statlist = NIL;
510 5351 : joinrel->pages = 0;
511 5351 : joinrel->tuples = 0;
512 5351 : joinrel->allvisfrac = 0;
513 5351 : joinrel->subroot = NULL;
514 5351 : joinrel->subplan_params = NIL;
515 5351 : joinrel->rel_parallel_workers = -1;
516 5351 : joinrel->serverid = InvalidOid;
517 5351 : joinrel->userid = InvalidOid;
518 5351 : joinrel->useridiscurrent = false;
519 5351 : joinrel->fdwroutine = NULL;
520 5351 : joinrel->fdw_private = NULL;
521 5351 : joinrel->unique_for_rels = NIL;
522 5351 : joinrel->non_unique_for_rels = NIL;
523 5351 : joinrel->baserestrictinfo = NIL;
524 5351 : joinrel->baserestrictcost.startup = 0;
525 5351 : joinrel->baserestrictcost.per_tuple = 0;
526 5351 : joinrel->baserestrict_min_security = UINT_MAX;
527 5351 : joinrel->joininfo = NIL;
528 5351 : joinrel->has_eclass_joins = false;
529 5351 : joinrel->top_parent_relids = NULL;
530 :
531 : /* Compute information relevant to the foreign relations. */
532 5351 : 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 5351 : build_joinrel_tlist(root, joinrel, outer_rel);
543 5351 : build_joinrel_tlist(root, joinrel, inner_rel);
544 5351 : 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 5351 : joinrel->direct_lateral_relids =
554 5351 : bms_del_members(joinrel->direct_lateral_relids, joinrel->relids);
555 5351 : if (bms_is_empty(joinrel->direct_lateral_relids))
556 5313 : 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 5351 : restrictlist = build_joinrel_restrictlist(root, joinrel,
564 : outer_rel, inner_rel);
565 5351 : if (restrictlist_ptr)
566 5351 : *restrictlist_ptr = restrictlist;
567 5351 : 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 5351 : joinrel->has_eclass_joins = has_relevant_eclass_joinclause(root, joinrel);
574 :
575 : /*
576 : * Set estimates of the joinrel's size.
577 : */
578 5351 : 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 9105 : if (inner_rel->consider_parallel && outer_rel->consider_parallel &&
596 7502 : is_parallel_safe(root, (Node *) restrictlist) &&
597 3748 : is_parallel_safe(root, (Node *) joinrel->reltarget->exprs))
598 3747 : joinrel->consider_parallel = true;
599 :
600 : /* Add the joinrel to the PlannerInfo. */
601 5351 : 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 5351 : if (root->join_rel_level)
610 : {
611 4835 : Assert(root->join_cur_level > 0);
612 4835 : Assert(root->join_cur_level <= bms_num_members(joinrel->relids));
613 9670 : root->join_rel_level[root->join_cur_level] =
614 4835 : lappend(root->join_rel_level[root->join_cur_level], joinrel);
615 : }
616 :
617 5351 : 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
629 5898 : 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 5898 : result = bms_union(outer_rel->lateral_relids, inner_rel->lateral_relids);
650 5898 : result = bms_del_members(result, joinrelids);
651 :
652 : /* Maintain invariant that result is exactly NULL if empty */
653 5898 : if (bms_is_empty(result))
654 5767 : result = NULL;
655 :
656 5898 : 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
672 10702 : build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
673 : RelOptInfo *input_rel)
674 : {
675 10702 : Relids relids = joinrel->relids;
676 : ListCell *vars;
677 :
678 38940 : foreach(vars, input_rel->reltarget->exprs)
679 : {
680 28238 : 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 28238 : if (IsA(var, PlaceHolderVar))
689 107 : 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 28131 : if (!IsA(var, Var))
697 0 : elog(ERROR, "unexpected node type in rel targetlist: %d",
698 : (int) nodeTag(var));
699 :
700 : /* Get the Var's original base rel */
701 28131 : baserel = find_base_rel(root, var->varno);
702 :
703 : /* Is it still needed above this joinrel? */
704 28131 : ndx = var->varattno - baserel->min_attr;
705 28131 : if (bms_nonempty_difference(baserel->attr_needed[ndx], relids))
706 : {
707 : /* Yup, add it to the output */
708 20601 : joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs, var);
709 : /* Vars have cost zero, so no need to adjust reltarget->cost */
710 20601 : joinrel->reltarget->width += baserel->attr_widths[ndx];
711 : }
712 : }
713 10702 : }
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 case 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 *
758 7501 : 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 7501 : result = subbuild_joinrel_restrictlist(joinrel, outer_rel->joininfo, NIL);
771 7501 : 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 7501 : result = list_concat(result,
779 : generate_join_implied_equalities(root,
780 : joinrel->relids,
781 : outer_rel->relids,
782 : inner_rel));
783 :
784 7501 : return result;
785 : }
786 :
787 : static void
788 5351 : 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 5351 : result = subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo, NIL);
800 5351 : result = subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo, result);
801 :
802 5351 : joinrel->joininfo = result;
803 5351 : }
804 :
805 : static List *
806 15002 : subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
807 : List *joininfo_list,
808 : List *new_restrictlist)
809 : {
810 : ListCell *l;
811 :
812 25811 : foreach(l, joininfo_list)
813 : {
814 10809 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
815 :
816 10809 : 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 5338 : 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 15002 : return new_restrictlist;
837 : }
838 :
839 : static List *
840 10702 : subbuild_joinrel_joinlist(RelOptInfo *joinrel,
841 : List *joininfo_list,
842 : List *new_joininfo)
843 : {
844 : ListCell *l;
845 :
846 17068 : foreach(l, joininfo_list)
847 : {
848 6366 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
849 :
850 6366 : 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 2738 : new_joininfo = list_append_unique_ptr(new_joininfo, rinfo);
868 : }
869 : }
870 :
871 10702 : 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 *
885 11429 : build_empty_join_rel(PlannerInfo *root)
886 : {
887 : RelOptInfo *joinrel;
888 :
889 : /* The dummy join relation should be the only one ... */
890 11429 : Assert(root->join_rel_list == NIL);
891 :
892 11429 : joinrel = makeNode(RelOptInfo);
893 11429 : joinrel->reloptkind = RELOPT_JOINREL;
894 11429 : joinrel->relids = NULL; /* empty set */
895 11429 : joinrel->rows = 1; /* we produce one row for such cases */
896 11429 : joinrel->rtekind = RTE_JOIN;
897 11429 : joinrel->reltarget = create_empty_pathtarget();
898 :
899 11429 : root->join_rel_list = lappend(root->join_rel_list, joinrel);
900 :
901 11429 : 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 *
919 84544 : 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 84544 : foreach(lc, root->upper_rels[kind])
933 : {
934 53760 : upperrel = (RelOptInfo *) lfirst(lc);
935 :
936 53760 : if (bms_equal(upperrel->relids, relids))
937 53760 : return upperrel;
938 : }
939 :
940 30784 : upperrel = makeNode(RelOptInfo);
941 30784 : upperrel->reloptkind = RELOPT_UPPER_REL;
942 30784 : upperrel->relids = bms_copy(relids);
943 :
944 : /* cheap startup cost is interesting iff not all tuples to be retrieved */
945 30784 : upperrel->consider_startup = (root->tuple_fraction > 0);
946 30784 : upperrel->consider_param_startup = false;
947 30784 : upperrel->consider_parallel = false; /* might get changed later */
948 30784 : upperrel->reltarget = create_empty_pathtarget();
949 30784 : upperrel->pathlist = NIL;
950 30784 : upperrel->cheapest_startup_path = NULL;
951 30784 : upperrel->cheapest_total_path = NULL;
952 30784 : upperrel->cheapest_unique_path = NULL;
953 30784 : upperrel->cheapest_parameterized_paths = NIL;
954 :
955 30784 : root->upper_rels[kind] = lappend(root->upper_rels[kind], upperrel);
956 :
957 30784 : 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 *
970 277 : find_childrel_appendrelinfo(PlannerInfo *root, RelOptInfo *rel)
971 : {
972 277 : Index relid = rel->relid;
973 : ListCell *lc;
974 :
975 : /* Should only be called on child rels */
976 277 : Assert(rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
977 :
978 817 : foreach(lc, root->append_rel_list)
979 : {
980 817 : AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
981 :
982 817 : if (appinfo->child_relid == relid)
983 277 : return appinfo;
984 : }
985 : /* should have found the entry ... */
986 0 : 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
1000 201 : find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
1001 : {
1002 201 : Relids result = NULL;
1003 :
1004 201 : Assert(rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
1005 :
1006 : do
1007 : {
1008 277 : AppendRelInfo *appinfo = find_childrel_appendrelinfo(root, rel);
1009 277 : Index prelid = appinfo->parent_relid;
1010 :
1011 277 : result = bms_add_member(result, prelid);
1012 :
1013 : /* traverse up to the parent rel, loop if it's also a child rel */
1014 277 : rel = find_base_rel(root, prelid);
1015 277 : } while (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
1016 :
1017 201 : Assert(rel->reloptkind == RELOPT_BASEREL);
1018 :
1019 201 : 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 *
1035 56440 : 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 : /* Unparameterized paths have no ParamPathInfo */
1045 56440 : if (bms_is_empty(required_outer))
1046 47389 : return NULL;
1047 :
1048 9051 : Assert(!bms_overlap(baserel->relids, required_outer));
1049 :
1050 : /* If we already have a PPI for this parameterization, just return it */
1051 9051 : if ((ppi = find_param_path_info(baserel, required_outer)))
1052 5392 : return ppi;
1053 :
1054 : /*
1055 : * Identify all joinclauses that are movable to this base rel given this
1056 : * parameterization.
1057 : */
1058 3659 : joinrelids = bms_union(baserel->relids, required_outer);
1059 3659 : pclauses = NIL;
1060 5711 : foreach(lc, baserel->joininfo)
1061 : {
1062 2052 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1063 :
1064 2052 : if (join_clause_is_movable_into(rinfo,
1065 : baserel->relids,
1066 : joinrelids))
1067 1145 : pclauses = lappend(pclauses, rinfo);
1068 : }
1069 :
1070 : /*
1071 : * Add in joinclauses generated by EquivalenceClasses, too. (These
1072 : * necessarily satisfy join_clause_is_movable_into.)
1073 : */
1074 3659 : pclauses = list_concat(pclauses,
1075 : generate_join_implied_equalities(root,
1076 : joinrelids,
1077 : required_outer,
1078 : baserel));
1079 :
1080 : /* Estimate the number of rows returned by the parameterized scan */
1081 3659 : rows = get_parameterized_baserel_size(root, baserel, pclauses);
1082 :
1083 : /* And now we can build the ParamPathInfo */
1084 3659 : ppi = makeNode(ParamPathInfo);
1085 3659 : ppi->ppi_req_outer = required_outer;
1086 3659 : ppi->ppi_rows = rows;
1087 3659 : ppi->ppi_clauses = pclauses;
1088 3659 : baserel->ppilist = lappend(baserel->ppilist, ppi);
1089 :
1090 3659 : return ppi;
1091 : }
1092 :
1093 : /*
1094 : * get_joinrel_parampathinfo
1095 : * Get the ParamPathInfo for a parameterized path for a join relation,
1096 : * constructing one if we don't have one already.
1097 : *
1098 : * This centralizes estimating the rowcounts for parameterized paths.
1099 : * We need to cache those to be sure we use the same rowcount for all paths
1100 : * of the same parameterization for a given rel. This is also a convenient
1101 : * place to determine which movable join clauses the parameterized path will
1102 : * be responsible for evaluating.
1103 : *
1104 : * outer_path and inner_path are a pair of input paths that can be used to
1105 : * construct the join, and restrict_clauses is the list of regular join
1106 : * clauses (including clauses derived from EquivalenceClasses) that must be
1107 : * applied at the join node when using these inputs.
1108 : *
1109 : * Unlike the situation for base rels, the set of movable join clauses to be
1110 : * enforced at a join varies with the selected pair of input paths, so we
1111 : * must calculate that and pass it back, even if we already have a matching
1112 : * ParamPathInfo. We handle this by adding any clauses moved down to this
1113 : * join to *restrict_clauses, which is an in/out parameter. (The addition
1114 : * is done in such a way as to not modify the passed-in List structure.)
1115 : *
1116 : * Note: when considering a nestloop join, the caller must have removed from
1117 : * restrict_clauses any movable clauses that are themselves scheduled to be
1118 : * pushed into the right-hand path. We do not do that here since it's
1119 : * unnecessary for other join types.
1120 : */
1121 : ParamPathInfo *
1122 39489 : get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel,
1123 : Path *outer_path,
1124 : Path *inner_path,
1125 : SpecialJoinInfo *sjinfo,
1126 : Relids required_outer,
1127 : List **restrict_clauses)
1128 : {
1129 : ParamPathInfo *ppi;
1130 : Relids join_and_req;
1131 : Relids outer_and_req;
1132 : Relids inner_and_req;
1133 : List *pclauses;
1134 : List *eclauses;
1135 : List *dropped_ecs;
1136 : double rows;
1137 : ListCell *lc;
1138 :
1139 : /* Unparameterized paths have no ParamPathInfo or extra join clauses */
1140 39489 : if (bms_is_empty(required_outer))
1141 38914 : return NULL;
1142 :
1143 575 : Assert(!bms_overlap(joinrel->relids, required_outer));
1144 :
1145 : /*
1146 : * Identify all joinclauses that are movable to this join rel given this
1147 : * parameterization. These are the clauses that are movable into this
1148 : * join, but not movable into either input path. Treat an unparameterized
1149 : * input path as not accepting parameterized clauses (because it won't,
1150 : * per the shortcut exit above), even though the joinclause movement rules
1151 : * might allow the same clauses to be moved into a parameterized path for
1152 : * that rel.
1153 : */
1154 575 : join_and_req = bms_union(joinrel->relids, required_outer);
1155 575 : if (outer_path->param_info)
1156 840 : outer_and_req = bms_union(outer_path->parent->relids,
1157 840 : PATH_REQ_OUTER(outer_path));
1158 : else
1159 155 : outer_and_req = NULL; /* outer path does not accept parameters */
1160 575 : if (inner_path->param_info)
1161 574 : inner_and_req = bms_union(inner_path->parent->relids,
1162 574 : PATH_REQ_OUTER(inner_path));
1163 : else
1164 288 : inner_and_req = NULL; /* inner path does not accept parameters */
1165 :
1166 575 : pclauses = NIL;
1167 1268 : foreach(lc, joinrel->joininfo)
1168 : {
1169 693 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1170 :
1171 693 : if (join_clause_is_movable_into(rinfo,
1172 : joinrel->relids,
1173 408 : join_and_req) &&
1174 408 : !join_clause_is_movable_into(rinfo,
1175 408 : outer_path->parent->relids,
1176 59 : outer_and_req) &&
1177 59 : !join_clause_is_movable_into(rinfo,
1178 59 : inner_path->parent->relids,
1179 : inner_and_req))
1180 4 : pclauses = lappend(pclauses, rinfo);
1181 : }
1182 :
1183 : /* Consider joinclauses generated by EquivalenceClasses, too */
1184 575 : eclauses = generate_join_implied_equalities(root,
1185 : join_and_req,
1186 : required_outer,
1187 : joinrel);
1188 : /* We only want ones that aren't movable to lower levels */
1189 575 : dropped_ecs = NIL;
1190 734 : foreach(lc, eclauses)
1191 : {
1192 159 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1193 :
1194 : /*
1195 : * In principle, join_clause_is_movable_into() should accept anything
1196 : * returned by generate_join_implied_equalities(); but because its
1197 : * analysis is only approximate, sometimes it doesn't. So we
1198 : * currently cannot use this Assert; instead just assume it's okay to
1199 : * apply the joinclause at this level.
1200 : */
1201 : #ifdef NOT_USED
1202 : Assert(join_clause_is_movable_into(rinfo,
1203 : joinrel->relids,
1204 : join_and_req));
1205 : #endif
1206 159 : if (join_clause_is_movable_into(rinfo,
1207 159 : outer_path->parent->relids,
1208 : outer_and_req))
1209 44 : continue; /* drop if movable into LHS */
1210 115 : if (join_clause_is_movable_into(rinfo,
1211 115 : inner_path->parent->relids,
1212 : inner_and_req))
1213 : {
1214 : /* drop if movable into RHS, but remember EC for use below */
1215 65 : Assert(rinfo->left_ec == rinfo->right_ec);
1216 65 : dropped_ecs = lappend(dropped_ecs, rinfo->left_ec);
1217 65 : continue;
1218 : }
1219 50 : pclauses = lappend(pclauses, rinfo);
1220 : }
1221 :
1222 : /*
1223 : * EquivalenceClasses are harder to deal with than we could wish, because
1224 : * of the fact that a given EC can generate different clauses depending on
1225 : * context. Suppose we have an EC {X.X, Y.Y, Z.Z} where X and Y are the
1226 : * LHS and RHS of the current join and Z is in required_outer, and further
1227 : * suppose that the inner_path is parameterized by both X and Z. The code
1228 : * above will have produced either Z.Z = X.X or Z.Z = Y.Y from that EC,
1229 : * and in the latter case will have discarded it as being movable into the
1230 : * RHS. However, the EC machinery might have produced either Y.Y = X.X or
1231 : * Y.Y = Z.Z as the EC enforcement clause within the inner_path; it will
1232 : * not have produced both, and we can't readily tell from here which one
1233 : * it did pick. If we add no clause to this join, we'll end up with
1234 : * insufficient enforcement of the EC; either Z.Z or X.X will fail to be
1235 : * constrained to be equal to the other members of the EC. (When we come
1236 : * to join Z to this X/Y path, we will certainly drop whichever EC clause
1237 : * is generated at that join, so this omission won't get fixed later.)
1238 : *
1239 : * To handle this, for each EC we discarded such a clause from, try to
1240 : * generate a clause connecting the required_outer rels to the join's LHS
1241 : * ("Z.Z = X.X" in the terms of the above example). If successful, and if
1242 : * the clause can't be moved to the LHS, add it to the current join's
1243 : * restriction clauses. (If an EC cannot generate such a clause then it
1244 : * has nothing that needs to be enforced here, while if the clause can be
1245 : * moved into the LHS then it should have been enforced within that path.)
1246 : *
1247 : * Note that we don't need similar processing for ECs whose clause was
1248 : * considered to be movable into the LHS, because the LHS can't refer to
1249 : * the RHS so there is no comparable ambiguity about what it might
1250 : * actually be enforcing internally.
1251 : */
1252 575 : if (dropped_ecs)
1253 : {
1254 : Relids real_outer_and_req;
1255 :
1256 60 : real_outer_and_req = bms_union(outer_path->parent->relids,
1257 : required_outer);
1258 60 : eclauses =
1259 60 : generate_join_implied_equalities_for_ecs(root,
1260 : dropped_ecs,
1261 : real_outer_and_req,
1262 : required_outer,
1263 : outer_path->parent);
1264 65 : foreach(lc, eclauses)
1265 : {
1266 5 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1267 :
1268 : /* As above, can't quite assert this here */
1269 : #ifdef NOT_USED
1270 : Assert(join_clause_is_movable_into(rinfo,
1271 : outer_path->parent->relids,
1272 : real_outer_and_req));
1273 : #endif
1274 5 : if (!join_clause_is_movable_into(rinfo,
1275 5 : outer_path->parent->relids,
1276 : outer_and_req))
1277 3 : pclauses = lappend(pclauses, rinfo);
1278 : }
1279 : }
1280 :
1281 : /*
1282 : * Now, attach the identified moved-down clauses to the caller's
1283 : * restrict_clauses list. By using list_concat in this order, we leave
1284 : * the original list structure of restrict_clauses undamaged.
1285 : */
1286 575 : *restrict_clauses = list_concat(pclauses, *restrict_clauses);
1287 :
1288 : /* If we already have a PPI for this parameterization, just return it */
1289 575 : if ((ppi = find_param_path_info(joinrel, required_outer)))
1290 399 : return ppi;
1291 :
1292 : /* Estimate the number of rows returned by the parameterized join */
1293 176 : rows = get_parameterized_joinrel_size(root, joinrel,
1294 : outer_path,
1295 : inner_path,
1296 : sjinfo,
1297 : *restrict_clauses);
1298 :
1299 : /*
1300 : * And now we can build the ParamPathInfo. No point in saving the
1301 : * input-pair-dependent clause list, though.
1302 : *
1303 : * Note: in GEQO mode, we'll be called in a temporary memory context, but
1304 : * the joinrel structure is there too, so no problem.
1305 : */
1306 176 : ppi = makeNode(ParamPathInfo);
1307 176 : ppi->ppi_req_outer = required_outer;
1308 176 : ppi->ppi_rows = rows;
1309 176 : ppi->ppi_clauses = NIL;
1310 176 : joinrel->ppilist = lappend(joinrel->ppilist, ppi);
1311 :
1312 176 : return ppi;
1313 : }
1314 :
1315 : /*
1316 : * get_appendrel_parampathinfo
1317 : * Get the ParamPathInfo for a parameterized path for an append relation.
1318 : *
1319 : * For an append relation, the rowcount estimate will just be the sum of
1320 : * the estimates for its children. However, we still need a ParamPathInfo
1321 : * to flag the fact that the path requires parameters. So this just creates
1322 : * a suitable struct with zero ppi_rows (and no ppi_clauses either, since
1323 : * the Append node isn't responsible for checking quals).
1324 : */
1325 : ParamPathInfo *
1326 1150 : get_appendrel_parampathinfo(RelOptInfo *appendrel, Relids required_outer)
1327 : {
1328 : ParamPathInfo *ppi;
1329 :
1330 : /* Unparameterized paths have no ParamPathInfo */
1331 1150 : if (bms_is_empty(required_outer))
1332 1097 : return NULL;
1333 :
1334 53 : Assert(!bms_overlap(appendrel->relids, required_outer));
1335 :
1336 : /* If we already have a PPI for this parameterization, just return it */
1337 53 : if ((ppi = find_param_path_info(appendrel, required_outer)))
1338 0 : return ppi;
1339 :
1340 : /* Else build the ParamPathInfo */
1341 53 : ppi = makeNode(ParamPathInfo);
1342 53 : ppi->ppi_req_outer = required_outer;
1343 53 : ppi->ppi_rows = 0;
1344 53 : ppi->ppi_clauses = NIL;
1345 53 : appendrel->ppilist = lappend(appendrel->ppilist, ppi);
1346 :
1347 53 : return ppi;
1348 : }
1349 :
1350 : /*
1351 : * Returns a ParamPathInfo for the parameterization given by required_outer, if
1352 : * already available in the given rel. Returns NULL otherwise.
1353 : */
1354 : ParamPathInfo *
1355 9679 : find_param_path_info(RelOptInfo *rel, Relids required_outer)
1356 : {
1357 : ListCell *lc;
1358 :
1359 10788 : foreach(lc, rel->ppilist)
1360 : {
1361 6900 : ParamPathInfo *ppi = (ParamPathInfo *) lfirst(lc);
1362 :
1363 6900 : if (bms_equal(ppi->ppi_req_outer, required_outer))
1364 5791 : return ppi;
1365 : }
1366 :
1367 3888 : return NULL;
1368 : }
|
