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