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