Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * relnode.c
4 : * Relation-node lookup/construction routines
5 : *
6 : * Portions Copyright (c) 1996-2026, 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 "access/nbtree.h"
20 : #include "catalog/pg_constraint.h"
21 : #include "miscadmin.h"
22 : #include "nodes/nodeFuncs.h"
23 : #include "optimizer/appendinfo.h"
24 : #include "optimizer/clauses.h"
25 : #include "optimizer/cost.h"
26 : #include "optimizer/inherit.h"
27 : #include "optimizer/optimizer.h"
28 : #include "optimizer/pathnode.h"
29 : #include "optimizer/paths.h"
30 : #include "optimizer/placeholder.h"
31 : #include "optimizer/plancat.h"
32 : #include "optimizer/planner.h"
33 : #include "optimizer/restrictinfo.h"
34 : #include "optimizer/tlist.h"
35 : #include "parser/parse_oper.h"
36 : #include "parser/parse_relation.h"
37 : #include "rewrite/rewriteManip.h"
38 : #include "utils/hsearch.h"
39 : #include "utils/lsyscache.h"
40 : #include "utils/selfuncs.h"
41 : #include "utils/typcache.h"
42 :
43 :
44 : typedef struct JoinHashEntry
45 : {
46 : Relids join_relids; /* hash key --- MUST BE FIRST */
47 : RelOptInfo *join_rel;
48 : } JoinHashEntry;
49 :
50 : /* Hook for plugins to get control in build_simple_rel() */
51 : build_simple_rel_hook_type build_simple_rel_hook = NULL;
52 :
53 : /* Hook for plugins to get control during joinrel setup */
54 : joinrel_setup_hook_type joinrel_setup_hook = NULL;
55 :
56 : static void build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
57 : RelOptInfo *input_rel,
58 : SpecialJoinInfo *sjinfo,
59 : List *pushed_down_joins,
60 : bool can_null);
61 : static List *build_joinrel_restrictlist(PlannerInfo *root,
62 : RelOptInfo *joinrel,
63 : RelOptInfo *outer_rel,
64 : RelOptInfo *inner_rel,
65 : SpecialJoinInfo *sjinfo);
66 : static void build_joinrel_joinlist(RelOptInfo *joinrel,
67 : RelOptInfo *outer_rel,
68 : RelOptInfo *inner_rel);
69 : static List *subbuild_joinrel_restrictlist(PlannerInfo *root,
70 : RelOptInfo *joinrel,
71 : RelOptInfo *input_rel,
72 : Relids both_input_relids,
73 : List *new_restrictlist);
74 : static List *subbuild_joinrel_joinlist(RelOptInfo *joinrel,
75 : List *joininfo_list,
76 : List *new_joininfo);
77 : static void set_foreign_rel_properties(RelOptInfo *joinrel,
78 : RelOptInfo *outer_rel, RelOptInfo *inner_rel);
79 : static void add_join_rel(PlannerInfo *root, RelOptInfo *joinrel);
80 : static void build_joinrel_partition_info(PlannerInfo *root,
81 : RelOptInfo *joinrel,
82 : RelOptInfo *outer_rel, RelOptInfo *inner_rel,
83 : SpecialJoinInfo *sjinfo,
84 : List *restrictlist);
85 : static bool have_partkey_equi_join(PlannerInfo *root, RelOptInfo *joinrel,
86 : RelOptInfo *rel1, RelOptInfo *rel2,
87 : JoinType jointype, List *restrictlist);
88 : static int match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel,
89 : bool strict_op);
90 : static void set_joinrel_partition_key_exprs(RelOptInfo *joinrel,
91 : RelOptInfo *outer_rel, RelOptInfo *inner_rel,
92 : JoinType jointype);
93 : static void build_child_join_reltarget(PlannerInfo *root,
94 : RelOptInfo *parentrel,
95 : RelOptInfo *childrel,
96 : int nappinfos,
97 : AppendRelInfo **appinfos);
98 : static bool eager_aggregation_possible_for_relation(PlannerInfo *root,
99 : RelOptInfo *rel);
100 : static bool init_grouping_targets(PlannerInfo *root, RelOptInfo *rel,
101 : PathTarget *target, PathTarget *agg_input,
102 : List **group_clauses, List **group_exprs);
103 : static bool is_var_in_aggref_only(PlannerInfo *root, Var *var);
104 : static bool is_var_needed_by_join(PlannerInfo *root, Var *var, RelOptInfo *rel);
105 : static Index get_expression_sortgroupref(PlannerInfo *root, Expr *expr);
106 :
107 :
108 : /*
109 : * setup_simple_rel_arrays
110 : * Prepare the arrays we use for quickly accessing base relations
111 : * and AppendRelInfos.
112 : */
113 : void
114 417423 : setup_simple_rel_arrays(PlannerInfo *root)
115 : {
116 : int size;
117 : Index rti;
118 : ListCell *lc;
119 :
120 : /* Arrays are accessed using RT indexes (1..N) */
121 417423 : size = list_length(root->parse->rtable) + 1;
122 417423 : root->simple_rel_array_size = size;
123 :
124 : /*
125 : * simple_rel_array is initialized to all NULLs, since no RelOptInfos
126 : * exist yet. It'll be filled by later calls to build_simple_rel().
127 : */
128 417423 : root->simple_rel_array = (RelOptInfo **)
129 417423 : palloc0_array(RelOptInfo *, size);
130 :
131 : /* simple_rte_array is an array equivalent of the rtable list */
132 417423 : root->simple_rte_array = (RangeTblEntry **)
133 417423 : palloc0_array(RangeTblEntry *, size);
134 417423 : rti = 1;
135 1139738 : foreach(lc, root->parse->rtable)
136 : {
137 722315 : RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
138 :
139 722315 : root->simple_rte_array[rti++] = rte;
140 : }
141 :
142 : /* append_rel_array is not needed if there are no AppendRelInfos */
143 417423 : if (root->append_rel_list == NIL)
144 : {
145 413014 : root->append_rel_array = NULL;
146 413014 : return;
147 : }
148 :
149 4409 : root->append_rel_array = (AppendRelInfo **)
150 4409 : palloc0_array(AppendRelInfo *, size);
151 :
152 : /*
153 : * append_rel_array is filled with any already-existing AppendRelInfos,
154 : * which currently could only come from UNION ALL flattening. We might
155 : * add more later during inheritance expansion, but it's the
156 : * responsibility of the expansion code to update the array properly.
157 : */
158 17171 : foreach(lc, root->append_rel_list)
159 : {
160 12762 : AppendRelInfo *appinfo = lfirst_node(AppendRelInfo, lc);
161 12762 : int child_relid = appinfo->child_relid;
162 :
163 : /* Sanity check */
164 : Assert(child_relid < size);
165 :
166 12762 : if (root->append_rel_array[child_relid])
167 0 : elog(ERROR, "child relation already exists");
168 :
169 12762 : root->append_rel_array[child_relid] = appinfo;
170 : }
171 : }
172 :
173 : /*
174 : * expand_planner_arrays
175 : * Expand the PlannerInfo's per-RTE arrays by add_size members
176 : * and initialize the newly added entries to NULLs
177 : *
178 : * Note: this causes the append_rel_array to become allocated even if
179 : * it was not before. This is okay for current uses, because we only call
180 : * this when adding child relations, which always have AppendRelInfos.
181 : */
182 : void
183 15979 : expand_planner_arrays(PlannerInfo *root, int add_size)
184 : {
185 : int new_size;
186 :
187 : Assert(add_size > 0);
188 :
189 15979 : new_size = root->simple_rel_array_size + add_size;
190 :
191 15979 : root->simple_rel_array =
192 15979 : repalloc0_array(root->simple_rel_array, RelOptInfo *, root->simple_rel_array_size, new_size);
193 :
194 15979 : root->simple_rte_array =
195 15979 : repalloc0_array(root->simple_rte_array, RangeTblEntry *, root->simple_rel_array_size, new_size);
196 :
197 15979 : if (root->append_rel_array)
198 5033 : root->append_rel_array =
199 5033 : repalloc0_array(root->append_rel_array, AppendRelInfo *, root->simple_rel_array_size, new_size);
200 : else
201 10946 : root->append_rel_array =
202 10946 : palloc0_array(AppendRelInfo *, new_size);
203 :
204 15979 : root->simple_rel_array_size = new_size;
205 15979 : }
206 :
207 : /*
208 : * build_simple_rel
209 : * Construct a new RelOptInfo for a base relation or 'other' relation.
210 : */
211 : RelOptInfo *
212 594342 : build_simple_rel(PlannerInfo *root, int relid, RelOptInfo *parent)
213 : {
214 : RelOptInfo *rel;
215 : RangeTblEntry *rte;
216 :
217 : /* Rel should not exist already */
218 : Assert(relid > 0 && relid < root->simple_rel_array_size);
219 594342 : if (root->simple_rel_array[relid] != NULL)
220 0 : elog(ERROR, "rel %d already exists", relid);
221 :
222 : /* Fetch RTE for relation */
223 594342 : rte = root->simple_rte_array[relid];
224 : Assert(rte != NULL);
225 :
226 594342 : rel = makeNode(RelOptInfo);
227 594342 : rel->reloptkind = parent ? RELOPT_OTHER_MEMBER_REL : RELOPT_BASEREL;
228 594342 : rel->relids = bms_make_singleton(relid);
229 594342 : rel->rows = 0;
230 : /* cheap startup cost is interesting iff not all tuples to be retrieved */
231 594342 : rel->consider_startup = (root->tuple_fraction > 0);
232 594342 : rel->consider_param_startup = false; /* might get changed later */
233 594342 : rel->consider_parallel = false; /* might get changed later */
234 594342 : rel->pgs_mask = root->glob->default_pgs_mask;
235 594342 : rel->reltarget = create_empty_pathtarget();
236 594342 : rel->pathlist = NIL;
237 594342 : rel->ppilist = NIL;
238 594342 : rel->partial_pathlist = NIL;
239 594342 : rel->cheapest_startup_path = NULL;
240 594342 : rel->cheapest_total_path = NULL;
241 594342 : rel->cheapest_parameterized_paths = NIL;
242 594342 : rel->relid = relid;
243 594342 : rel->rtekind = rte->rtekind;
244 : /* min_attr, max_attr, attr_needed, attr_widths are set below */
245 594342 : rel->notnullattnums = NULL;
246 594342 : rel->lateral_vars = NIL;
247 594342 : rel->indexlist = NIL;
248 594342 : rel->statlist = NIL;
249 594342 : rel->pages = 0;
250 594342 : rel->tuples = 0;
251 594342 : rel->allvisfrac = 0;
252 594342 : rel->eclass_indexes = NULL;
253 594342 : rel->subroot = NULL;
254 594342 : rel->subplan_params = NIL;
255 594342 : rel->rel_parallel_workers = -1; /* set up in get_relation_info */
256 594342 : rel->amflags = 0;
257 594342 : rel->serverid = InvalidOid;
258 594342 : if (rte->rtekind == RTE_RELATION)
259 : {
260 : Assert(parent == NULL ||
261 : parent->rtekind == RTE_RELATION ||
262 : parent->rtekind == RTE_SUBQUERY);
263 :
264 : /*
265 : * For any RELATION rte, we need a userid with which to check
266 : * permission access. Baserels simply use their own
267 : * RTEPermissionInfo's checkAsUser.
268 : *
269 : * For otherrels normally there's no RTEPermissionInfo, so we use the
270 : * parent's, which normally has one. The exceptional case is that the
271 : * parent is a subquery, in which case the otherrel will have its own.
272 : */
273 371122 : if (rel->reloptkind == RELOPT_BASEREL ||
274 35909 : (rel->reloptkind == RELOPT_OTHER_MEMBER_REL &&
275 35909 : parent->rtekind == RTE_SUBQUERY))
276 336197 : {
277 : RTEPermissionInfo *perminfo;
278 :
279 336197 : perminfo = getRTEPermissionInfo(root->parse->rteperminfos, rte);
280 336197 : rel->userid = perminfo->checkAsUser;
281 : }
282 : else
283 34925 : rel->userid = parent->userid;
284 : }
285 : else
286 223220 : rel->userid = InvalidOid;
287 594342 : rel->useridiscurrent = false;
288 594342 : rel->fdwroutine = NULL;
289 594342 : rel->fdw_private = NULL;
290 594342 : rel->unique_for_rels = NIL;
291 594342 : rel->non_unique_for_rels = NIL;
292 594342 : rel->unique_rel = NULL;
293 594342 : rel->unique_pathkeys = NIL;
294 594342 : rel->unique_groupclause = NIL;
295 594342 : rel->baserestrictinfo = NIL;
296 594342 : rel->baserestrictcost.startup = 0;
297 594342 : rel->baserestrictcost.per_tuple = 0;
298 594342 : rel->baserestrict_min_security = UINT_MAX;
299 594342 : rel->joininfo = NIL;
300 594342 : rel->has_eclass_joins = false;
301 594342 : rel->consider_partitionwise_join = false; /* might get changed later */
302 594342 : rel->agg_info = NULL;
303 594342 : rel->grouped_rel = NULL;
304 594342 : rel->part_scheme = NULL;
305 594342 : rel->nparts = -1;
306 594342 : rel->boundinfo = NULL;
307 594342 : rel->partbounds_merged = false;
308 594342 : rel->partition_qual = NIL;
309 594342 : rel->part_rels = NULL;
310 594342 : rel->live_parts = NULL;
311 594342 : rel->all_partrels = NULL;
312 594342 : rel->partexprs = NULL;
313 594342 : rel->nullable_partexprs = NULL;
314 :
315 : /*
316 : * Pass assorted information down the inheritance hierarchy.
317 : */
318 594342 : if (parent)
319 : {
320 : /* We keep back-links to immediate parent and topmost parent. */
321 47687 : rel->parent = parent;
322 47687 : rel->top_parent = parent->top_parent ? parent->top_parent : parent;
323 47687 : rel->top_parent_relids = rel->top_parent->relids;
324 :
325 : /*
326 : * A child rel is below the same outer joins as its parent. (We
327 : * presume this info was already calculated for the parent.)
328 : */
329 47687 : rel->nulling_relids = parent->nulling_relids;
330 :
331 : /*
332 : * Also propagate lateral-reference information from appendrel parent
333 : * rels to their child rels. We intentionally give each child rel the
334 : * same minimum parameterization, even though it's quite possible that
335 : * some don't reference all the lateral rels. This is because any
336 : * append path for the parent will have to have the same
337 : * parameterization for every child anyway, and there's no value in
338 : * forcing extra reparameterize_path() calls. Similarly, a lateral
339 : * reference to the parent prevents use of otherwise-movable join rels
340 : * for each child.
341 : *
342 : * It's possible for child rels to have their own children, in which
343 : * case the topmost parent's lateral info propagates all the way down.
344 : */
345 47687 : rel->direct_lateral_relids = parent->direct_lateral_relids;
346 47687 : rel->lateral_relids = parent->lateral_relids;
347 47687 : rel->lateral_referencers = parent->lateral_referencers;
348 : }
349 : else
350 : {
351 546655 : rel->parent = NULL;
352 546655 : rel->top_parent = NULL;
353 546655 : rel->top_parent_relids = NULL;
354 546655 : rel->nulling_relids = NULL;
355 546655 : rel->direct_lateral_relids = NULL;
356 546655 : rel->lateral_relids = NULL;
357 546655 : rel->lateral_referencers = NULL;
358 : }
359 :
360 : /* Check type of rtable entry */
361 594342 : switch (rte->rtekind)
362 : {
363 371122 : case RTE_RELATION:
364 : /* Table --- retrieve statistics from the system catalogs */
365 371122 : get_relation_info(root, rte->relid, rte->inh, rel);
366 371111 : break;
367 81816 : case RTE_SUBQUERY:
368 : case RTE_FUNCTION:
369 : case RTE_TABLEFUNC:
370 : case RTE_VALUES:
371 : case RTE_CTE:
372 : case RTE_NAMEDTUPLESTORE:
373 :
374 : /*
375 : * Subquery, function, tablefunc, values list, CTE, or ENR --- set
376 : * up attr range and arrays
377 : *
378 : * Note: 0 is included in range to support whole-row Vars
379 : */
380 81816 : rel->min_attr = 0;
381 81816 : rel->max_attr = list_length(rte->eref->colnames);
382 81816 : rel->attr_needed = (Relids *)
383 81816 : palloc0_array(Relids, rel->max_attr - rel->min_attr + 1);
384 81816 : rel->attr_widths = (int32 *)
385 81816 : palloc0_array(int32, rel->max_attr - rel->min_attr + 1);
386 81816 : break;
387 141404 : case RTE_RESULT:
388 : /* RTE_RESULT has no columns, nor could it have whole-row Var */
389 141404 : rel->min_attr = 0;
390 141404 : rel->max_attr = -1;
391 141404 : rel->attr_needed = NULL;
392 141404 : rel->attr_widths = NULL;
393 141404 : break;
394 0 : default:
395 0 : elog(ERROR, "unrecognized RTE kind: %d",
396 : (int) rte->rtekind);
397 : break;
398 : }
399 :
400 : /*
401 : * Allow a plugin to editorialize on the new RelOptInfo. This could
402 : * involve editorializing on the information which get_relation_info
403 : * obtained from the catalogs, such as altering the assumed relation size,
404 : * removing an index, or adding a hypothetical index to the indexlist.
405 : *
406 : * An extension can also modify rel->pgs_mask here to control path
407 : * generation.
408 : */
409 594331 : if (build_simple_rel_hook)
410 156550 : (*build_simple_rel_hook) (root, rel, rte);
411 :
412 : /*
413 : * Apply the parent's quals to the child, with appropriate substitution of
414 : * variables. If any resulting clause is reduced to constant FALSE or
415 : * NULL, apply_child_basequals returns false to indicate that scanning
416 : * this relation won't yield any rows. In this case, we mark the child as
417 : * dummy right away. (We must do this immediately so that pruning works
418 : * correctly when recursing in expand_partitioned_rtentry.)
419 : */
420 594331 : if (parent)
421 : {
422 47687 : AppendRelInfo *appinfo = root->append_rel_array[relid];
423 :
424 : Assert(appinfo != NULL);
425 47687 : if (!apply_child_basequals(root, parent, rel, rte, appinfo))
426 : {
427 : /*
428 : * A restriction clause reduced to constant FALSE or NULL after
429 : * substitution. Mark the child as dummy so that it need not be
430 : * scanned.
431 : */
432 83 : mark_dummy_rel(rel);
433 : }
434 : }
435 :
436 : /* Save the finished struct in the query's simple_rel_array */
437 594331 : root->simple_rel_array[relid] = rel;
438 :
439 594331 : return rel;
440 : }
441 :
442 : /*
443 : * build_simple_grouped_rel
444 : * Construct a new RelOptInfo representing a grouped version of the input
445 : * simple relation.
446 : */
447 : RelOptInfo *
448 2530 : build_simple_grouped_rel(PlannerInfo *root, RelOptInfo *rel)
449 : {
450 : RelOptInfo *grouped_rel;
451 : RelAggInfo *agg_info;
452 :
453 : /*
454 : * We should have available aggregate expressions and grouping
455 : * expressions, otherwise we cannot reach here.
456 : */
457 : Assert(root->agg_clause_list != NIL);
458 : Assert(root->group_expr_list != NIL);
459 :
460 : /* nothing to do for dummy rel */
461 2530 : if (IS_DUMMY_REL(rel))
462 0 : return NULL;
463 :
464 : /*
465 : * Prepare the information needed to create grouped paths for this simple
466 : * relation.
467 : */
468 2530 : agg_info = create_rel_agg_info(root, rel, true);
469 2530 : if (agg_info == NULL)
470 1826 : return NULL;
471 :
472 : /*
473 : * If grouped paths for the given simple relation are not considered
474 : * useful, skip building the grouped relation.
475 : */
476 704 : if (!agg_info->agg_useful)
477 217 : return NULL;
478 :
479 : /* Track the set of relids at which partial aggregation is applied */
480 487 : agg_info->apply_agg_at = bms_copy(rel->relids);
481 :
482 : /* build the grouped relation */
483 487 : grouped_rel = build_grouped_rel(root, rel);
484 487 : grouped_rel->reltarget = agg_info->target;
485 487 : grouped_rel->rows = agg_info->grouped_rows;
486 487 : grouped_rel->agg_info = agg_info;
487 :
488 487 : rel->grouped_rel = grouped_rel;
489 :
490 487 : return grouped_rel;
491 : }
492 :
493 : /*
494 : * build_grouped_rel
495 : * Build a grouped relation by flat copying the input relation and resetting
496 : * the necessary fields.
497 : */
498 : RelOptInfo *
499 14544 : build_grouped_rel(PlannerInfo *root, RelOptInfo *rel)
500 : {
501 : RelOptInfo *grouped_rel;
502 :
503 14544 : grouped_rel = makeNode(RelOptInfo);
504 14544 : memcpy(grouped_rel, rel, sizeof(RelOptInfo));
505 :
506 : /*
507 : * clear path info
508 : */
509 14544 : grouped_rel->pathlist = NIL;
510 14544 : grouped_rel->ppilist = NIL;
511 14544 : grouped_rel->partial_pathlist = NIL;
512 14544 : grouped_rel->cheapest_startup_path = NULL;
513 14544 : grouped_rel->cheapest_total_path = NULL;
514 14544 : grouped_rel->cheapest_parameterized_paths = NIL;
515 :
516 : /*
517 : * clear partition info
518 : */
519 14544 : grouped_rel->part_scheme = NULL;
520 14544 : grouped_rel->nparts = -1;
521 14544 : grouped_rel->boundinfo = NULL;
522 14544 : grouped_rel->partbounds_merged = false;
523 14544 : grouped_rel->partition_qual = NIL;
524 14544 : grouped_rel->part_rels = NULL;
525 14544 : grouped_rel->live_parts = NULL;
526 14544 : grouped_rel->all_partrels = NULL;
527 14544 : grouped_rel->partexprs = NULL;
528 14544 : grouped_rel->nullable_partexprs = NULL;
529 14544 : grouped_rel->consider_partitionwise_join = false;
530 :
531 : /*
532 : * clear size estimates
533 : */
534 14544 : grouped_rel->rows = 0;
535 :
536 14544 : return grouped_rel;
537 : }
538 :
539 : /*
540 : * find_base_rel
541 : * Find a base or otherrel relation entry, which must already exist.
542 : */
543 : RelOptInfo *
544 5626592 : find_base_rel(PlannerInfo *root, int relid)
545 : {
546 : RelOptInfo *rel;
547 :
548 : /* use an unsigned comparison to prevent negative array element access */
549 5626592 : if ((uint32) relid < (uint32) root->simple_rel_array_size)
550 : {
551 5626592 : rel = root->simple_rel_array[relid];
552 5626592 : if (rel)
553 5626592 : return rel;
554 : }
555 :
556 0 : elog(ERROR, "no relation entry for relid %d", relid);
557 :
558 : return NULL; /* keep compiler quiet */
559 : }
560 :
561 : /*
562 : * find_base_rel_noerr
563 : * Find a base or otherrel relation entry, returning NULL if there's none
564 : */
565 : RelOptInfo *
566 1160211 : find_base_rel_noerr(PlannerInfo *root, int relid)
567 : {
568 : /* use an unsigned comparison to prevent negative array element access */
569 1160211 : if ((uint32) relid < (uint32) root->simple_rel_array_size)
570 1160211 : return root->simple_rel_array[relid];
571 0 : return NULL;
572 : }
573 :
574 : /*
575 : * find_base_rel_ignore_join
576 : * Find a base or otherrel relation entry, which must already exist.
577 : *
578 : * Unlike find_base_rel, if relid references an outer join then this
579 : * will return NULL rather than raising an error. This is convenient
580 : * for callers that must deal with relid sets including both base and
581 : * outer joins.
582 : */
583 : RelOptInfo *
584 155698 : find_base_rel_ignore_join(PlannerInfo *root, int relid)
585 : {
586 : /* use an unsigned comparison to prevent negative array element access */
587 155698 : if ((uint32) relid < (uint32) root->simple_rel_array_size)
588 : {
589 : RelOptInfo *rel;
590 : RangeTblEntry *rte;
591 :
592 155698 : rel = root->simple_rel_array[relid];
593 155698 : if (rel)
594 146129 : return rel;
595 :
596 : /*
597 : * We could just return NULL here, but for debugging purposes it seems
598 : * best to actually verify that the relid is an outer join and not
599 : * something weird.
600 : */
601 9569 : rte = root->simple_rte_array[relid];
602 9569 : if (rte && rte->rtekind == RTE_JOIN && rte->jointype != JOIN_INNER)
603 9569 : return NULL;
604 : }
605 :
606 0 : elog(ERROR, "no relation entry for relid %d", relid);
607 :
608 : return NULL; /* keep compiler quiet */
609 : }
610 :
611 : /*
612 : * build_join_rel_hash
613 : * Construct the auxiliary hash table for join relations.
614 : */
615 : static void
616 44 : build_join_rel_hash(PlannerInfo *root)
617 : {
618 : HTAB *hashtab;
619 : HASHCTL hash_ctl;
620 : ListCell *l;
621 :
622 : /* Create the hash table */
623 44 : hash_ctl.keysize = sizeof(Relids);
624 44 : hash_ctl.entrysize = sizeof(JoinHashEntry);
625 44 : hash_ctl.hash = bitmap_hash;
626 44 : hash_ctl.match = bitmap_match;
627 44 : hash_ctl.hcxt = CurrentMemoryContext;
628 44 : hashtab = hash_create("JoinRelHashTable",
629 : 256L,
630 : &hash_ctl,
631 : HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);
632 :
633 : /* Insert all the already-existing joinrels */
634 1496 : foreach(l, root->join_rel_list)
635 : {
636 1452 : RelOptInfo *rel = (RelOptInfo *) lfirst(l);
637 : JoinHashEntry *hentry;
638 : bool found;
639 :
640 1452 : hentry = (JoinHashEntry *) hash_search(hashtab,
641 1452 : &(rel->relids),
642 : HASH_ENTER,
643 : &found);
644 : Assert(!found);
645 1452 : hentry->join_rel = rel;
646 : }
647 :
648 44 : root->join_rel_hash = hashtab;
649 44 : }
650 :
651 : /*
652 : * find_join_rel
653 : * Returns relation entry corresponding to 'relids' (a set of RT indexes),
654 : * or NULL if none exists. This is for join relations.
655 : */
656 : RelOptInfo *
657 283914 : find_join_rel(PlannerInfo *root, Relids relids)
658 : {
659 : /*
660 : * Switch to using hash lookup when list grows "too long". The threshold
661 : * is arbitrary and is known only here.
662 : */
663 283914 : if (!root->join_rel_hash && list_length(root->join_rel_list) > 32)
664 44 : build_join_rel_hash(root);
665 :
666 : /*
667 : * Use either hashtable lookup or linear search, as appropriate.
668 : *
669 : * Note: the seemingly redundant hashkey variable is used to avoid taking
670 : * the address of relids; unless the compiler is exceedingly smart, doing
671 : * so would force relids out of a register and thus probably slow down the
672 : * list-search case.
673 : */
674 283914 : if (root->join_rel_hash)
675 : {
676 3264 : Relids hashkey = relids;
677 : JoinHashEntry *hentry;
678 :
679 3264 : hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
680 : &hashkey,
681 : HASH_FIND,
682 : NULL);
683 3264 : if (hentry)
684 2873 : return hentry->join_rel;
685 : }
686 : else
687 : {
688 : ListCell *l;
689 :
690 1785831 : foreach(l, root->join_rel_list)
691 : {
692 1605629 : RelOptInfo *rel = (RelOptInfo *) lfirst(l);
693 :
694 1605629 : if (bms_equal(rel->relids, relids))
695 100448 : return rel;
696 : }
697 : }
698 :
699 180593 : return NULL;
700 : }
701 :
702 : /*
703 : * set_foreign_rel_properties
704 : * Set up foreign-join fields if outer and inner relation are foreign
705 : * tables (or joins) belonging to the same server and assigned to the same
706 : * user to check access permissions as.
707 : *
708 : * In addition to an exact match of userid, we allow the case where one side
709 : * has zero userid (implying current user) and the other side has explicit
710 : * userid that happens to equal the current user; but in that case, pushdown of
711 : * the join is only valid for the current user. The useridiscurrent field
712 : * records whether we had to make such an assumption for this join or any
713 : * sub-join.
714 : *
715 : * Otherwise these fields are left invalid, so GetForeignJoinPaths will not be
716 : * called for the join relation.
717 : */
718 : static void
719 195236 : set_foreign_rel_properties(RelOptInfo *joinrel, RelOptInfo *outer_rel,
720 : RelOptInfo *inner_rel)
721 : {
722 195236 : if (OidIsValid(outer_rel->serverid) &&
723 449 : inner_rel->serverid == outer_rel->serverid)
724 : {
725 403 : if (inner_rel->userid == outer_rel->userid)
726 : {
727 397 : joinrel->serverid = outer_rel->serverid;
728 397 : joinrel->userid = outer_rel->userid;
729 397 : joinrel->useridiscurrent = outer_rel->useridiscurrent || inner_rel->useridiscurrent;
730 397 : joinrel->fdwroutine = outer_rel->fdwroutine;
731 : }
732 10 : else if (!OidIsValid(inner_rel->userid) &&
733 4 : outer_rel->userid == GetUserId())
734 : {
735 2 : joinrel->serverid = outer_rel->serverid;
736 2 : joinrel->userid = outer_rel->userid;
737 2 : joinrel->useridiscurrent = true;
738 2 : joinrel->fdwroutine = outer_rel->fdwroutine;
739 : }
740 4 : else if (!OidIsValid(outer_rel->userid) &&
741 0 : inner_rel->userid == GetUserId())
742 : {
743 0 : joinrel->serverid = outer_rel->serverid;
744 0 : joinrel->userid = inner_rel->userid;
745 0 : joinrel->useridiscurrent = true;
746 0 : joinrel->fdwroutine = outer_rel->fdwroutine;
747 : }
748 : }
749 195236 : }
750 :
751 : /*
752 : * add_join_rel
753 : * Add given join relation to the list of join relations in the given
754 : * PlannerInfo. Also add it to the auxiliary hashtable if there is one.
755 : */
756 : static void
757 195236 : add_join_rel(PlannerInfo *root, RelOptInfo *joinrel)
758 : {
759 : /* GEQO requires us to append the new joinrel to the end of the list! */
760 195236 : root->join_rel_list = lappend(root->join_rel_list, joinrel);
761 :
762 : /* store it into the auxiliary hashtable if there is one. */
763 195236 : if (root->join_rel_hash)
764 : {
765 : JoinHashEntry *hentry;
766 : bool found;
767 :
768 391 : hentry = (JoinHashEntry *) hash_search(root->join_rel_hash,
769 391 : &(joinrel->relids),
770 : HASH_ENTER,
771 : &found);
772 : Assert(!found);
773 391 : hentry->join_rel = joinrel;
774 : }
775 195236 : }
776 :
777 : /*
778 : * build_join_rel
779 : * Returns relation entry corresponding to the union of two given rels,
780 : * creating a new relation entry if none already exists.
781 : *
782 : * 'joinrelids' is the Relids set that uniquely identifies the join
783 : * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be
784 : * joined
785 : * 'sjinfo': join context info
786 : * 'pushed_down_joins': any pushed-down outer joins that are now completed
787 : * 'restrictlist_ptr': result variable. If not NULL, *restrictlist_ptr
788 : * receives the list of RestrictInfo nodes that apply to this
789 : * particular pair of joinable relations.
790 : *
791 : * restrictlist_ptr makes the routine's API a little grotty, but it saves
792 : * duplicated calculation of the restrictlist...
793 : */
794 : RelOptInfo *
795 280908 : build_join_rel(PlannerInfo *root,
796 : Relids joinrelids,
797 : RelOptInfo *outer_rel,
798 : RelOptInfo *inner_rel,
799 : SpecialJoinInfo *sjinfo,
800 : List *pushed_down_joins,
801 : List **restrictlist_ptr)
802 : {
803 : RelOptInfo *joinrel;
804 : List *restrictlist;
805 :
806 : /* This function should be used only for join between parents. */
807 : Assert(!IS_OTHER_REL(outer_rel) && !IS_OTHER_REL(inner_rel));
808 :
809 : /*
810 : * See if we already have a joinrel for this set of base rels.
811 : */
812 280908 : joinrel = find_join_rel(root, joinrelids);
813 :
814 280908 : if (joinrel)
815 : {
816 : /*
817 : * Yes, so we only need to figure the restrictlist for this particular
818 : * pair of component relations.
819 : */
820 101027 : if (restrictlist_ptr)
821 101027 : *restrictlist_ptr = build_joinrel_restrictlist(root,
822 : joinrel,
823 : outer_rel,
824 : inner_rel,
825 : sjinfo);
826 101027 : return joinrel;
827 : }
828 :
829 : /*
830 : * Nope, so make one.
831 : */
832 179881 : joinrel = makeNode(RelOptInfo);
833 179881 : joinrel->reloptkind = RELOPT_JOINREL;
834 179881 : joinrel->relids = bms_copy(joinrelids);
835 179881 : joinrel->rows = 0;
836 : /* cheap startup cost is interesting iff not all tuples to be retrieved */
837 179881 : joinrel->consider_startup = (root->tuple_fraction > 0);
838 179881 : joinrel->consider_param_startup = false;
839 179881 : joinrel->consider_parallel = false;
840 179881 : joinrel->pgs_mask = root->glob->default_pgs_mask;
841 179881 : joinrel->reltarget = create_empty_pathtarget();
842 179881 : joinrel->pathlist = NIL;
843 179881 : joinrel->ppilist = NIL;
844 179881 : joinrel->partial_pathlist = NIL;
845 179881 : joinrel->cheapest_startup_path = NULL;
846 179881 : joinrel->cheapest_total_path = NULL;
847 179881 : joinrel->cheapest_parameterized_paths = NIL;
848 : /* init direct_lateral_relids from children; we'll finish it up below */
849 179881 : joinrel->direct_lateral_relids =
850 179881 : bms_union(outer_rel->direct_lateral_relids,
851 179881 : inner_rel->direct_lateral_relids);
852 179881 : joinrel->lateral_relids = min_join_parameterization(root, joinrel->relids,
853 : outer_rel, inner_rel);
854 179881 : joinrel->relid = 0; /* indicates not a baserel */
855 179881 : joinrel->rtekind = RTE_JOIN;
856 179881 : joinrel->min_attr = 0;
857 179881 : joinrel->max_attr = 0;
858 179881 : joinrel->attr_needed = NULL;
859 179881 : joinrel->attr_widths = NULL;
860 179881 : joinrel->notnullattnums = NULL;
861 179881 : joinrel->nulling_relids = NULL;
862 179881 : joinrel->lateral_vars = NIL;
863 179881 : joinrel->lateral_referencers = NULL;
864 179881 : joinrel->indexlist = NIL;
865 179881 : joinrel->statlist = NIL;
866 179881 : joinrel->pages = 0;
867 179881 : joinrel->tuples = 0;
868 179881 : joinrel->allvisfrac = 0;
869 179881 : joinrel->eclass_indexes = NULL;
870 179881 : joinrel->subroot = NULL;
871 179881 : joinrel->subplan_params = NIL;
872 179881 : joinrel->rel_parallel_workers = -1;
873 179881 : joinrel->amflags = 0;
874 179881 : joinrel->serverid = InvalidOid;
875 179881 : joinrel->userid = InvalidOid;
876 179881 : joinrel->useridiscurrent = false;
877 179881 : joinrel->fdwroutine = NULL;
878 179881 : joinrel->fdw_private = NULL;
879 179881 : joinrel->unique_for_rels = NIL;
880 179881 : joinrel->non_unique_for_rels = NIL;
881 179881 : joinrel->unique_rel = NULL;
882 179881 : joinrel->unique_pathkeys = NIL;
883 179881 : joinrel->unique_groupclause = NIL;
884 179881 : joinrel->baserestrictinfo = NIL;
885 179881 : joinrel->baserestrictcost.startup = 0;
886 179881 : joinrel->baserestrictcost.per_tuple = 0;
887 179881 : joinrel->baserestrict_min_security = UINT_MAX;
888 179881 : joinrel->joininfo = NIL;
889 179881 : joinrel->has_eclass_joins = false;
890 179881 : joinrel->consider_partitionwise_join = false; /* might get changed later */
891 179881 : joinrel->agg_info = NULL;
892 179881 : joinrel->grouped_rel = NULL;
893 179881 : joinrel->parent = NULL;
894 179881 : joinrel->top_parent = NULL;
895 179881 : joinrel->top_parent_relids = NULL;
896 179881 : joinrel->part_scheme = NULL;
897 179881 : joinrel->nparts = -1;
898 179881 : joinrel->boundinfo = NULL;
899 179881 : joinrel->partbounds_merged = false;
900 179881 : joinrel->partition_qual = NIL;
901 179881 : joinrel->part_rels = NULL;
902 179881 : joinrel->live_parts = NULL;
903 179881 : joinrel->all_partrels = NULL;
904 179881 : joinrel->partexprs = NULL;
905 179881 : joinrel->nullable_partexprs = NULL;
906 :
907 : /* Compute information relevant to the foreign relations. */
908 179881 : set_foreign_rel_properties(joinrel, outer_rel, inner_rel);
909 :
910 : /*
911 : * Fill the joinrel's tlist with just the Vars and PHVs that need to be
912 : * output from this join (ie, are needed for higher joinclauses or final
913 : * output).
914 : *
915 : * NOTE: the tlist order for a join rel will depend on which pair of outer
916 : * and inner rels we first try to build it from. But the contents should
917 : * be the same regardless.
918 : */
919 179881 : build_joinrel_tlist(root, joinrel, outer_rel, sjinfo, pushed_down_joins,
920 179881 : (sjinfo->jointype == JOIN_FULL));
921 179881 : build_joinrel_tlist(root, joinrel, inner_rel, sjinfo, pushed_down_joins,
922 179881 : (sjinfo->jointype != JOIN_INNER));
923 179881 : add_placeholders_to_joinrel(root, joinrel, outer_rel, inner_rel, sjinfo);
924 :
925 : /*
926 : * add_placeholders_to_joinrel also took care of adding the ph_lateral
927 : * sets of any PlaceHolderVars computed here to direct_lateral_relids, so
928 : * now we can finish computing that. This is much like the computation of
929 : * the transitively-closed lateral_relids in min_join_parameterization,
930 : * except that here we *do* have to consider the added PHVs.
931 : */
932 179881 : joinrel->direct_lateral_relids =
933 179881 : bms_del_members(joinrel->direct_lateral_relids, joinrel->relids);
934 :
935 : /*
936 : * Construct restrict and join clause lists for the new joinrel. (The
937 : * caller might or might not need the restrictlist, but I need it anyway
938 : * for set_joinrel_size_estimates().)
939 : */
940 179881 : restrictlist = build_joinrel_restrictlist(root, joinrel,
941 : outer_rel, inner_rel,
942 : sjinfo);
943 179881 : if (restrictlist_ptr)
944 179881 : *restrictlist_ptr = restrictlist;
945 179881 : build_joinrel_joinlist(joinrel, outer_rel, inner_rel);
946 :
947 : /*
948 : * This is also the right place to check whether the joinrel has any
949 : * pending EquivalenceClass joins.
950 : */
951 179881 : joinrel->has_eclass_joins = has_relevant_eclass_joinclause(root, joinrel);
952 :
953 : /*
954 : * Set estimates of the joinrel's size.
955 : */
956 179881 : set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel,
957 : sjinfo, restrictlist);
958 :
959 : /*
960 : * Set the consider_parallel flag if this joinrel could potentially be
961 : * scanned within a parallel worker. If this flag is false for either
962 : * inner_rel or outer_rel, then it must be false for the joinrel also.
963 : * Even if both are true, there might be parallel-restricted expressions
964 : * in the targetlist or quals.
965 : *
966 : * Note that if there are more than two rels in this relation, they could
967 : * be divided between inner_rel and outer_rel in any arbitrary way. We
968 : * assume this doesn't matter, because we should hit all the same baserels
969 : * and joinclauses while building up to this joinrel no matter which we
970 : * take; therefore, we should make the same decision here however we get
971 : * here.
972 : */
973 332068 : if (inner_rel->consider_parallel && outer_rel->consider_parallel &&
974 303950 : is_parallel_safe(root, (Node *) restrictlist) &&
975 151763 : is_parallel_safe(root, (Node *) joinrel->reltarget->exprs))
976 151753 : joinrel->consider_parallel = true;
977 :
978 : /*
979 : * Allow a plugin to editorialize on the new joinrel's properties. Actions
980 : * might include altering the size estimate, clearing consider_parallel,
981 : * or adjusting pgs_mask.
982 : */
983 179881 : if (joinrel_setup_hook)
984 43726 : (*joinrel_setup_hook) (root, joinrel, outer_rel, inner_rel, sjinfo,
985 : restrictlist);
986 :
987 : /* Store the partition information. */
988 179881 : build_joinrel_partition_info(root, joinrel, outer_rel, inner_rel, sjinfo,
989 : restrictlist);
990 :
991 : /* Add the joinrel to the PlannerInfo. */
992 179881 : add_join_rel(root, joinrel);
993 :
994 : /*
995 : * Also, if dynamic-programming join search is active, add the new joinrel
996 : * to the appropriate sublist. Note: you might think the Assert on number
997 : * of members should be for equality, but some of the level 1 rels might
998 : * have been joinrels already, so we can only assert <=.
999 : */
1000 179881 : if (root->join_rel_level)
1001 : {
1002 : Assert(root->join_cur_level > 0);
1003 : Assert(root->join_cur_level <= bms_num_members(joinrel->relids));
1004 174271 : root->join_rel_level[root->join_cur_level] =
1005 174271 : lappend(root->join_rel_level[root->join_cur_level], joinrel);
1006 : }
1007 :
1008 179881 : return joinrel;
1009 : }
1010 :
1011 : /*
1012 : * build_child_join_rel
1013 : * Builds RelOptInfo representing join between given two child relations.
1014 : *
1015 : * 'outer_rel' and 'inner_rel' are the RelOptInfos of child relations being
1016 : * joined
1017 : * 'parent_joinrel' is the RelOptInfo representing the join between parent
1018 : * relations. Some of the members of new RelOptInfo are produced by
1019 : * translating corresponding members of this RelOptInfo
1020 : * 'restrictlist': list of RestrictInfo nodes that apply to this particular
1021 : * pair of joinable relations
1022 : * 'sjinfo': child join's join-type details
1023 : * 'nappinfos' and 'appinfos': AppendRelInfo array for child relids
1024 : */
1025 : RelOptInfo *
1026 15355 : build_child_join_rel(PlannerInfo *root, RelOptInfo *outer_rel,
1027 : RelOptInfo *inner_rel, RelOptInfo *parent_joinrel,
1028 : List *restrictlist, SpecialJoinInfo *sjinfo,
1029 : int nappinfos, AppendRelInfo **appinfos)
1030 : {
1031 15355 : RelOptInfo *joinrel = makeNode(RelOptInfo);
1032 :
1033 : /* Only joins between "other" relations land here. */
1034 : Assert(IS_OTHER_REL(outer_rel) && IS_OTHER_REL(inner_rel));
1035 :
1036 : /* The parent joinrel should have consider_partitionwise_join set. */
1037 : Assert(parent_joinrel->consider_partitionwise_join);
1038 :
1039 15355 : joinrel->reloptkind = RELOPT_OTHER_JOINREL;
1040 15355 : joinrel->relids = adjust_child_relids(parent_joinrel->relids,
1041 : nappinfos, appinfos);
1042 15355 : joinrel->rows = 0;
1043 : /* cheap startup cost is interesting iff not all tuples to be retrieved */
1044 15355 : joinrel->consider_startup = (root->tuple_fraction > 0);
1045 15355 : joinrel->consider_param_startup = false;
1046 15355 : joinrel->consider_parallel = false;
1047 15355 : joinrel->pgs_mask = root->glob->default_pgs_mask;
1048 15355 : joinrel->reltarget = create_empty_pathtarget();
1049 15355 : joinrel->pathlist = NIL;
1050 15355 : joinrel->ppilist = NIL;
1051 15355 : joinrel->partial_pathlist = NIL;
1052 15355 : joinrel->cheapest_startup_path = NULL;
1053 15355 : joinrel->cheapest_total_path = NULL;
1054 15355 : joinrel->cheapest_parameterized_paths = NIL;
1055 15355 : joinrel->direct_lateral_relids = NULL;
1056 15355 : joinrel->lateral_relids = NULL;
1057 15355 : joinrel->relid = 0; /* indicates not a baserel */
1058 15355 : joinrel->rtekind = RTE_JOIN;
1059 15355 : joinrel->min_attr = 0;
1060 15355 : joinrel->max_attr = 0;
1061 15355 : joinrel->attr_needed = NULL;
1062 15355 : joinrel->attr_widths = NULL;
1063 15355 : joinrel->notnullattnums = NULL;
1064 15355 : joinrel->nulling_relids = NULL;
1065 15355 : joinrel->lateral_vars = NIL;
1066 15355 : joinrel->lateral_referencers = NULL;
1067 15355 : joinrel->indexlist = NIL;
1068 15355 : joinrel->pages = 0;
1069 15355 : joinrel->tuples = 0;
1070 15355 : joinrel->allvisfrac = 0;
1071 15355 : joinrel->eclass_indexes = NULL;
1072 15355 : joinrel->subroot = NULL;
1073 15355 : joinrel->subplan_params = NIL;
1074 15355 : joinrel->amflags = 0;
1075 15355 : joinrel->serverid = InvalidOid;
1076 15355 : joinrel->userid = InvalidOid;
1077 15355 : joinrel->useridiscurrent = false;
1078 15355 : joinrel->fdwroutine = NULL;
1079 15355 : joinrel->fdw_private = NULL;
1080 15355 : joinrel->unique_rel = NULL;
1081 15355 : joinrel->unique_pathkeys = NIL;
1082 15355 : joinrel->unique_groupclause = NIL;
1083 15355 : joinrel->baserestrictinfo = NIL;
1084 15355 : joinrel->baserestrictcost.startup = 0;
1085 15355 : joinrel->baserestrictcost.per_tuple = 0;
1086 15355 : joinrel->joininfo = NIL;
1087 15355 : joinrel->has_eclass_joins = false;
1088 15355 : joinrel->consider_partitionwise_join = false; /* might get changed later */
1089 15355 : joinrel->agg_info = NULL;
1090 15355 : joinrel->grouped_rel = NULL;
1091 15355 : joinrel->parent = parent_joinrel;
1092 15355 : joinrel->top_parent = parent_joinrel->top_parent ? parent_joinrel->top_parent : parent_joinrel;
1093 15355 : joinrel->top_parent_relids = joinrel->top_parent->relids;
1094 15355 : joinrel->part_scheme = NULL;
1095 15355 : joinrel->nparts = -1;
1096 15355 : joinrel->boundinfo = NULL;
1097 15355 : joinrel->partbounds_merged = false;
1098 15355 : joinrel->partition_qual = NIL;
1099 15355 : joinrel->part_rels = NULL;
1100 15355 : joinrel->live_parts = NULL;
1101 15355 : joinrel->all_partrels = NULL;
1102 15355 : joinrel->partexprs = NULL;
1103 15355 : joinrel->nullable_partexprs = NULL;
1104 :
1105 : /* Compute information relevant to foreign relations. */
1106 15355 : set_foreign_rel_properties(joinrel, outer_rel, inner_rel);
1107 :
1108 : /* Set up reltarget struct */
1109 15355 : build_child_join_reltarget(root, parent_joinrel, joinrel,
1110 : nappinfos, appinfos);
1111 :
1112 : /* Construct joininfo list. */
1113 30710 : joinrel->joininfo = (List *) adjust_appendrel_attrs(root,
1114 15355 : (Node *) parent_joinrel->joininfo,
1115 : nappinfos,
1116 : appinfos);
1117 :
1118 : /*
1119 : * Lateral relids referred in child join will be same as that referred in
1120 : * the parent relation.
1121 : */
1122 15355 : joinrel->direct_lateral_relids = (Relids) bms_copy(parent_joinrel->direct_lateral_relids);
1123 15355 : joinrel->lateral_relids = (Relids) bms_copy(parent_joinrel->lateral_relids);
1124 :
1125 : /*
1126 : * If the parent joinrel has pending equivalence classes, so does the
1127 : * child.
1128 : */
1129 15355 : joinrel->has_eclass_joins = parent_joinrel->has_eclass_joins;
1130 :
1131 : /* Child joinrel is parallel safe if parent is parallel safe. */
1132 15355 : joinrel->consider_parallel = parent_joinrel->consider_parallel;
1133 :
1134 : /* Set estimates of the child-joinrel's size. */
1135 15355 : set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel,
1136 : sjinfo, restrictlist);
1137 :
1138 : /*
1139 : * Allow a plugin to editorialize on the new joinrel's properties. Actions
1140 : * might include altering the size estimate, clearing consider_parallel,
1141 : * or adjusting pgs_mask. (However, note that clearing consider_parallel
1142 : * would be better done in the parent joinrel rather than here.)
1143 : */
1144 15355 : if (joinrel_setup_hook)
1145 6170 : (*joinrel_setup_hook) (root, joinrel, outer_rel, inner_rel, sjinfo,
1146 : restrictlist);
1147 :
1148 : /* Is the join between partitions itself partitioned? */
1149 15355 : build_joinrel_partition_info(root, joinrel, outer_rel, inner_rel, sjinfo,
1150 : restrictlist);
1151 :
1152 : /* We build the join only once. */
1153 : Assert(!find_join_rel(root, joinrel->relids));
1154 :
1155 : /* Add the relation to the PlannerInfo. */
1156 15355 : add_join_rel(root, joinrel);
1157 :
1158 : /*
1159 : * We might need EquivalenceClass members corresponding to the child join,
1160 : * so that we can represent sort pathkeys for it. As with children of
1161 : * baserels, we shouldn't need this unless there are relevant eclass joins
1162 : * (implying that a merge join might be possible) or pathkeys to sort by.
1163 : */
1164 15355 : if (joinrel->has_eclass_joins || has_useful_pathkeys(root, parent_joinrel))
1165 14885 : add_child_join_rel_equivalences(root,
1166 : nappinfos, appinfos,
1167 : parent_joinrel, joinrel);
1168 :
1169 15355 : return joinrel;
1170 : }
1171 :
1172 : /*
1173 : * min_join_parameterization
1174 : *
1175 : * Determine the minimum possible parameterization of a joinrel, that is, the
1176 : * set of other rels it contains LATERAL references to. We save this value in
1177 : * the join's RelOptInfo. This function is split out of build_join_rel()
1178 : * because join_is_legal() needs the value to check a prospective join.
1179 : */
1180 : Relids
1181 206421 : min_join_parameterization(PlannerInfo *root,
1182 : Relids joinrelids,
1183 : RelOptInfo *outer_rel,
1184 : RelOptInfo *inner_rel)
1185 : {
1186 : Relids result;
1187 :
1188 : /*
1189 : * Basically we just need the union of the inputs' lateral_relids, less
1190 : * whatever is already in the join.
1191 : *
1192 : * It's not immediately obvious that this is a valid way to compute the
1193 : * result, because it might seem that we're ignoring possible lateral refs
1194 : * of PlaceHolderVars that are due to be computed at the join but not in
1195 : * either input. However, because create_lateral_join_info() already
1196 : * charged all such PHV refs to each member baserel of the join, they'll
1197 : * be accounted for already in the inputs' lateral_relids. Likewise, we
1198 : * do not need to worry about doing transitive closure here, because that
1199 : * was already accounted for in the original baserel lateral_relids.
1200 : */
1201 206421 : result = bms_union(outer_rel->lateral_relids, inner_rel->lateral_relids);
1202 206421 : result = bms_del_members(result, joinrelids);
1203 206421 : return result;
1204 : }
1205 :
1206 : /*
1207 : * build_joinrel_tlist
1208 : * Builds a join relation's target list from an input relation.
1209 : * (This is invoked twice to handle the two input relations.)
1210 : *
1211 : * The join's targetlist includes all Vars of its member relations that
1212 : * will still be needed above the join. This subroutine adds all such
1213 : * Vars from the specified input rel's tlist to the join rel's tlist.
1214 : * Likewise for any PlaceHolderVars emitted by the input rel.
1215 : *
1216 : * We also compute the expected width of the join's output, making use
1217 : * of data that was cached at the baserel level by set_rel_width().
1218 : *
1219 : * Pass can_null as true if the join is an outer join that can null Vars
1220 : * from this input relation. If so, we will (normally) add the join's relid
1221 : * to the nulling bitmaps of Vars and PHVs bubbled up from the input.
1222 : *
1223 : * When forming an outer join's target list, special handling is needed in
1224 : * case the outer join was commuted with another one per outer join identity 3
1225 : * (see optimizer/README). We must take steps to ensure that the output Vars
1226 : * have the same nulling bitmaps that they would if the two joins had been
1227 : * done in syntactic order; else they won't match Vars appearing higher in
1228 : * the query tree. An exception to the match-the-syntactic-order rule is
1229 : * that when an outer join is pushed down into another one's RHS per identity
1230 : * 3, we can't mark its Vars as nulled until the now-upper outer join is also
1231 : * completed. So we need to do three things:
1232 : *
1233 : * First, we add the outer join's relid to the nulling bitmap only if the
1234 : * outer join has been completely performed and the Var or PHV actually
1235 : * comes from within the syntactically nullable side(s) of the outer join.
1236 : * This takes care of the possibility that we have transformed
1237 : * (A leftjoin B on (Pab)) leftjoin C on (Pbc)
1238 : * to
1239 : * A leftjoin (B leftjoin C on (Pbc)) on (Pab)
1240 : * Here the pushed-down B/C join cannot mark C columns as nulled yet,
1241 : * while the now-upper A/B join must not mark C columns as nulled by itself.
1242 : *
1243 : * Second, perform the same operation for each SpecialJoinInfo listed in
1244 : * pushed_down_joins (which, in this example, would be the B/C join when
1245 : * we are at the now-upper A/B join). This allows the now-upper join to
1246 : * complete the marking of "C" Vars that now have fully valid values.
1247 : *
1248 : * Third, any relid in sjinfo->commute_above_r that is already part of
1249 : * the joinrel is added to the nulling bitmaps of nullable Vars and PHVs.
1250 : * This takes care of the reverse case where we implement
1251 : * A leftjoin (B leftjoin C on (Pbc)) on (Pab)
1252 : * as
1253 : * (A leftjoin B on (Pab)) leftjoin C on (Pbc)
1254 : * The C columns emitted by the B/C join need to be shown as nulled by both
1255 : * the B/C and A/B joins, even though they've not physically traversed the
1256 : * A/B join.
1257 : */
1258 : static void
1259 359762 : build_joinrel_tlist(PlannerInfo *root, RelOptInfo *joinrel,
1260 : RelOptInfo *input_rel,
1261 : SpecialJoinInfo *sjinfo,
1262 : List *pushed_down_joins,
1263 : bool can_null)
1264 : {
1265 359762 : Relids relids = joinrel->relids;
1266 359762 : int64 tuple_width = joinrel->reltarget->width;
1267 : ListCell *vars;
1268 : ListCell *lc;
1269 :
1270 1732534 : foreach(vars, input_rel->reltarget->exprs)
1271 : {
1272 1372772 : Var *var = (Var *) lfirst(vars);
1273 :
1274 : /*
1275 : * For a PlaceHolderVar, we have to look up the PlaceHolderInfo.
1276 : */
1277 1372772 : if (IsA(var, PlaceHolderVar))
1278 1738 : {
1279 1738 : PlaceHolderVar *phv = (PlaceHolderVar *) var;
1280 1738 : PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
1281 :
1282 : /* Is it still needed above this joinrel? */
1283 1738 : if (bms_nonempty_difference(phinfo->ph_needed, relids))
1284 : {
1285 : /*
1286 : * Yup, add it to the output. If this join potentially nulls
1287 : * this input, we have to update the PHV's phnullingrels,
1288 : * which means making a copy.
1289 : */
1290 1326 : if (can_null)
1291 : {
1292 855 : phv = copyObject(phv);
1293 : /* See comments above to understand this logic */
1294 1710 : if (sjinfo->ojrelid != 0 &&
1295 1690 : bms_is_member(sjinfo->ojrelid, relids) &&
1296 835 : (bms_is_subset(phv->phrels, sjinfo->syn_righthand) ||
1297 256 : (sjinfo->jointype == JOIN_FULL &&
1298 123 : bms_is_subset(phv->phrels, sjinfo->syn_lefthand))))
1299 825 : phv->phnullingrels = bms_add_member(phv->phnullingrels,
1300 825 : sjinfo->ojrelid);
1301 870 : foreach(lc, pushed_down_joins)
1302 : {
1303 15 : SpecialJoinInfo *othersj = (SpecialJoinInfo *) lfirst(lc);
1304 :
1305 : Assert(bms_is_member(othersj->ojrelid, relids));
1306 15 : if (bms_is_subset(phv->phrels, othersj->syn_righthand))
1307 10 : phv->phnullingrels = bms_add_member(phv->phnullingrels,
1308 10 : othersj->ojrelid);
1309 : }
1310 855 : phv->phnullingrels =
1311 855 : bms_join(phv->phnullingrels,
1312 855 : bms_intersect(sjinfo->commute_above_r,
1313 : relids));
1314 : }
1315 :
1316 1326 : joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs,
1317 : phv);
1318 : /* Bubbling up the precomputed result has cost zero */
1319 1326 : tuple_width += phinfo->ph_width;
1320 : }
1321 1738 : continue;
1322 : }
1323 :
1324 : /*
1325 : * Otherwise, anything in a baserel or joinrel targetlist ought to be
1326 : * a Var. (More general cases can only appear in appendrel child
1327 : * rels, which will never be seen here.)
1328 : */
1329 1371034 : if (!IsA(var, Var))
1330 0 : elog(ERROR, "unexpected node type in rel targetlist: %d",
1331 : (int) nodeTag(var));
1332 :
1333 1371034 : if (var->varno == ROWID_VAR)
1334 : {
1335 : /* UPDATE/DELETE/MERGE row identity vars are always needed */
1336 : RowIdentityVarInfo *ridinfo = (RowIdentityVarInfo *)
1337 992 : list_nth(root->row_identity_vars, var->varattno - 1);
1338 :
1339 : /* Update reltarget width estimate from RowIdentityVarInfo */
1340 992 : tuple_width += ridinfo->rowidwidth;
1341 : }
1342 : else
1343 : {
1344 : RelOptInfo *baserel;
1345 : int ndx;
1346 :
1347 : /* Get the Var's original base rel */
1348 1370042 : baserel = find_base_rel(root, var->varno);
1349 :
1350 : /* Is it still needed above this joinrel? */
1351 1370042 : ndx = var->varattno - baserel->min_attr;
1352 1370042 : if (!bms_nonempty_difference(baserel->attr_needed[ndx], relids))
1353 273035 : continue; /* nope, skip it */
1354 :
1355 : /* Update reltarget width estimate from baserel's attr_widths */
1356 1097007 : tuple_width += baserel->attr_widths[ndx];
1357 : }
1358 :
1359 : /*
1360 : * Add the Var to the output. If this join potentially nulls this
1361 : * input, we have to update the Var's varnullingrels, which means
1362 : * making a copy. But note that we don't ever add nullingrel bits to
1363 : * row identity Vars (cf. comments in setrefs.c).
1364 : */
1365 1097999 : if (can_null && var->varno != ROWID_VAR)
1366 : {
1367 100687 : var = copyObject(var);
1368 : /* See comments above to understand this logic */
1369 200875 : if (sjinfo->ojrelid != 0 &&
1370 197275 : bms_is_member(sjinfo->ojrelid, relids) &&
1371 97087 : (bms_is_member(var->varno, sjinfo->syn_righthand) ||
1372 3120 : (sjinfo->jointype == JOIN_FULL &&
1373 1450 : bms_is_member(var->varno, sjinfo->syn_lefthand))))
1374 96867 : var->varnullingrels = bms_add_member(var->varnullingrels,
1375 96867 : sjinfo->ojrelid);
1376 101252 : foreach(lc, pushed_down_joins)
1377 : {
1378 565 : SpecialJoinInfo *othersj = (SpecialJoinInfo *) lfirst(lc);
1379 :
1380 : Assert(bms_is_member(othersj->ojrelid, relids));
1381 565 : if (bms_is_member(var->varno, othersj->syn_righthand))
1382 220 : var->varnullingrels = bms_add_member(var->varnullingrels,
1383 220 : othersj->ojrelid);
1384 : }
1385 100687 : var->varnullingrels =
1386 100687 : bms_join(var->varnullingrels,
1387 100687 : bms_intersect(sjinfo->commute_above_r,
1388 : relids));
1389 : }
1390 :
1391 1097999 : joinrel->reltarget->exprs = lappend(joinrel->reltarget->exprs,
1392 : var);
1393 :
1394 : /* Vars have cost zero, so no need to adjust reltarget->cost */
1395 : }
1396 :
1397 359762 : joinrel->reltarget->width = clamp_width_est(tuple_width);
1398 359762 : }
1399 :
1400 : /*
1401 : * build_joinrel_restrictlist
1402 : * build_joinrel_joinlist
1403 : * These routines build lists of restriction and join clauses for a
1404 : * join relation from the joininfo lists of the relations it joins.
1405 : *
1406 : * These routines are separate because the restriction list must be
1407 : * built afresh for each pair of input sub-relations we consider, whereas
1408 : * the join list need only be computed once for any join RelOptInfo.
1409 : * The join list is fully determined by the set of rels making up the
1410 : * joinrel, so we should get the same results (up to ordering) from any
1411 : * candidate pair of sub-relations. But the restriction list is whatever
1412 : * is not handled in the sub-relations, so it depends on which
1413 : * sub-relations are considered.
1414 : *
1415 : * If a join clause from an input relation refers to base+OJ rels still not
1416 : * present in the joinrel, then it is still a join clause for the joinrel;
1417 : * we put it into the joininfo list for the joinrel. Otherwise,
1418 : * the clause is now a restrict clause for the joined relation, and we
1419 : * return it to the caller of build_joinrel_restrictlist() to be stored in
1420 : * join paths made from this pair of sub-relations. (It will not need to
1421 : * be considered further up the join tree.)
1422 : *
1423 : * In many cases we will find the same RestrictInfos in both input
1424 : * relations' joinlists, so be careful to eliminate duplicates.
1425 : * Pointer equality should be a sufficient test for dups, since all
1426 : * the various joinlist entries ultimately refer to RestrictInfos
1427 : * pushed into them by distribute_restrictinfo_to_rels().
1428 : *
1429 : * 'joinrel' is a join relation node
1430 : * 'outer_rel' and 'inner_rel' are a pair of relations that can be joined
1431 : * to form joinrel.
1432 : * 'sjinfo': join context info
1433 : *
1434 : * build_joinrel_restrictlist() returns a list of relevant restrictinfos,
1435 : * whereas build_joinrel_joinlist() stores its results in the joinrel's
1436 : * joininfo list. One or the other must accept each given clause!
1437 : *
1438 : * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass
1439 : * up to the join relation. I believe this is no longer necessary, because
1440 : * RestrictInfo nodes are no longer context-dependent. Instead, just include
1441 : * the original nodes in the lists made for the join relation.
1442 : */
1443 : static List *
1444 280908 : build_joinrel_restrictlist(PlannerInfo *root,
1445 : RelOptInfo *joinrel,
1446 : RelOptInfo *outer_rel,
1447 : RelOptInfo *inner_rel,
1448 : SpecialJoinInfo *sjinfo)
1449 : {
1450 : List *result;
1451 : Relids both_input_relids;
1452 :
1453 280908 : both_input_relids = bms_union(outer_rel->relids, inner_rel->relids);
1454 :
1455 : /*
1456 : * Collect all the clauses that syntactically belong at this level,
1457 : * eliminating any duplicates (important since we will see many of the
1458 : * same clauses arriving from both input relations).
1459 : */
1460 280908 : result = subbuild_joinrel_restrictlist(root, joinrel, outer_rel,
1461 : both_input_relids, NIL);
1462 280908 : result = subbuild_joinrel_restrictlist(root, joinrel, inner_rel,
1463 : both_input_relids, result);
1464 :
1465 : /*
1466 : * Add on any clauses derived from EquivalenceClasses. These cannot be
1467 : * redundant with the clauses in the joininfo lists, so don't bother
1468 : * checking.
1469 : */
1470 280908 : result = list_concat(result,
1471 280908 : generate_join_implied_equalities(root,
1472 : joinrel->relids,
1473 : outer_rel->relids,
1474 : inner_rel,
1475 : sjinfo));
1476 :
1477 280908 : return result;
1478 : }
1479 :
1480 : static void
1481 179881 : build_joinrel_joinlist(RelOptInfo *joinrel,
1482 : RelOptInfo *outer_rel,
1483 : RelOptInfo *inner_rel)
1484 : {
1485 : List *result;
1486 :
1487 : /*
1488 : * Collect all the clauses that syntactically belong above this level,
1489 : * eliminating any duplicates (important since we will see many of the
1490 : * same clauses arriving from both input relations).
1491 : */
1492 179881 : result = subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo, NIL);
1493 179881 : result = subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo, result);
1494 :
1495 179881 : joinrel->joininfo = result;
1496 179881 : }
1497 :
1498 : static List *
1499 561816 : subbuild_joinrel_restrictlist(PlannerInfo *root,
1500 : RelOptInfo *joinrel,
1501 : RelOptInfo *input_rel,
1502 : Relids both_input_relids,
1503 : List *new_restrictlist)
1504 : {
1505 : ListCell *l;
1506 :
1507 1005203 : foreach(l, input_rel->joininfo)
1508 : {
1509 443387 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
1510 :
1511 443387 : if (bms_is_subset(rinfo->required_relids, joinrel->relids))
1512 : {
1513 : /*
1514 : * This clause should become a restriction clause for the joinrel,
1515 : * since it refers to no outside rels. However, if it's a clone
1516 : * clause then it might be too late to evaluate it, so we have to
1517 : * check. (If it is too late, just ignore the clause, taking it
1518 : * on faith that another clone was or will be selected.) Clone
1519 : * clauses should always be outer-join clauses, so we compare
1520 : * against both_input_relids.
1521 : */
1522 265300 : if (rinfo->has_clone || rinfo->is_clone)
1523 : {
1524 : Assert(!RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids));
1525 37416 : if (!bms_is_subset(rinfo->required_relids, both_input_relids))
1526 6324 : continue;
1527 31092 : if (bms_overlap(rinfo->incompatible_relids, both_input_relids))
1528 12380 : continue;
1529 : }
1530 : else
1531 : {
1532 : /*
1533 : * For non-clone clauses, we just Assert it's OK. These might
1534 : * be either join or filter clauses; if it's a join clause
1535 : * then it should not refer to the current join's output.
1536 : * (There is little point in checking incompatible_relids,
1537 : * because it'll be NULL.)
1538 : */
1539 : Assert(RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids) ||
1540 : bms_is_subset(rinfo->required_relids,
1541 : both_input_relids));
1542 : }
1543 :
1544 : /*
1545 : * OK, so add it to the list, being careful to eliminate
1546 : * duplicates. (Since RestrictInfo nodes in different joinlists
1547 : * will have been multiply-linked rather than copied, pointer
1548 : * equality should be a sufficient test.)
1549 : */
1550 246596 : new_restrictlist = list_append_unique_ptr(new_restrictlist, rinfo);
1551 : }
1552 : else
1553 : {
1554 : /*
1555 : * This clause is still a join clause at this level, so we ignore
1556 : * it in this routine.
1557 : */
1558 : }
1559 : }
1560 :
1561 561816 : return new_restrictlist;
1562 : }
1563 :
1564 : static List *
1565 359762 : subbuild_joinrel_joinlist(RelOptInfo *joinrel,
1566 : List *joininfo_list,
1567 : List *new_joininfo)
1568 : {
1569 : ListCell *l;
1570 :
1571 : /* Expected to be called only for join between parent relations. */
1572 : Assert(joinrel->reloptkind == RELOPT_JOINREL);
1573 :
1574 640806 : foreach(l, joininfo_list)
1575 : {
1576 281044 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
1577 :
1578 281044 : if (bms_is_subset(rinfo->required_relids, joinrel->relids))
1579 : {
1580 : /*
1581 : * This clause becomes a restriction clause for the joinrel, since
1582 : * it refers to no outside rels. So we can ignore it in this
1583 : * routine.
1584 : */
1585 : }
1586 : else
1587 : {
1588 : /*
1589 : * This clause is still a join clause at this level, so add it to
1590 : * the new joininfo list, being careful to eliminate duplicates.
1591 : * (Since RestrictInfo nodes in different joinlists will have been
1592 : * multiply-linked rather than copied, pointer equality should be
1593 : * a sufficient test.)
1594 : */
1595 107740 : new_joininfo = list_append_unique_ptr(new_joininfo, rinfo);
1596 : }
1597 : }
1598 :
1599 359762 : return new_joininfo;
1600 : }
1601 :
1602 :
1603 : /*
1604 : * fetch_upper_rel
1605 : * Build a RelOptInfo describing some post-scan/join query processing,
1606 : * or return a pre-existing one if somebody already built it.
1607 : *
1608 : * An "upper" relation is identified by an UpperRelationKind and a Relids set.
1609 : * The meaning of the Relids set is not specified here, and very likely will
1610 : * vary for different relation kinds.
1611 : *
1612 : * Most of the fields in an upper-level RelOptInfo are not used and are not
1613 : * set here (though makeNode should ensure they're zeroes). We basically only
1614 : * care about fields that are of interest to add_path() and set_cheapest().
1615 : */
1616 : RelOptInfo *
1617 1352709 : fetch_upper_rel(PlannerInfo *root, UpperRelationKind kind, Relids relids)
1618 : {
1619 : RelOptInfo *upperrel;
1620 : ListCell *lc;
1621 :
1622 : /*
1623 : * For the moment, our indexing data structure is just a List for each
1624 : * relation kind. If we ever get so many of one kind that this stops
1625 : * working well, we can improve it. No code outside this function should
1626 : * assume anything about how to find a particular upperrel.
1627 : */
1628 :
1629 : /* If we already made this upperrel for the query, return it */
1630 1362060 : foreach(lc, root->upper_rels[kind])
1631 : {
1632 858947 : upperrel = (RelOptInfo *) lfirst(lc);
1633 :
1634 858947 : if (bms_equal(upperrel->relids, relids))
1635 849596 : return upperrel;
1636 : }
1637 :
1638 503113 : upperrel = makeNode(RelOptInfo);
1639 503113 : upperrel->reloptkind = RELOPT_UPPER_REL;
1640 503113 : upperrel->relids = bms_copy(relids);
1641 503113 : upperrel->pgs_mask = root->glob->default_pgs_mask;
1642 :
1643 : /* cheap startup cost is interesting iff not all tuples to be retrieved */
1644 503113 : upperrel->consider_startup = (root->tuple_fraction > 0);
1645 503113 : upperrel->consider_param_startup = false;
1646 503113 : upperrel->consider_parallel = false; /* might get changed later */
1647 503113 : upperrel->reltarget = create_empty_pathtarget();
1648 503113 : upperrel->pathlist = NIL;
1649 503113 : upperrel->cheapest_startup_path = NULL;
1650 503113 : upperrel->cheapest_total_path = NULL;
1651 503113 : upperrel->cheapest_parameterized_paths = NIL;
1652 :
1653 503113 : root->upper_rels[kind] = lappend(root->upper_rels[kind], upperrel);
1654 :
1655 503113 : return upperrel;
1656 : }
1657 :
1658 :
1659 : /*
1660 : * find_childrel_parents
1661 : * Compute the set of parent relids of an appendrel child rel.
1662 : *
1663 : * Since appendrels can be nested, a child could have multiple levels of
1664 : * appendrel ancestors. This function computes a Relids set of all the
1665 : * parent relation IDs.
1666 : */
1667 : Relids
1668 10180 : find_childrel_parents(PlannerInfo *root, RelOptInfo *rel)
1669 : {
1670 10180 : Relids result = NULL;
1671 :
1672 : Assert(rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
1673 : Assert(rel->relid > 0 && rel->relid < root->simple_rel_array_size);
1674 :
1675 : do
1676 : {
1677 12162 : AppendRelInfo *appinfo = root->append_rel_array[rel->relid];
1678 12162 : Index prelid = appinfo->parent_relid;
1679 :
1680 12162 : result = bms_add_member(result, prelid);
1681 :
1682 : /* traverse up to the parent rel, loop if it's also a child rel */
1683 12162 : rel = find_base_rel(root, prelid);
1684 12162 : } while (rel->reloptkind == RELOPT_OTHER_MEMBER_REL);
1685 :
1686 : Assert(rel->reloptkind == RELOPT_BASEREL);
1687 :
1688 10180 : return result;
1689 : }
1690 :
1691 :
1692 : /*
1693 : * get_baserel_parampathinfo
1694 : * Get the ParamPathInfo for a parameterized path for a base relation,
1695 : * constructing one if we don't have one already.
1696 : *
1697 : * This centralizes estimating the rowcounts for parameterized paths.
1698 : * We need to cache those to be sure we use the same rowcount for all paths
1699 : * of the same parameterization for a given rel. This is also a convenient
1700 : * place to determine which movable join clauses the parameterized path will
1701 : * be responsible for evaluating.
1702 : */
1703 : ParamPathInfo *
1704 1508320 : get_baserel_parampathinfo(PlannerInfo *root, RelOptInfo *baserel,
1705 : Relids required_outer)
1706 : {
1707 : ParamPathInfo *ppi;
1708 : Relids joinrelids;
1709 : List *pclauses;
1710 : List *eqclauses;
1711 : Bitmapset *pserials;
1712 : double rows;
1713 : ListCell *lc;
1714 :
1715 : /* If rel has LATERAL refs, every path for it should account for them */
1716 : Assert(bms_is_subset(baserel->lateral_relids, required_outer));
1717 :
1718 : /* Unparameterized paths have no ParamPathInfo */
1719 1508320 : if (bms_is_empty(required_outer))
1720 1220498 : return NULL;
1721 :
1722 : Assert(!bms_overlap(baserel->relids, required_outer));
1723 :
1724 : /* If we already have a PPI for this parameterization, just return it */
1725 287822 : if ((ppi = find_param_path_info(baserel, required_outer)))
1726 155166 : return ppi;
1727 :
1728 : /*
1729 : * Identify all joinclauses that are movable to this base rel given this
1730 : * parameterization.
1731 : */
1732 132656 : joinrelids = bms_union(baserel->relids, required_outer);
1733 132656 : pclauses = NIL;
1734 208213 : foreach(lc, baserel->joininfo)
1735 : {
1736 75557 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1737 :
1738 75557 : if (join_clause_is_movable_into(rinfo,
1739 : baserel->relids,
1740 : joinrelids))
1741 32788 : pclauses = lappend(pclauses, rinfo);
1742 : }
1743 :
1744 : /*
1745 : * Add in joinclauses generated by EquivalenceClasses, too. (These
1746 : * necessarily satisfy join_clause_is_movable_into; but in assert-enabled
1747 : * builds, let's verify that.)
1748 : */
1749 132656 : eqclauses = generate_join_implied_equalities(root,
1750 : joinrelids,
1751 : required_outer,
1752 : baserel,
1753 : NULL);
1754 : #ifdef USE_ASSERT_CHECKING
1755 : foreach(lc, eqclauses)
1756 : {
1757 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1758 :
1759 : Assert(join_clause_is_movable_into(rinfo,
1760 : baserel->relids,
1761 : joinrelids));
1762 : }
1763 : #endif
1764 132656 : pclauses = list_concat(pclauses, eqclauses);
1765 :
1766 : /* Compute set of serial numbers of the enforced clauses */
1767 132656 : pserials = NULL;
1768 275311 : foreach(lc, pclauses)
1769 : {
1770 142655 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1771 :
1772 142655 : pserials = bms_add_member(pserials, rinfo->rinfo_serial);
1773 : }
1774 :
1775 : /* Estimate the number of rows returned by the parameterized scan */
1776 132656 : rows = get_parameterized_baserel_size(root, baserel, pclauses);
1777 :
1778 : /* And now we can build the ParamPathInfo */
1779 132656 : ppi = makeNode(ParamPathInfo);
1780 132656 : ppi->ppi_req_outer = required_outer;
1781 132656 : ppi->ppi_rows = rows;
1782 132656 : ppi->ppi_clauses = pclauses;
1783 132656 : ppi->ppi_serials = pserials;
1784 132656 : baserel->ppilist = lappend(baserel->ppilist, ppi);
1785 :
1786 132656 : return ppi;
1787 : }
1788 :
1789 : /*
1790 : * get_joinrel_parampathinfo
1791 : * Get the ParamPathInfo for a parameterized path for a join relation,
1792 : * constructing one if we don't have one already.
1793 : *
1794 : * This centralizes estimating the rowcounts for parameterized paths.
1795 : * We need to cache those to be sure we use the same rowcount for all paths
1796 : * of the same parameterization for a given rel. This is also a convenient
1797 : * place to determine which movable join clauses the parameterized path will
1798 : * be responsible for evaluating.
1799 : *
1800 : * outer_path and inner_path are a pair of input paths that can be used to
1801 : * construct the join, and restrict_clauses is the list of regular join
1802 : * clauses (including clauses derived from EquivalenceClasses) that must be
1803 : * applied at the join node when using these inputs.
1804 : *
1805 : * Unlike the situation for base rels, the set of movable join clauses to be
1806 : * enforced at a join varies with the selected pair of input paths, so we
1807 : * must calculate that and pass it back, even if we already have a matching
1808 : * ParamPathInfo. We handle this by adding any clauses moved down to this
1809 : * join to *restrict_clauses, which is an in/out parameter. (The addition
1810 : * is done in such a way as to not modify the passed-in List structure.)
1811 : *
1812 : * Note: when considering a nestloop join, the caller must have removed from
1813 : * restrict_clauses any movable clauses that are themselves scheduled to be
1814 : * pushed into the right-hand path. We do not do that here since it's
1815 : * unnecessary for other join types.
1816 : */
1817 : ParamPathInfo *
1818 1842401 : get_joinrel_parampathinfo(PlannerInfo *root, RelOptInfo *joinrel,
1819 : Path *outer_path,
1820 : Path *inner_path,
1821 : SpecialJoinInfo *sjinfo,
1822 : Relids required_outer,
1823 : List **restrict_clauses)
1824 : {
1825 : ParamPathInfo *ppi;
1826 : Relids join_and_req;
1827 : Relids outer_and_req;
1828 : Relids inner_and_req;
1829 : List *pclauses;
1830 : List *eclauses;
1831 : List *dropped_ecs;
1832 : double rows;
1833 : ListCell *lc;
1834 :
1835 : /* If rel has LATERAL refs, every path for it should account for them */
1836 : Assert(bms_is_subset(joinrel->lateral_relids, required_outer));
1837 :
1838 : /* Unparameterized paths have no ParamPathInfo or extra join clauses */
1839 1842401 : if (bms_is_empty(required_outer))
1840 1812227 : return NULL;
1841 :
1842 : Assert(!bms_overlap(joinrel->relids, required_outer));
1843 :
1844 : /*
1845 : * Identify all joinclauses that are movable to this join rel given this
1846 : * parameterization. These are the clauses that are movable into this
1847 : * join, but not movable into either input path. Treat an unparameterized
1848 : * input path as not accepting parameterized clauses (because it won't,
1849 : * per the shortcut exit above), even though the joinclause movement rules
1850 : * might allow the same clauses to be moved into a parameterized path for
1851 : * that rel.
1852 : */
1853 30174 : join_and_req = bms_union(joinrel->relids, required_outer);
1854 30174 : if (outer_path->param_info)
1855 22964 : outer_and_req = bms_union(outer_path->parent->relids,
1856 22964 : PATH_REQ_OUTER(outer_path));
1857 : else
1858 7210 : outer_and_req = NULL; /* outer path does not accept parameters */
1859 30174 : if (inner_path->param_info)
1860 16992 : inner_and_req = bms_union(inner_path->parent->relids,
1861 16992 : PATH_REQ_OUTER(inner_path));
1862 : else
1863 13182 : inner_and_req = NULL; /* inner path does not accept parameters */
1864 :
1865 30174 : pclauses = NIL;
1866 59126 : foreach(lc, joinrel->joininfo)
1867 : {
1868 28952 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1869 :
1870 28952 : if (join_clause_is_movable_into(rinfo,
1871 : joinrel->relids,
1872 14400 : join_and_req) &&
1873 14400 : !join_clause_is_movable_into(rinfo,
1874 14400 : outer_path->parent->relids,
1875 548 : outer_and_req) &&
1876 548 : !join_clause_is_movable_into(rinfo,
1877 548 : inner_path->parent->relids,
1878 : inner_and_req))
1879 72 : pclauses = lappend(pclauses, rinfo);
1880 : }
1881 :
1882 : /* Consider joinclauses generated by EquivalenceClasses, too */
1883 30174 : eclauses = generate_join_implied_equalities(root,
1884 : join_and_req,
1885 : required_outer,
1886 : joinrel,
1887 : NULL);
1888 : /* We only want ones that aren't movable to lower levels */
1889 30174 : dropped_ecs = NIL;
1890 44810 : foreach(lc, eclauses)
1891 : {
1892 14636 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1893 :
1894 : Assert(join_clause_is_movable_into(rinfo,
1895 : joinrel->relids,
1896 : join_and_req));
1897 14636 : if (join_clause_is_movable_into(rinfo,
1898 14636 : outer_path->parent->relids,
1899 : outer_and_req))
1900 6529 : continue; /* drop if movable into LHS */
1901 8107 : if (join_clause_is_movable_into(rinfo,
1902 8107 : inner_path->parent->relids,
1903 : inner_and_req))
1904 : {
1905 : /* drop if movable into RHS, but remember EC for use below */
1906 : Assert(rinfo->left_ec == rinfo->right_ec);
1907 5725 : dropped_ecs = lappend(dropped_ecs, rinfo->left_ec);
1908 5725 : continue;
1909 : }
1910 2382 : pclauses = lappend(pclauses, rinfo);
1911 : }
1912 :
1913 : /*
1914 : * EquivalenceClasses are harder to deal with than we could wish, because
1915 : * of the fact that a given EC can generate different clauses depending on
1916 : * context. Suppose we have an EC {X.X, Y.Y, Z.Z} where X and Y are the
1917 : * LHS and RHS of the current join and Z is in required_outer, and further
1918 : * suppose that the inner_path is parameterized by both X and Z. The code
1919 : * above will have produced either Z.Z = X.X or Z.Z = Y.Y from that EC,
1920 : * and in the latter case will have discarded it as being movable into the
1921 : * RHS. However, the EC machinery might have produced either Y.Y = X.X or
1922 : * Y.Y = Z.Z as the EC enforcement clause within the inner_path; it will
1923 : * not have produced both, and we can't readily tell from here which one
1924 : * it did pick. If we add no clause to this join, we'll end up with
1925 : * insufficient enforcement of the EC; either Z.Z or X.X will fail to be
1926 : * constrained to be equal to the other members of the EC. (When we come
1927 : * to join Z to this X/Y path, we will certainly drop whichever EC clause
1928 : * is generated at that join, so this omission won't get fixed later.)
1929 : *
1930 : * To handle this, for each EC we discarded such a clause from, try to
1931 : * generate a clause connecting the required_outer rels to the join's LHS
1932 : * ("Z.Z = X.X" in the terms of the above example). If successful, and if
1933 : * the clause can't be moved to the LHS, add it to the current join's
1934 : * restriction clauses. (If an EC cannot generate such a clause then it
1935 : * has nothing that needs to be enforced here, while if the clause can be
1936 : * moved into the LHS then it should have been enforced within that path.)
1937 : *
1938 : * Note that we don't need similar processing for ECs whose clause was
1939 : * considered to be movable into the LHS, because the LHS can't refer to
1940 : * the RHS so there is no comparable ambiguity about what it might
1941 : * actually be enforcing internally.
1942 : */
1943 30174 : if (dropped_ecs)
1944 : {
1945 : Relids real_outer_and_req;
1946 :
1947 5336 : real_outer_and_req = bms_union(outer_path->parent->relids,
1948 : required_outer);
1949 : eclauses =
1950 5336 : generate_join_implied_equalities_for_ecs(root,
1951 : dropped_ecs,
1952 : real_outer_and_req,
1953 : required_outer,
1954 : outer_path->parent);
1955 5582 : foreach(lc, eclauses)
1956 : {
1957 246 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
1958 :
1959 : Assert(join_clause_is_movable_into(rinfo,
1960 : outer_path->parent->relids,
1961 : real_outer_and_req));
1962 246 : if (!join_clause_is_movable_into(rinfo,
1963 246 : outer_path->parent->relids,
1964 : outer_and_req))
1965 226 : pclauses = lappend(pclauses, rinfo);
1966 : }
1967 : }
1968 :
1969 : /*
1970 : * Now, attach the identified moved-down clauses to the caller's
1971 : * restrict_clauses list. By using list_concat in this order, we leave
1972 : * the original list structure of restrict_clauses undamaged.
1973 : */
1974 30174 : *restrict_clauses = list_concat(pclauses, *restrict_clauses);
1975 :
1976 : /* If we already have a PPI for this parameterization, just return it */
1977 30174 : if ((ppi = find_param_path_info(joinrel, required_outer)))
1978 21714 : return ppi;
1979 :
1980 : /* Estimate the number of rows returned by the parameterized join */
1981 8460 : rows = get_parameterized_joinrel_size(root, joinrel,
1982 : outer_path,
1983 : inner_path,
1984 : sjinfo,
1985 : *restrict_clauses);
1986 :
1987 : /*
1988 : * And now we can build the ParamPathInfo. No point in saving the
1989 : * input-pair-dependent clause list, though.
1990 : *
1991 : * Note: in GEQO mode, we'll be called in a temporary memory context, but
1992 : * the joinrel structure is there too, so no problem.
1993 : */
1994 8460 : ppi = makeNode(ParamPathInfo);
1995 8460 : ppi->ppi_req_outer = required_outer;
1996 8460 : ppi->ppi_rows = rows;
1997 8460 : ppi->ppi_clauses = NIL;
1998 8460 : ppi->ppi_serials = NULL;
1999 8460 : joinrel->ppilist = lappend(joinrel->ppilist, ppi);
2000 :
2001 8460 : return ppi;
2002 : }
2003 :
2004 : /*
2005 : * get_appendrel_parampathinfo
2006 : * Get the ParamPathInfo for a parameterized path for an append relation.
2007 : *
2008 : * For an append relation, the rowcount estimate will just be the sum of
2009 : * the estimates for its children. However, we still need a ParamPathInfo
2010 : * to flag the fact that the path requires parameters. So this just creates
2011 : * a suitable struct with zero ppi_rows (and no ppi_clauses either, since
2012 : * the Append node isn't responsible for checking quals).
2013 : */
2014 : ParamPathInfo *
2015 41735 : get_appendrel_parampathinfo(RelOptInfo *appendrel, Relids required_outer)
2016 : {
2017 : ParamPathInfo *ppi;
2018 :
2019 : /* If rel has LATERAL refs, every path for it should account for them */
2020 : Assert(bms_is_subset(appendrel->lateral_relids, required_outer));
2021 :
2022 : /* Unparameterized paths have no ParamPathInfo */
2023 41735 : if (bms_is_empty(required_outer))
2024 41271 : return NULL;
2025 :
2026 : Assert(!bms_overlap(appendrel->relids, required_outer));
2027 :
2028 : /* If we already have a PPI for this parameterization, just return it */
2029 464 : if ((ppi = find_param_path_info(appendrel, required_outer)))
2030 110 : return ppi;
2031 :
2032 : /* Else build the ParamPathInfo */
2033 354 : ppi = makeNode(ParamPathInfo);
2034 354 : ppi->ppi_req_outer = required_outer;
2035 354 : ppi->ppi_rows = 0;
2036 354 : ppi->ppi_clauses = NIL;
2037 354 : ppi->ppi_serials = NULL;
2038 354 : appendrel->ppilist = lappend(appendrel->ppilist, ppi);
2039 :
2040 354 : return ppi;
2041 : }
2042 :
2043 : /*
2044 : * Returns a ParamPathInfo for the parameterization given by required_outer, if
2045 : * already available in the given rel. Returns NULL otherwise.
2046 : */
2047 : ParamPathInfo *
2048 319307 : find_param_path_info(RelOptInfo *rel, Relids required_outer)
2049 : {
2050 : ListCell *lc;
2051 :
2052 375402 : foreach(lc, rel->ppilist)
2053 : {
2054 233205 : ParamPathInfo *ppi = (ParamPathInfo *) lfirst(lc);
2055 :
2056 233205 : if (bms_equal(ppi->ppi_req_outer, required_outer))
2057 177110 : return ppi;
2058 : }
2059 :
2060 142197 : return NULL;
2061 : }
2062 :
2063 : /*
2064 : * get_param_path_clause_serials
2065 : * Given a parameterized Path, return the set of pushed-down clauses
2066 : * (identified by rinfo_serial numbers) enforced within the Path.
2067 : */
2068 : Bitmapset *
2069 326233 : get_param_path_clause_serials(Path *path)
2070 : {
2071 326233 : if (path->param_info == NULL)
2072 2418 : return NULL; /* not parameterized */
2073 :
2074 : /*
2075 : * We don't currently support parameterized MergeAppend paths, as
2076 : * explained in the comments for generate_orderedappend_paths.
2077 : */
2078 : Assert(!IsA(path, MergeAppendPath));
2079 :
2080 323815 : if (IsA(path, NestPath) ||
2081 316038 : IsA(path, MergePath) ||
2082 316033 : IsA(path, HashPath))
2083 : {
2084 : /*
2085 : * For a join path, combine clauses enforced within either input path
2086 : * with those enforced as joinrestrictinfo in this path. Note that
2087 : * joinrestrictinfo may include some non-pushed-down clauses, but for
2088 : * current purposes it's okay if we include those in the result. (To
2089 : * be more careful, we could check for clause_relids overlapping the
2090 : * path parameterization, but it's not worth the cycles for now.)
2091 : */
2092 9314 : JoinPath *jpath = (JoinPath *) path;
2093 : Bitmapset *pserials;
2094 : ListCell *lc;
2095 :
2096 9314 : pserials = NULL;
2097 9314 : pserials = bms_add_members(pserials,
2098 9314 : get_param_path_clause_serials(jpath->outerjoinpath));
2099 9314 : pserials = bms_add_members(pserials,
2100 9314 : get_param_path_clause_serials(jpath->innerjoinpath));
2101 12706 : foreach(lc, jpath->joinrestrictinfo)
2102 : {
2103 3392 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
2104 :
2105 3392 : pserials = bms_add_member(pserials, rinfo->rinfo_serial);
2106 : }
2107 9314 : return pserials;
2108 : }
2109 314501 : else if (IsA(path, AppendPath))
2110 : {
2111 : /*
2112 : * For an appendrel, take the intersection of the sets of clauses
2113 : * enforced in each input path.
2114 : */
2115 2418 : AppendPath *apath = (AppendPath *) path;
2116 : Bitmapset *pserials;
2117 : ListCell *lc;
2118 :
2119 2418 : pserials = NULL;
2120 9750 : foreach(lc, apath->subpaths)
2121 : {
2122 7332 : Path *subpath = (Path *) lfirst(lc);
2123 : Bitmapset *subserials;
2124 :
2125 7332 : subserials = get_param_path_clause_serials(subpath);
2126 7332 : if (lc == list_head(apath->subpaths))
2127 2398 : pserials = bms_copy(subserials);
2128 : else
2129 4934 : pserials = bms_int_members(pserials, subserials);
2130 : }
2131 2418 : return pserials;
2132 : }
2133 : else
2134 : {
2135 : /*
2136 : * Otherwise, it's a baserel path and we can use the
2137 : * previously-computed set of serial numbers.
2138 : */
2139 312083 : return path->param_info->ppi_serials;
2140 : }
2141 : }
2142 :
2143 : /*
2144 : * build_joinrel_partition_info
2145 : * Checks if the two relations being joined can use partitionwise join
2146 : * and if yes, initialize partitioning information of the resulting
2147 : * partitioned join relation.
2148 : */
2149 : static void
2150 195236 : build_joinrel_partition_info(PlannerInfo *root,
2151 : RelOptInfo *joinrel, RelOptInfo *outer_rel,
2152 : RelOptInfo *inner_rel, SpecialJoinInfo *sjinfo,
2153 : List *restrictlist)
2154 : {
2155 : PartitionScheme part_scheme;
2156 :
2157 : /* Nothing to do if partitionwise join technique is disabled. */
2158 195236 : if ((joinrel->pgs_mask & PGS_CONSIDER_PARTITIONWISE) == 0)
2159 : {
2160 : Assert(!IS_PARTITIONED_REL(joinrel));
2161 175904 : return;
2162 : }
2163 :
2164 : /*
2165 : * We can only consider this join as an input to further partitionwise
2166 : * joins if (a) the input relations are partitioned and have
2167 : * consider_partitionwise_join=true, (b) the partition schemes match, and
2168 : * (c) we can identify an equi-join between the partition keys. Note that
2169 : * if it were possible for have_partkey_equi_join to return different
2170 : * answers for the same joinrel depending on which join ordering we try
2171 : * first, this logic would break. That shouldn't happen, though, because
2172 : * of the way the query planner deduces implied equalities and reorders
2173 : * the joins. Please see optimizer/README for details.
2174 : */
2175 19332 : if (outer_rel->part_scheme == NULL || inner_rel->part_scheme == NULL ||
2176 6392 : !outer_rel->consider_partitionwise_join ||
2177 6358 : !inner_rel->consider_partitionwise_join ||
2178 6328 : outer_rel->part_scheme != inner_rel->part_scheme ||
2179 6308 : !have_partkey_equi_join(root, joinrel, outer_rel, inner_rel,
2180 : sjinfo->jointype, restrictlist))
2181 : {
2182 : Assert(!IS_PARTITIONED_REL(joinrel));
2183 13164 : return;
2184 : }
2185 :
2186 6168 : part_scheme = outer_rel->part_scheme;
2187 :
2188 : /*
2189 : * This function will be called only once for each joinrel, hence it
2190 : * should not have partitioning fields filled yet.
2191 : */
2192 : Assert(!joinrel->part_scheme && !joinrel->partexprs &&
2193 : !joinrel->nullable_partexprs && !joinrel->part_rels &&
2194 : !joinrel->boundinfo);
2195 :
2196 : /*
2197 : * If the join relation is partitioned, it uses the same partitioning
2198 : * scheme as the joining relations.
2199 : *
2200 : * Note: we calculate the partition bounds, number of partitions, and
2201 : * child-join relations of the join relation in try_partitionwise_join().
2202 : */
2203 6168 : joinrel->part_scheme = part_scheme;
2204 6168 : set_joinrel_partition_key_exprs(joinrel, outer_rel, inner_rel,
2205 : sjinfo->jointype);
2206 :
2207 : /*
2208 : * Set the consider_partitionwise_join flag.
2209 : */
2210 : Assert(outer_rel->consider_partitionwise_join);
2211 : Assert(inner_rel->consider_partitionwise_join);
2212 6168 : joinrel->consider_partitionwise_join = true;
2213 : }
2214 :
2215 : /*
2216 : * have_partkey_equi_join
2217 : *
2218 : * Returns true if there exist equi-join conditions involving pairs
2219 : * of matching partition keys of the relations being joined for all
2220 : * partition keys.
2221 : */
2222 : static bool
2223 6308 : have_partkey_equi_join(PlannerInfo *root, RelOptInfo *joinrel,
2224 : RelOptInfo *rel1, RelOptInfo *rel2,
2225 : JoinType jointype, List *restrictlist)
2226 : {
2227 6308 : PartitionScheme part_scheme = rel1->part_scheme;
2228 : bool pk_known_equal[PARTITION_MAX_KEYS];
2229 : int num_equal_pks;
2230 : ListCell *lc;
2231 :
2232 : /*
2233 : * This function must only be called when the joined relations have same
2234 : * partitioning scheme.
2235 : */
2236 : Assert(rel1->part_scheme == rel2->part_scheme);
2237 : Assert(part_scheme);
2238 :
2239 : /* We use a bool array to track which partkey columns are known equal */
2240 6308 : memset(pk_known_equal, 0, sizeof(pk_known_equal));
2241 : /* ... as well as a count of how many are known equal */
2242 6308 : num_equal_pks = 0;
2243 :
2244 : /* First, look through the join's restriction clauses */
2245 7343 : foreach(lc, restrictlist)
2246 : {
2247 7168 : RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
2248 : OpExpr *opexpr;
2249 : Expr *expr1;
2250 : Expr *expr2;
2251 : bool strict_op;
2252 : int ipk1;
2253 : int ipk2;
2254 :
2255 : /* If processing an outer join, only use its own join clauses. */
2256 7168 : if (IS_OUTER_JOIN(jointype) &&
2257 1399 : RINFO_IS_PUSHED_DOWN(rinfo, joinrel->relids))
2258 205 : continue;
2259 :
2260 : /* Skip clauses which can not be used for a join. */
2261 6963 : if (!rinfo->can_join)
2262 15 : continue;
2263 :
2264 : /* Skip clauses which are not equality conditions. */
2265 6948 : if (!rinfo->mergeopfamilies && !OidIsValid(rinfo->hashjoinoperator))
2266 5 : continue;
2267 :
2268 : /* Should be OK to assume it's an OpExpr. */
2269 6943 : opexpr = castNode(OpExpr, rinfo->clause);
2270 :
2271 : /* Match the operands to the relation. */
2272 11761 : if (bms_is_subset(rinfo->left_relids, rel1->relids) &&
2273 4818 : bms_is_subset(rinfo->right_relids, rel2->relids))
2274 : {
2275 4818 : expr1 = linitial(opexpr->args);
2276 4818 : expr2 = lsecond(opexpr->args);
2277 : }
2278 4250 : else if (bms_is_subset(rinfo->left_relids, rel2->relids) &&
2279 2125 : bms_is_subset(rinfo->right_relids, rel1->relids))
2280 : {
2281 2125 : expr1 = lsecond(opexpr->args);
2282 2125 : expr2 = linitial(opexpr->args);
2283 : }
2284 : else
2285 0 : continue;
2286 :
2287 : /*
2288 : * Now we need to know whether the join operator is strict; see
2289 : * comments in pathnodes.h.
2290 : */
2291 6943 : strict_op = op_strict(opexpr->opno);
2292 :
2293 : /*
2294 : * Vars appearing in the relation's partition keys will not have any
2295 : * varnullingrels, but those in expr1 and expr2 will if we're above
2296 : * outer joins that could null the respective rels. It's okay to
2297 : * match anyway, if the join operator is strict.
2298 : */
2299 6943 : if (strict_op)
2300 : {
2301 6943 : if (bms_overlap(rel1->relids, root->outer_join_rels))
2302 160 : expr1 = (Expr *) remove_nulling_relids((Node *) expr1,
2303 160 : root->outer_join_rels,
2304 : NULL);
2305 6943 : if (bms_overlap(rel2->relids, root->outer_join_rels))
2306 0 : expr2 = (Expr *) remove_nulling_relids((Node *) expr2,
2307 0 : root->outer_join_rels,
2308 : NULL);
2309 : }
2310 :
2311 : /*
2312 : * Only clauses referencing the partition keys are useful for
2313 : * partitionwise join.
2314 : */
2315 6943 : ipk1 = match_expr_to_partition_keys(expr1, rel1, strict_op);
2316 6943 : if (ipk1 < 0)
2317 750 : continue;
2318 6193 : ipk2 = match_expr_to_partition_keys(expr2, rel2, strict_op);
2319 6193 : if (ipk2 < 0)
2320 40 : continue;
2321 :
2322 : /*
2323 : * If the clause refers to keys at different ordinal positions, it can
2324 : * not be used for partitionwise join.
2325 : */
2326 6153 : if (ipk1 != ipk2)
2327 5 : continue;
2328 :
2329 : /* Ignore clause if we already proved these keys equal. */
2330 6148 : if (pk_known_equal[ipk1])
2331 0 : continue;
2332 :
2333 : /* Reject if the partition key collation differs from the clause's. */
2334 6148 : if (rel1->part_scheme->partcollation[ipk1] != opexpr->inputcollid)
2335 6133 : return false;
2336 :
2337 : /*
2338 : * The clause allows partitionwise join only if it uses the same
2339 : * operator family as that specified by the partition key.
2340 : */
2341 6138 : if (part_scheme->strategy == PARTITION_STRATEGY_HASH)
2342 : {
2343 60 : if (!OidIsValid(rinfo->hashjoinoperator) ||
2344 60 : !op_in_opfamily(rinfo->hashjoinoperator,
2345 60 : part_scheme->partopfamily[ipk1]))
2346 0 : continue;
2347 : }
2348 6078 : else if (!list_member_oid(rinfo->mergeopfamilies,
2349 6078 : part_scheme->partopfamily[ipk1]))
2350 0 : continue;
2351 :
2352 : /* Mark the partition key as having an equi-join clause. */
2353 6138 : pk_known_equal[ipk1] = true;
2354 :
2355 : /* We can stop examining clauses once we prove all keys equal. */
2356 6138 : if (++num_equal_pks == part_scheme->partnatts)
2357 6123 : return true;
2358 : }
2359 :
2360 : /*
2361 : * Also check to see if any keys are known equal by equivclass.c. In most
2362 : * cases there would have been a join restriction clause generated from
2363 : * any EC that had such knowledge, but there might be no such clause, or
2364 : * it might happen to constrain other members of the ECs than the ones we
2365 : * are looking for.
2366 : */
2367 180 : for (int ipk = 0; ipk < part_scheme->partnatts; ipk++)
2368 : {
2369 : Oid btree_opfamily;
2370 :
2371 : /* Ignore if we already proved these keys equal. */
2372 180 : if (pk_known_equal[ipk])
2373 5 : continue;
2374 :
2375 : /*
2376 : * We need a btree opfamily to ask equivclass.c about. If the
2377 : * partopfamily is a hash opfamily, look up its equality operator, and
2378 : * select some btree opfamily that that operator is part of. (Any
2379 : * such opfamily should be good enough, since equivclass.c will track
2380 : * multiple opfamilies as appropriate.)
2381 : */
2382 175 : if (part_scheme->strategy == PARTITION_STRATEGY_HASH)
2383 : {
2384 : Oid eq_op;
2385 : List *eq_opfamilies;
2386 :
2387 0 : eq_op = get_opfamily_member(part_scheme->partopfamily[ipk],
2388 0 : part_scheme->partopcintype[ipk],
2389 0 : part_scheme->partopcintype[ipk],
2390 : HTEqualStrategyNumber);
2391 0 : if (!OidIsValid(eq_op))
2392 0 : break; /* we're not going to succeed */
2393 0 : eq_opfamilies = get_mergejoin_opfamilies(eq_op);
2394 0 : if (eq_opfamilies == NIL)
2395 0 : break; /* we're not going to succeed */
2396 0 : btree_opfamily = linitial_oid(eq_opfamilies);
2397 : }
2398 : else
2399 175 : btree_opfamily = part_scheme->partopfamily[ipk];
2400 :
2401 : /*
2402 : * We consider only non-nullable partition keys here; nullable ones
2403 : * would not be treated as part of the same equivalence classes as
2404 : * non-nullable ones.
2405 : */
2406 305 : foreach(lc, rel1->partexprs[ipk])
2407 : {
2408 175 : Node *expr1 = (Node *) lfirst(lc);
2409 : ListCell *lc2;
2410 175 : Oid partcoll1 = rel1->part_scheme->partcollation[ipk];
2411 175 : Oid exprcoll1 = exprCollation(expr1);
2412 :
2413 315 : foreach(lc2, rel2->partexprs[ipk])
2414 : {
2415 185 : Node *expr2 = (Node *) lfirst(lc2);
2416 :
2417 185 : if (exprs_known_equal(root, expr1, expr2, btree_opfamily))
2418 : {
2419 : /*
2420 : * Ensure that the collation of the expression matches
2421 : * that of the partition key. Checking just one collation
2422 : * (partcoll1 and exprcoll1) suffices because partcoll1
2423 : * and partcoll2, as well as exprcoll1 and exprcoll2,
2424 : * should be identical. This holds because both rel1 and
2425 : * rel2 use the same PartitionScheme and expr1 and expr2
2426 : * are equal.
2427 : */
2428 55 : if (partcoll1 == exprcoll1)
2429 : {
2430 45 : Oid partcoll2 PG_USED_FOR_ASSERTS_ONLY =
2431 45 : rel2->part_scheme->partcollation[ipk];
2432 : Oid exprcoll2 PG_USED_FOR_ASSERTS_ONLY =
2433 45 : exprCollation(expr2);
2434 :
2435 : Assert(partcoll2 == exprcoll2);
2436 45 : pk_known_equal[ipk] = true;
2437 45 : break;
2438 : }
2439 : }
2440 : }
2441 175 : if (pk_known_equal[ipk])
2442 45 : break;
2443 : }
2444 :
2445 175 : if (pk_known_equal[ipk])
2446 : {
2447 : /* We can stop examining keys once we prove all keys equal. */
2448 45 : if (++num_equal_pks == part_scheme->partnatts)
2449 45 : return true;
2450 : }
2451 : else
2452 130 : break; /* no chance to succeed, give up */
2453 : }
2454 :
2455 130 : return false;
2456 : }
2457 :
2458 : /*
2459 : * match_expr_to_partition_keys
2460 : *
2461 : * Tries to match an expression to one of the nullable or non-nullable
2462 : * partition keys of "rel". Returns the matched key's ordinal position,
2463 : * or -1 if the expression could not be matched to any of the keys.
2464 : *
2465 : * strict_op must be true if the expression will be compared with the
2466 : * partition key using a strict operator. This allows us to consider
2467 : * nullable as well as nonnullable partition keys.
2468 : */
2469 : static int
2470 13136 : match_expr_to_partition_keys(Expr *expr, RelOptInfo *rel, bool strict_op)
2471 : {
2472 : int cnt;
2473 :
2474 : /* This function should be called only for partitioned relations. */
2475 : Assert(rel->part_scheme);
2476 : Assert(rel->partexprs);
2477 : Assert(rel->nullable_partexprs);
2478 :
2479 : /* Remove any relabel decorations. */
2480 13376 : while (IsA(expr, RelabelType))
2481 240 : expr = (Expr *) (castNode(RelabelType, expr))->arg;
2482 :
2483 13956 : for (cnt = 0; cnt < rel->part_scheme->partnatts; cnt++)
2484 : {
2485 : ListCell *lc;
2486 :
2487 : /* We can always match to the non-nullable partition keys. */
2488 14016 : foreach(lc, rel->partexprs[cnt])
2489 : {
2490 13126 : if (equal(lfirst(lc), expr))
2491 12276 : return cnt;
2492 : }
2493 :
2494 890 : if (!strict_op)
2495 0 : continue;
2496 :
2497 : /*
2498 : * If it's a strict join operator then a NULL partition key on one
2499 : * side will not join to any partition key on the other side, and in
2500 : * particular such a row can't join to a row from a different
2501 : * partition on the other side. So, it's okay to search the nullable
2502 : * partition keys as well.
2503 : */
2504 1020 : foreach(lc, rel->nullable_partexprs[cnt])
2505 : {
2506 200 : if (equal(lfirst(lc), expr))
2507 70 : return cnt;
2508 : }
2509 : }
2510 :
2511 790 : return -1;
2512 : }
2513 :
2514 : /*
2515 : * set_joinrel_partition_key_exprs
2516 : * Initialize partition key expressions for a partitioned joinrel.
2517 : */
2518 : static void
2519 6168 : set_joinrel_partition_key_exprs(RelOptInfo *joinrel,
2520 : RelOptInfo *outer_rel, RelOptInfo *inner_rel,
2521 : JoinType jointype)
2522 : {
2523 6168 : PartitionScheme part_scheme = joinrel->part_scheme;
2524 6168 : int partnatts = part_scheme->partnatts;
2525 :
2526 6168 : joinrel->partexprs = palloc0_array(List *, partnatts);
2527 6168 : joinrel->nullable_partexprs = palloc0_array(List *, partnatts);
2528 :
2529 : /*
2530 : * The joinrel's partition expressions are the same as those of the input
2531 : * rels, but we must properly classify them as nullable or not in the
2532 : * joinrel's output. (Also, we add some more partition expressions if
2533 : * it's a FULL JOIN.)
2534 : */
2535 12346 : for (int cnt = 0; cnt < partnatts; cnt++)
2536 : {
2537 : /* mark these const to enforce that we copy them properly */
2538 6178 : const List *outer_expr = outer_rel->partexprs[cnt];
2539 6178 : const List *outer_null_expr = outer_rel->nullable_partexprs[cnt];
2540 6178 : const List *inner_expr = inner_rel->partexprs[cnt];
2541 6178 : const List *inner_null_expr = inner_rel->nullable_partexprs[cnt];
2542 6178 : List *partexpr = NIL;
2543 6178 : List *nullable_partexpr = NIL;
2544 : ListCell *lc;
2545 :
2546 6178 : switch (jointype)
2547 : {
2548 : /*
2549 : * A join relation resulting from an INNER join may be
2550 : * regarded as partitioned by either of the inner and outer
2551 : * relation keys. For example, A INNER JOIN B ON A.a = B.b
2552 : * can be regarded as partitioned on either A.a or B.b. So we
2553 : * add both keys to the joinrel's partexpr lists. However,
2554 : * anything that was already nullable still has to be treated
2555 : * as nullable.
2556 : */
2557 5199 : case JOIN_INNER:
2558 5199 : partexpr = list_concat_copy(outer_expr, inner_expr);
2559 5199 : nullable_partexpr = list_concat_copy(outer_null_expr,
2560 : inner_null_expr);
2561 5199 : break;
2562 :
2563 : /*
2564 : * A join relation resulting from a SEMI or ANTI join may be
2565 : * regarded as partitioned by the outer relation keys. The
2566 : * inner relation's keys are no longer interesting; since they
2567 : * aren't visible in the join output, nothing could join to
2568 : * them.
2569 : */
2570 260 : case JOIN_SEMI:
2571 : case JOIN_ANTI:
2572 260 : partexpr = list_copy(outer_expr);
2573 260 : nullable_partexpr = list_copy(outer_null_expr);
2574 260 : break;
2575 :
2576 : /*
2577 : * A join relation resulting from a LEFT OUTER JOIN likewise
2578 : * may be regarded as partitioned on the (non-nullable) outer
2579 : * relation keys. The inner (nullable) relation keys are okay
2580 : * as partition keys for further joins as long as they involve
2581 : * strict join operators.
2582 : */
2583 482 : case JOIN_LEFT:
2584 482 : partexpr = list_copy(outer_expr);
2585 482 : nullable_partexpr = list_concat_copy(inner_expr,
2586 : outer_null_expr);
2587 482 : nullable_partexpr = list_concat(nullable_partexpr,
2588 : inner_null_expr);
2589 482 : break;
2590 :
2591 : /*
2592 : * For FULL OUTER JOINs, both relations are nullable, so the
2593 : * resulting join relation may be regarded as partitioned on
2594 : * either of inner and outer relation keys, but only for joins
2595 : * that involve strict join operators.
2596 : */
2597 237 : case JOIN_FULL:
2598 237 : nullable_partexpr = list_concat_copy(outer_expr,
2599 : inner_expr);
2600 237 : nullable_partexpr = list_concat(nullable_partexpr,
2601 : outer_null_expr);
2602 237 : nullable_partexpr = list_concat(nullable_partexpr,
2603 : inner_null_expr);
2604 :
2605 : /*
2606 : * Also add CoalesceExprs corresponding to each possible
2607 : * full-join output variable (that is, left side coalesced to
2608 : * right side), so that we can match equijoin expressions
2609 : * using those variables. We really only need these for
2610 : * columns merged by JOIN USING, and only with the pairs of
2611 : * input items that correspond to the data structures that
2612 : * parse analysis would build for such variables. But it's
2613 : * hard to tell which those are, so just make all the pairs.
2614 : * Extra items in the nullable_partexprs list won't cause big
2615 : * problems. (It's possible that such items will get matched
2616 : * to user-written COALESCEs, but it should still be valid to
2617 : * partition on those, since they're going to be either the
2618 : * partition column or NULL; it's the same argument as for
2619 : * partitionwise nesting of any outer join.) We assume no
2620 : * type coercions are needed to make the coalesce expressions,
2621 : * since columns of different types won't have gotten
2622 : * classified as the same PartitionScheme. Note that we
2623 : * intentionally leave out the varnullingrels decoration that
2624 : * would ordinarily appear on the Vars inside these
2625 : * CoalesceExprs, because have_partkey_equi_join will strip
2626 : * varnullingrels from the expressions it will compare to the
2627 : * partexprs.
2628 : */
2629 604 : foreach(lc, list_concat_copy(outer_expr, outer_null_expr))
2630 : {
2631 367 : Node *larg = (Node *) lfirst(lc);
2632 : ListCell *lc2;
2633 :
2634 734 : foreach(lc2, list_concat_copy(inner_expr, inner_null_expr))
2635 : {
2636 367 : Node *rarg = (Node *) lfirst(lc2);
2637 367 : CoalesceExpr *c = makeNode(CoalesceExpr);
2638 :
2639 367 : c->coalescetype = exprType(larg);
2640 367 : c->coalescecollid = exprCollation(larg);
2641 367 : c->args = list_make2(larg, rarg);
2642 367 : c->location = -1;
2643 367 : nullable_partexpr = lappend(nullable_partexpr, c);
2644 : }
2645 : }
2646 237 : break;
2647 :
2648 0 : default:
2649 0 : elog(ERROR, "unrecognized join type: %d", (int) jointype);
2650 : }
2651 :
2652 6178 : joinrel->partexprs[cnt] = partexpr;
2653 6178 : joinrel->nullable_partexprs[cnt] = nullable_partexpr;
2654 : }
2655 6168 : }
2656 :
2657 : /*
2658 : * build_child_join_reltarget
2659 : * Set up a child-join relation's reltarget from a parent-join relation.
2660 : */
2661 : static void
2662 15355 : build_child_join_reltarget(PlannerInfo *root,
2663 : RelOptInfo *parentrel,
2664 : RelOptInfo *childrel,
2665 : int nappinfos,
2666 : AppendRelInfo **appinfos)
2667 : {
2668 : /* Build the targetlist */
2669 30710 : childrel->reltarget->exprs = (List *)
2670 15355 : adjust_appendrel_attrs(root,
2671 15355 : (Node *) parentrel->reltarget->exprs,
2672 : nappinfos, appinfos);
2673 :
2674 : /* Set the cost and width fields */
2675 15355 : childrel->reltarget->cost.startup = parentrel->reltarget->cost.startup;
2676 15355 : childrel->reltarget->cost.per_tuple = parentrel->reltarget->cost.per_tuple;
2677 15355 : childrel->reltarget->width = parentrel->reltarget->width;
2678 15355 : }
2679 :
2680 : /*
2681 : * create_rel_agg_info
2682 : * Create the RelAggInfo structure for the given relation if it can produce
2683 : * grouped paths. The given relation is the non-grouped one which has the
2684 : * reltarget already constructed.
2685 : *
2686 : * calculate_grouped_rows: if true, calculate the estimated number of grouped
2687 : * rows for the relation. If false, skip the estimation to avoid unnecessary
2688 : * planning overhead.
2689 : */
2690 : RelAggInfo *
2691 17490 : create_rel_agg_info(PlannerInfo *root, RelOptInfo *rel,
2692 : bool calculate_grouped_rows)
2693 : {
2694 : ListCell *lc;
2695 : RelAggInfo *result;
2696 : PathTarget *agg_input;
2697 : PathTarget *target;
2698 17490 : List *group_clauses = NIL;
2699 17490 : List *group_exprs = NIL;
2700 :
2701 : /*
2702 : * The lists of aggregate expressions and grouping expressions should have
2703 : * been constructed.
2704 : */
2705 : Assert(root->agg_clause_list != NIL);
2706 : Assert(root->group_expr_list != NIL);
2707 :
2708 : /*
2709 : * If this is a child rel, the grouped rel for its parent rel must have
2710 : * been created if it can. So we can just use parent's RelAggInfo if
2711 : * there is one, with appropriate variable substitutions.
2712 : */
2713 17490 : if (IS_OTHER_REL(rel))
2714 : {
2715 : RelOptInfo *grouped_rel;
2716 : RelAggInfo *agg_info;
2717 :
2718 12610 : grouped_rel = rel->top_parent->grouped_rel;
2719 12610 : if (grouped_rel == NULL)
2720 1510 : return NULL;
2721 :
2722 : Assert(IS_GROUPED_REL(grouped_rel));
2723 :
2724 : /* Must do multi-level transformation */
2725 : agg_info = (RelAggInfo *)
2726 11100 : adjust_appendrel_attrs_multilevel(root,
2727 11100 : (Node *) grouped_rel->agg_info,
2728 : rel,
2729 11100 : rel->top_parent);
2730 :
2731 11100 : agg_info->apply_agg_at = NULL; /* caller will change this later */
2732 :
2733 11100 : if (calculate_grouped_rows)
2734 : {
2735 770 : agg_info->grouped_rows =
2736 770 : estimate_num_groups(root, agg_info->group_exprs,
2737 : rel->rows, NULL, NULL);
2738 :
2739 : /*
2740 : * The grouped paths for the given relation are considered useful
2741 : * iff the average group size is no less than
2742 : * min_eager_agg_group_size.
2743 : */
2744 770 : agg_info->agg_useful =
2745 770 : (rel->rows / agg_info->grouped_rows) >= min_eager_agg_group_size;
2746 : }
2747 :
2748 11100 : return agg_info;
2749 : }
2750 :
2751 : /* Check if it's possible to produce grouped paths for this relation. */
2752 4880 : if (!eager_aggregation_possible_for_relation(root, rel))
2753 876 : return NULL;
2754 :
2755 : /*
2756 : * Create targets for the grouped paths and for the input paths of the
2757 : * grouped paths.
2758 : */
2759 4004 : target = create_empty_pathtarget();
2760 4004 : agg_input = create_empty_pathtarget();
2761 :
2762 : /* ... and initialize these targets */
2763 4004 : if (!init_grouping_targets(root, rel, target, agg_input,
2764 : &group_clauses, &group_exprs))
2765 125 : return NULL;
2766 :
2767 : /*
2768 : * Eager aggregation is not applicable if there are no available grouping
2769 : * expressions.
2770 : */
2771 3879 : if (group_clauses == NIL)
2772 15 : return NULL;
2773 :
2774 : /* Add aggregates to the grouping target */
2775 9958 : foreach(lc, root->agg_clause_list)
2776 : {
2777 6094 : AggClauseInfo *ac_info = lfirst_node(AggClauseInfo, lc);
2778 : Aggref *aggref;
2779 :
2780 : Assert(IsA(ac_info->aggref, Aggref));
2781 :
2782 6094 : aggref = (Aggref *) copyObject(ac_info->aggref);
2783 6094 : mark_partial_aggref(aggref, AGGSPLIT_INITIAL_SERIAL);
2784 :
2785 6094 : add_column_to_pathtarget(target, (Expr *) aggref, 0);
2786 : }
2787 :
2788 : /* Set the estimated eval cost and output width for both targets */
2789 3864 : set_pathtarget_cost_width(root, target);
2790 3864 : set_pathtarget_cost_width(root, agg_input);
2791 :
2792 : /* build the RelAggInfo result */
2793 3864 : result = makeNode(RelAggInfo);
2794 3864 : result->target = target;
2795 3864 : result->agg_input = agg_input;
2796 3864 : result->group_clauses = group_clauses;
2797 3864 : result->group_exprs = group_exprs;
2798 3864 : result->apply_agg_at = NULL; /* caller will change this later */
2799 :
2800 3864 : if (calculate_grouped_rows)
2801 : {
2802 687 : result->grouped_rows = estimate_num_groups(root, result->group_exprs,
2803 : rel->rows, NULL, NULL);
2804 :
2805 : /*
2806 : * The grouped paths for the given relation are considered useful iff
2807 : * the average group size is no less than min_eager_agg_group_size.
2808 : */
2809 687 : result->agg_useful =
2810 687 : (rel->rows / result->grouped_rows) >= min_eager_agg_group_size;
2811 : }
2812 :
2813 3864 : return result;
2814 : }
2815 :
2816 : /*
2817 : * eager_aggregation_possible_for_relation
2818 : * Check if it's possible to produce grouped paths for the given relation.
2819 : */
2820 : static bool
2821 4880 : eager_aggregation_possible_for_relation(PlannerInfo *root, RelOptInfo *rel)
2822 : {
2823 : ListCell *lc;
2824 : int cur_relid;
2825 :
2826 : /*
2827 : * Check to see if the given relation is in the nullable side of an outer
2828 : * join. In this case, we cannot push a partial aggregation down to the
2829 : * relation, because the NULL-extended rows produced by the outer join
2830 : * would not be available when we perform the partial aggregation, while
2831 : * with a non-eager-aggregation plan these rows are available for the
2832 : * top-level aggregation. Doing so may result in the rows being grouped
2833 : * differently than expected, or produce incorrect values from the
2834 : * aggregate functions.
2835 : */
2836 4880 : cur_relid = -1;
2837 13930 : while ((cur_relid = bms_next_member(rel->relids, cur_relid)) >= 0)
2838 : {
2839 9203 : RelOptInfo *baserel = find_base_rel_ignore_join(root, cur_relid);
2840 :
2841 9203 : if (baserel == NULL)
2842 333 : continue; /* ignore outer joins in rel->relids */
2843 :
2844 8870 : if (!bms_is_subset(baserel->nulling_relids, rel->relids))
2845 153 : return false;
2846 : }
2847 :
2848 : /*
2849 : * For now we don't try to support PlaceHolderVars.
2850 : */
2851 14593 : foreach(lc, rel->reltarget->exprs)
2852 : {
2853 9876 : Expr *expr = lfirst(lc);
2854 :
2855 9876 : if (IsA(expr, PlaceHolderVar))
2856 10 : return false;
2857 : }
2858 :
2859 : /* Caller should only pass base relations or joins. */
2860 : Assert(rel->reloptkind == RELOPT_BASEREL ||
2861 : rel->reloptkind == RELOPT_JOINREL);
2862 :
2863 : /*
2864 : * Check if all aggregate expressions can be evaluated on this relation
2865 : * level.
2866 : */
2867 10996 : foreach(lc, root->agg_clause_list)
2868 : {
2869 6992 : AggClauseInfo *ac_info = lfirst_node(AggClauseInfo, lc);
2870 :
2871 : Assert(IsA(ac_info->aggref, Aggref));
2872 :
2873 : /*
2874 : * Give up if any aggregate requires relations other than the current
2875 : * one. If the aggregate requires the current relation plus
2876 : * additional relations, grouping the current relation could make some
2877 : * input rows unavailable for the higher aggregate and may reduce the
2878 : * number of input rows it receives. If the aggregate does not
2879 : * require the current relation at all, it should not be grouped, as
2880 : * we do not support joining two grouped relations.
2881 : */
2882 6992 : if (!bms_is_subset(ac_info->agg_eval_at, rel->relids))
2883 713 : return false;
2884 : }
2885 :
2886 4004 : return true;
2887 : }
2888 :
2889 : /*
2890 : * init_grouping_targets
2891 : * Initialize the target for grouped paths (target) as well as the target
2892 : * for paths that generate input for the grouped paths (agg_input).
2893 : *
2894 : * We also construct the list of SortGroupClauses and the list of grouping
2895 : * expressions for the partial aggregation, and return them in *group_clause
2896 : * and *group_exprs.
2897 : *
2898 : * Return true if the targets could be initialized, false otherwise.
2899 : */
2900 : static bool
2901 4004 : init_grouping_targets(PlannerInfo *root, RelOptInfo *rel,
2902 : PathTarget *target, PathTarget *agg_input,
2903 : List **group_clauses, List **group_exprs)
2904 : {
2905 : ListCell *lc;
2906 4004 : List *possibly_dependent = NIL;
2907 : Index maxSortGroupRef;
2908 :
2909 : /* Identify the max sortgroupref */
2910 4004 : maxSortGroupRef = 0;
2911 18873 : foreach(lc, root->processed_tlist)
2912 : {
2913 14869 : Index ref = ((TargetEntry *) lfirst(lc))->ressortgroupref;
2914 :
2915 14869 : if (ref > maxSortGroupRef)
2916 4376 : maxSortGroupRef = ref;
2917 : }
2918 :
2919 : /*
2920 : * At this point, all Vars from this relation that are needed by upper
2921 : * joins or are required in the final targetlist should already be present
2922 : * in its reltarget. Therefore, we can safely iterate over this
2923 : * relation's reltarget->exprs to construct the PathTarget and grouping
2924 : * clauses for the grouped paths.
2925 : */
2926 12388 : foreach(lc, rel->reltarget->exprs)
2927 : {
2928 8389 : Expr *expr = (Expr *) lfirst(lc);
2929 : Index sortgroupref;
2930 :
2931 : /*
2932 : * Given that PlaceHolderVar currently prevents us from doing eager
2933 : * aggregation, the source target cannot contain anything more complex
2934 : * than a Var.
2935 : */
2936 : Assert(IsA(expr, Var));
2937 :
2938 : /*
2939 : * Get the sortgroupref of the expr if it is found among, or can be
2940 : * deduced from, the original grouping expressions.
2941 : */
2942 8389 : sortgroupref = get_expression_sortgroupref(root, expr);
2943 8389 : if (sortgroupref > 0)
2944 : {
2945 : SortGroupClause *sgc;
2946 :
2947 : /* Find the matching SortGroupClause */
2948 3928 : sgc = get_sortgroupref_clause(sortgroupref, root->processed_groupClause);
2949 : Assert(sgc->tleSortGroupRef <= maxSortGroupRef);
2950 :
2951 : /*
2952 : * If the target expression is to be used as a grouping key, it
2953 : * should be emitted by the grouped paths that have been pushed
2954 : * down to this relation level.
2955 : */
2956 3928 : add_column_to_pathtarget(target, expr, sortgroupref);
2957 :
2958 : /*
2959 : * ... and it also should be emitted by the input paths.
2960 : */
2961 3928 : add_column_to_pathtarget(agg_input, expr, sortgroupref);
2962 :
2963 : /*
2964 : * Record this SortGroupClause and grouping expression. Note that
2965 : * this SortGroupClause might have already been recorded.
2966 : */
2967 3928 : if (!list_member(*group_clauses, sgc))
2968 : {
2969 3818 : *group_clauses = lappend(*group_clauses, sgc);
2970 3818 : *group_exprs = lappend(*group_exprs, expr);
2971 : }
2972 : }
2973 4461 : else if (is_var_needed_by_join(root, (Var *) expr, rel))
2974 : {
2975 : /*
2976 : * The expression is needed for an upper join but is neither in
2977 : * the GROUP BY clause nor derivable from it using EC (otherwise,
2978 : * it would have already been included in the targets above). We
2979 : * need to create a special SortGroupClause for this expression.
2980 : *
2981 : * It is important to include such expressions in the grouping
2982 : * keys. This is essential to ensure that an aggregated row from
2983 : * the partial aggregation matches the other side of the join if
2984 : * and only if each row in the partial group does. This ensures
2985 : * that all rows within the same partial group share the same
2986 : * 'destiny', which is crucial for maintaining correctness.
2987 : */
2988 : SortGroupClause *sgc;
2989 : TypeCacheEntry *tce;
2990 : Oid equalimageproc;
2991 :
2992 : /*
2993 : * But first, check if equality implies image equality for this
2994 : * expression. If not, we cannot use it as a grouping key. See
2995 : * comments in create_grouping_expr_infos().
2996 : */
2997 319 : tce = lookup_type_cache(exprType((Node *) expr),
2998 : TYPECACHE_BTREE_OPFAMILY);
2999 319 : if (!OidIsValid(tce->btree_opf) ||
3000 319 : !OidIsValid(tce->btree_opintype))
3001 5 : return false;
3002 :
3003 319 : equalimageproc = get_opfamily_proc(tce->btree_opf,
3004 : tce->btree_opintype,
3005 : tce->btree_opintype,
3006 : BTEQUALIMAGE_PROC);
3007 319 : if (!OidIsValid(equalimageproc) ||
3008 314 : !DatumGetBool(OidFunctionCall1Coll(equalimageproc,
3009 : tce->typcollation,
3010 : ObjectIdGetDatum(tce->btree_opintype))))
3011 5 : return false;
3012 :
3013 : /* Create the SortGroupClause. */
3014 314 : sgc = makeNode(SortGroupClause);
3015 :
3016 : /* Initialize the SortGroupClause. */
3017 314 : sgc->tleSortGroupRef = ++maxSortGroupRef;
3018 314 : get_sort_group_operators(exprType((Node *) expr),
3019 : false, true, false,
3020 : &sgc->sortop, &sgc->eqop, NULL,
3021 : &sgc->hashable);
3022 :
3023 : /* This expression should be emitted by the grouped paths */
3024 314 : add_column_to_pathtarget(target, expr, sgc->tleSortGroupRef);
3025 :
3026 : /* ... and it also should be emitted by the input paths. */
3027 314 : add_column_to_pathtarget(agg_input, expr, sgc->tleSortGroupRef);
3028 :
3029 : /* Record this SortGroupClause and grouping expression */
3030 314 : *group_clauses = lappend(*group_clauses, sgc);
3031 314 : *group_exprs = lappend(*group_exprs, expr);
3032 : }
3033 4142 : else if (is_var_in_aggref_only(root, (Var *) expr))
3034 : {
3035 : /*
3036 : * The expression is referenced by an aggregate function pushed
3037 : * down to this relation and does not appear elsewhere in the
3038 : * targetlist or havingQual. Add it to 'agg_input' but not to
3039 : * 'target'.
3040 : */
3041 3862 : add_new_column_to_pathtarget(agg_input, expr);
3042 : }
3043 : else
3044 : {
3045 : /*
3046 : * The expression may be functionally dependent on other
3047 : * expressions in the target, but we cannot verify this until all
3048 : * target expressions have been constructed.
3049 : */
3050 280 : possibly_dependent = lappend(possibly_dependent, expr);
3051 : }
3052 : }
3053 :
3054 : /*
3055 : * Now we can verify whether an expression is functionally dependent on
3056 : * others.
3057 : */
3058 4039 : foreach(lc, possibly_dependent)
3059 : {
3060 : Var *tvar;
3061 160 : List *deps = NIL;
3062 : RangeTblEntry *rte;
3063 :
3064 160 : tvar = lfirst_node(Var, lc);
3065 160 : rte = root->simple_rte_array[tvar->varno];
3066 :
3067 160 : if (check_functional_grouping(rte->relid, tvar->varno,
3068 : tvar->varlevelsup,
3069 : target->exprs, &deps))
3070 : {
3071 : /*
3072 : * The expression is functionally dependent on other target
3073 : * expressions, so it can be included in the targets. Since it
3074 : * will not be used as a grouping key, a sortgroupref is not
3075 : * needed for it.
3076 : */
3077 40 : add_new_column_to_pathtarget(target, (Expr *) tvar);
3078 40 : add_new_column_to_pathtarget(agg_input, (Expr *) tvar);
3079 : }
3080 : else
3081 : {
3082 : /*
3083 : * We may arrive here with a grouping expression that is proven
3084 : * redundant by EquivalenceClass processing, such as 't1.a' in the
3085 : * query below.
3086 : *
3087 : * select max(t1.c) from t t1, t t2 where t1.a = 1 group by t1.a,
3088 : * t1.b;
3089 : *
3090 : * For now we just give up in this case.
3091 : */
3092 120 : return false;
3093 : }
3094 : }
3095 :
3096 3879 : return true;
3097 : }
3098 :
3099 : /*
3100 : * is_var_in_aggref_only
3101 : * Check whether the given Var appears in aggregate expressions and not
3102 : * elsewhere in the targetlist or havingQual.
3103 : */
3104 : static bool
3105 4142 : is_var_in_aggref_only(PlannerInfo *root, Var *var)
3106 : {
3107 : ListCell *lc;
3108 :
3109 : /*
3110 : * Search the list of aggregate expressions for the Var.
3111 : */
3112 4542 : foreach(lc, root->agg_clause_list)
3113 : {
3114 4262 : AggClauseInfo *ac_info = lfirst_node(AggClauseInfo, lc);
3115 : List *vars;
3116 :
3117 : Assert(IsA(ac_info->aggref, Aggref));
3118 :
3119 4262 : if (!bms_is_member(var->varno, ac_info->agg_eval_at))
3120 400 : continue;
3121 :
3122 3862 : vars = pull_var_clause((Node *) ac_info->aggref,
3123 : PVC_RECURSE_AGGREGATES |
3124 : PVC_RECURSE_WINDOWFUNCS |
3125 : PVC_RECURSE_PLACEHOLDERS);
3126 :
3127 3862 : if (list_member(vars, var))
3128 : {
3129 3862 : list_free(vars);
3130 3862 : break;
3131 : }
3132 :
3133 0 : list_free(vars);
3134 : }
3135 :
3136 4142 : return (lc != NULL && !list_member(root->tlist_vars, var));
3137 : }
3138 :
3139 : /*
3140 : * is_var_needed_by_join
3141 : * Check if the given Var is needed by joins above the current rel.
3142 : */
3143 : static bool
3144 4461 : is_var_needed_by_join(PlannerInfo *root, Var *var, RelOptInfo *rel)
3145 : {
3146 : Relids relids;
3147 : int attno;
3148 : RelOptInfo *baserel;
3149 :
3150 : /*
3151 : * Note that when checking if the Var is needed by joins above, we want to
3152 : * exclude cases where the Var is only needed in the final targetlist. So
3153 : * include "relation 0" in the check.
3154 : */
3155 4461 : relids = bms_copy(rel->relids);
3156 4461 : relids = bms_add_member(relids, 0);
3157 :
3158 4461 : baserel = find_base_rel(root, var->varno);
3159 4461 : attno = var->varattno - baserel->min_attr;
3160 :
3161 4461 : return bms_nonempty_difference(baserel->attr_needed[attno], relids);
3162 : }
3163 :
3164 : /*
3165 : * get_expression_sortgroupref
3166 : * Return the sortgroupref of the given "expr" if it is found among the
3167 : * original grouping expressions, or is known equal to any of the original
3168 : * grouping expressions due to equivalence relationships. Return 0 if no
3169 : * match is found.
3170 : */
3171 : static Index
3172 8389 : get_expression_sortgroupref(PlannerInfo *root, Expr *expr)
3173 : {
3174 : ListCell *lc;
3175 :
3176 : Assert(IsA(expr, Var));
3177 :
3178 13006 : foreach(lc, root->group_expr_list)
3179 : {
3180 8545 : GroupingExprInfo *ge_info = lfirst_node(GroupingExprInfo, lc);
3181 : ListCell *lc1;
3182 :
3183 : Assert(IsA(ge_info->expr, Var));
3184 : Assert(ge_info->sortgroupref > 0);
3185 :
3186 8545 : if (equal(expr, ge_info->expr))
3187 3928 : return ge_info->sortgroupref;
3188 :
3189 4857 : if (ge_info->ec == NULL ||
3190 4857 : !bms_is_member(((Var *) expr)->varno, ge_info->ec->ec_relids))
3191 2265 : continue;
3192 :
3193 : /*
3194 : * Scan the EquivalenceClass, looking for a match to the given
3195 : * expression. We ignore child members here.
3196 : */
3197 7549 : foreach(lc1, ge_info->ec->ec_members)
3198 : {
3199 5197 : EquivalenceMember *em = (EquivalenceMember *) lfirst(lc1);
3200 :
3201 : /* Child members should not exist in ec_members */
3202 : Assert(!em->em_is_child);
3203 :
3204 5197 : if (equal(expr, em->em_expr))
3205 240 : return ge_info->sortgroupref;
3206 : }
3207 : }
3208 :
3209 : /* no match is found */
3210 4461 : return 0;
3211 : }
|
