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