Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * initsplan.c
4 : : * Target list, group by, qualification, joininfo initialization routines
5 : : *
6 : : * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
7 : : * Portions Copyright (c) 1994, Regents of the University of California
8 : : *
9 : : *
10 : : * IDENTIFICATION
11 : : * src/backend/optimizer/plan/initsplan.c
12 : : *
13 : : *-------------------------------------------------------------------------
14 : : */
15 : : #include "postgres.h"
16 : :
17 : : #include "catalog/pg_constraint.h"
18 : : #include "catalog/pg_type.h"
19 : : #include "nodes/makefuncs.h"
20 : : #include "nodes/nodeFuncs.h"
21 : : #include "optimizer/clauses.h"
22 : : #include "optimizer/cost.h"
23 : : #include "optimizer/inherit.h"
24 : : #include "optimizer/joininfo.h"
25 : : #include "optimizer/optimizer.h"
26 : : #include "optimizer/pathnode.h"
27 : : #include "optimizer/paths.h"
28 : : #include "optimizer/placeholder.h"
29 : : #include "optimizer/planmain.h"
30 : : #include "optimizer/planner.h"
31 : : #include "optimizer/restrictinfo.h"
32 : : #include "parser/analyze.h"
33 : : #include "rewrite/rewriteManip.h"
34 : : #include "utils/lsyscache.h"
35 : : #include "utils/rel.h"
36 : : #include "utils/typcache.h"
37 : :
38 : : /* These parameters are set by GUC */
39 : : int from_collapse_limit;
40 : : int join_collapse_limit;
41 : :
42 : :
43 : : /*
44 : : * deconstruct_jointree requires multiple passes over the join tree, because we
45 : : * need to finish computing JoinDomains before we start distributing quals.
46 : : * As long as we have to do that, other information such as the relevant
47 : : * qualscopes might as well be computed in the first pass too.
48 : : *
49 : : * deconstruct_recurse recursively examines the join tree and builds a List
50 : : * (in depth-first traversal order) of JoinTreeItem structs, which are then
51 : : * processed iteratively by deconstruct_distribute. If there are outer
52 : : * joins, non-degenerate outer join clauses are processed in a third pass
53 : : * deconstruct_distribute_oj_quals.
54 : : *
55 : : * The JoinTreeItem structs themselves can be freed at the end of
56 : : * deconstruct_jointree, but do not modify or free their substructure,
57 : : * as the relid sets may also be pointed to by RestrictInfo and
58 : : * SpecialJoinInfo nodes.
59 : : */
60 : : typedef struct JoinTreeItem
61 : : {
62 : : /* Fields filled during deconstruct_recurse: */
63 : : Node *jtnode; /* jointree node to examine */
64 : : JoinDomain *jdomain; /* join domain for its ON/WHERE clauses */
65 : : struct JoinTreeItem *jti_parent; /* JoinTreeItem for this node's
66 : : * parent, or NULL if it's the top */
67 : : Relids qualscope; /* base+OJ Relids syntactically included in
68 : : * this jointree node */
69 : : Relids inner_join_rels; /* base+OJ Relids syntactically included
70 : : * in inner joins appearing at or below
71 : : * this jointree node */
72 : : Relids left_rels; /* if join node, Relids of the left side */
73 : : Relids right_rels; /* if join node, Relids of the right side */
74 : : Relids nonnullable_rels; /* if outer join, Relids of the
75 : : * non-nullable side */
76 : : /* Fields filled during deconstruct_distribute: */
77 : : SpecialJoinInfo *sjinfo; /* if outer join, its SpecialJoinInfo */
78 : : List *oj_joinclauses; /* outer join quals not yet distributed */
79 : : List *lateral_clauses; /* quals postponed from children due to
80 : : * lateral references */
81 : : } JoinTreeItem;
82 : :
83 : :
84 : : static void extract_lateral_references(PlannerInfo *root, RelOptInfo *brel,
85 : : Index rtindex);
86 : : static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode,
87 : : JoinDomain *parent_domain,
88 : : JoinTreeItem *parent_jtitem,
89 : : List **item_list);
90 : : static void deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem);
91 : : static void process_security_barrier_quals(PlannerInfo *root,
92 : : int rti, JoinTreeItem *jtitem);
93 : : static void mark_rels_nulled_by_join(PlannerInfo *root, Index ojrelid,
94 : : Relids lower_rels);
95 : : static SpecialJoinInfo *make_outerjoininfo(PlannerInfo *root,
96 : : Relids left_rels, Relids right_rels,
97 : : Relids inner_join_rels,
98 : : JoinType jointype, Index ojrelid,
99 : : List *clause);
100 : : static void compute_semijoin_info(PlannerInfo *root, SpecialJoinInfo *sjinfo,
101 : : List *clause);
102 : : static void deconstruct_distribute_oj_quals(PlannerInfo *root,
103 : : List *jtitems,
104 : : JoinTreeItem *jtitem);
105 : : static void distribute_quals_to_rels(PlannerInfo *root, List *clauses,
106 : : JoinTreeItem *jtitem,
107 : : SpecialJoinInfo *sjinfo,
108 : : Index security_level,
109 : : Relids qualscope,
110 : : Relids ojscope,
111 : : Relids outerjoin_nonnullable,
112 : : Relids incompatible_relids,
113 : : bool allow_equivalence,
114 : : bool has_clone,
115 : : bool is_clone,
116 : : List **postponed_oj_qual_list);
117 : : static void distribute_qual_to_rels(PlannerInfo *root, Node *clause,
118 : : JoinTreeItem *jtitem,
119 : : SpecialJoinInfo *sjinfo,
120 : : Index security_level,
121 : : Relids qualscope,
122 : : Relids ojscope,
123 : : Relids outerjoin_nonnullable,
124 : : Relids incompatible_relids,
125 : : bool allow_equivalence,
126 : : bool has_clone,
127 : : bool is_clone,
128 : : List **postponed_oj_qual_list);
129 : : static bool check_redundant_nullability_qual(PlannerInfo *root, Node *clause);
130 : : static Relids get_join_domain_min_rels(PlannerInfo *root, Relids domain_relids);
131 : : static void check_mergejoinable(RestrictInfo *restrictinfo);
132 : : static void check_hashjoinable(RestrictInfo *restrictinfo);
133 : : static void check_memoizable(RestrictInfo *restrictinfo);
134 : :
135 : :
136 : : /*****************************************************************************
137 : : *
138 : : * JOIN TREES
139 : : *
140 : : *****************************************************************************/
141 : :
142 : : /*
143 : : * add_base_rels_to_query
144 : : *
145 : : * Scan the query's jointree and create baserel RelOptInfos for all
146 : : * the base relations (e.g., table, subquery, and function RTEs)
147 : : * appearing in the jointree.
148 : : *
149 : : * The initial invocation must pass root->parse->jointree as the value of
150 : : * jtnode. Internally, the function recurses through the jointree.
151 : : *
152 : : * At the end of this process, there should be one baserel RelOptInfo for
153 : : * every non-join RTE that is used in the query. Some of the baserels
154 : : * may be appendrel parents, which will require additional "otherrel"
155 : : * RelOptInfos for their member rels, but those are added later.
156 : : */
157 : : void
7398 tgl@sss.pgh.pa.us 158 :CBC 441595 : add_base_rels_to_query(PlannerInfo *root, Node *jtnode)
159 : : {
9125 160 [ - + ]: 441595 : if (jtnode == NULL)
8270 tgl@sss.pgh.pa.us 161 :UBC 0 : return;
9108 tgl@sss.pgh.pa.us 162 [ + + ]:CBC 441595 : if (IsA(jtnode, RangeTblRef))
163 : : {
164 : 230125 : int varno = ((RangeTblRef *) jtnode)->rtindex;
165 : :
3078 rhaas@postgresql.org 166 : 230125 : (void) build_simple_rel(root, varno, NULL);
167 : : }
9108 tgl@sss.pgh.pa.us 168 [ + + ]: 211470 : else if (IsA(jtnode, FromExpr))
169 : : {
170 : 165519 : FromExpr *f = (FromExpr *) jtnode;
171 : : ListCell *l;
172 : :
173 [ + - + + : 355844 : foreach(l, f->fromlist)
+ + ]
8270 174 : 190334 : add_base_rels_to_query(root, lfirst(l));
175 : : }
9125 176 [ + - ]: 45951 : else if (IsA(jtnode, JoinExpr))
177 : : {
178 : 45951 : JoinExpr *j = (JoinExpr *) jtnode;
179 : :
8270 180 : 45951 : add_base_rels_to_query(root, j->larg);
181 : 45951 : add_base_rels_to_query(root, j->rarg);
182 : : }
183 : : else
8079 tgl@sss.pgh.pa.us 184 [ # # ]:UBC 0 : elog(ERROR, "unrecognized node type: %d",
185 : : (int) nodeTag(jtnode));
186 : : }
187 : :
188 : : /*
189 : : * add_other_rels_to_query
190 : : * create "otherrel" RelOptInfos for the children of appendrel baserels
191 : : *
192 : : * At the end of this process, there should be RelOptInfos for all relations
193 : : * that will be scanned by the query.
194 : : */
195 : : void
2356 tgl@sss.pgh.pa.us 196 :CBC 159350 : add_other_rels_to_query(PlannerInfo *root)
197 : : {
198 : : int rti;
199 : :
200 [ + + ]: 485477 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
201 : : {
202 : 326128 : RelOptInfo *rel = root->simple_rel_array[rti];
203 : 326128 : RangeTblEntry *rte = root->simple_rte_array[rti];
204 : :
205 : : /* there may be empty slots corresponding to non-baserel RTEs */
206 [ + + ]: 326128 : if (rel == NULL)
207 : 76047 : continue;
208 : :
209 : : /* Ignore any "otherrels" that were already added. */
210 [ + + ]: 250081 : if (rel->reloptkind != RELOPT_BASEREL)
211 : 25548 : continue;
212 : :
213 : : /* If it's marked as inheritable, look for children. */
214 [ + + ]: 224533 : if (rte->inh)
2352 215 : 10489 : expand_inherited_rtentry(root, rel, rte, rti);
216 : : }
2356 217 : 159349 : }
218 : :
219 : :
220 : : /*****************************************************************************
221 : : *
222 : : * TARGET LISTS
223 : : *
224 : : *****************************************************************************/
225 : :
226 : : /*
227 : : * build_base_rel_tlists
228 : : * Add targetlist entries for each var needed in the query's final tlist
229 : : * (and HAVING clause, if any) to the appropriate base relations.
230 : : *
231 : : * We mark such vars as needed by "relation 0" to ensure that they will
232 : : * propagate up through all join plan steps.
233 : : */
234 : : void
7398 235 : 159365 : build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
236 : : {
5984 237 : 159365 : List *tlist_vars = pull_var_clause((Node *) final_tlist,
238 : : PVC_RECURSE_AGGREGATES |
239 : : PVC_RECURSE_WINDOWFUNCS |
240 : : PVC_INCLUDE_PLACEHOLDERS);
241 : :
8105 242 [ + + ]: 159365 : if (tlist_vars != NIL)
243 : : {
1116 244 : 150777 : add_vars_to_targetlist(root, tlist_vars, bms_make_singleton(0));
7769 neilc@samurai.com 245 : 150777 : list_free(tlist_vars);
246 : : }
247 : :
248 : : /*
249 : : * If there's a HAVING clause, we'll need the Vars it uses, too. Note
250 : : * that HAVING can contain Aggrefs but not WindowFuncs.
251 : : */
3530 tgl@sss.pgh.pa.us 252 [ + + ]: 159365 : if (root->parse->havingQual)
253 : : {
254 : 427 : List *having_vars = pull_var_clause(root->parse->havingQual,
255 : : PVC_RECURSE_AGGREGATES |
256 : : PVC_INCLUDE_PLACEHOLDERS);
257 : :
258 [ + + ]: 427 : if (having_vars != NIL)
259 : : {
260 : 379 : add_vars_to_targetlist(root, having_vars,
261 : : bms_make_singleton(0));
262 : 379 : list_free(having_vars);
263 : : }
264 : : }
8579 265 : 159365 : }
266 : :
267 : : /*
268 : : * add_vars_to_targetlist
269 : : * For each variable appearing in the list, add it to the owning
270 : : * relation's targetlist if not already present, and mark the variable
271 : : * as being needed for the indicated join (or for final output if
272 : : * where_needed includes "relation 0").
273 : : *
274 : : * The list may also contain PlaceHolderVars. These don't necessarily
275 : : * have a single owning relation; we keep their attr_needed info in
276 : : * root->placeholder_list instead. Find or create the associated
277 : : * PlaceHolderInfo entry, and update its ph_needed.
278 : : *
279 : : * See also add_vars_to_attr_needed.
280 : : */
281 : : void
5142 282 : 297895 : add_vars_to_targetlist(PlannerInfo *root, List *vars,
283 : : Relids where_needed)
284 : : {
285 : : ListCell *temp;
286 : :
8105 287 [ - + ]: 297895 : Assert(!bms_is_empty(where_needed));
288 : :
8579 289 [ + + + + : 1079192 : foreach(temp, vars)
+ + ]
290 : : {
6164 291 : 781297 : Node *node = (Node *) lfirst(temp);
292 : :
293 [ + + ]: 781297 : if (IsA(node, Var))
294 : : {
295 : 779732 : Var *var = (Var *) node;
296 : 779732 : RelOptInfo *rel = find_base_rel(root, var->varno);
297 : 779732 : int attno = var->varattno;
298 : :
4403 299 [ + + ]: 779732 : if (bms_is_subset(where_needed, rel->relids))
300 : 698 : continue;
6164 301 [ + - - + ]: 779034 : Assert(attno >= rel->min_attr && attno <= rel->max_attr);
302 : 779034 : attno -= rel->min_attr;
303 [ + + ]: 779034 : if (rel->attr_needed[attno] == NULL)
304 : : {
305 : : /*
306 : : * Variable not yet requested, so add to rel's targetlist.
307 : : *
308 : : * The value available at the rel's scan level has not been
309 : : * nulled by any outer join, so drop its varnullingrels.
310 : : * (We'll put those back as we climb up the join tree.)
311 : : */
950 312 : 596156 : var = copyObject(var);
313 : 596156 : var->varnullingrels = NULL;
314 : 596156 : rel->reltarget->exprs = lappend(rel->reltarget->exprs, var);
315 : : /* reltarget cost and width will be computed later */
316 : : }
6164 317 : 779034 : rel->attr_needed[attno] = bms_add_members(rel->attr_needed[attno],
318 : : where_needed);
319 : : }
320 [ + - ]: 1565 : else if (IsA(node, PlaceHolderVar))
321 : : {
322 : 1565 : PlaceHolderVar *phv = (PlaceHolderVar *) node;
1116 323 : 1565 : PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
324 : :
6164 325 : 1565 : phinfo->ph_needed = bms_add_members(phinfo->ph_needed,
326 : : where_needed);
327 : : }
328 : : else
6164 tgl@sss.pgh.pa.us 329 [ # # ]:UBC 0 : elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
330 : : }
8579 tgl@sss.pgh.pa.us 331 :CBC 297895 : }
332 : :
333 : : /*
334 : : * add_vars_to_attr_needed
335 : : * This does a subset of what add_vars_to_targetlist does: it just
336 : : * updates attr_needed for Vars and ph_needed for PlaceHolderVars.
337 : : * We assume the Vars are already in their relations' targetlists.
338 : : *
339 : : * This is used to rebuild attr_needed/ph_needed sets after removal
340 : : * of a useless outer join. The removed join clause might have been
341 : : * the only upper-level use of some other relation's Var, in which
342 : : * case we can reduce that Var's attr_needed and thereby possibly
343 : : * open the door to further join removals. But we can't tell that
344 : : * without tedious reconstruction of the attr_needed data.
345 : : *
346 : : * Note that if a Var's attr_needed is successfully reduced to empty,
347 : : * it will still be in the relation's targetlist even though we do
348 : : * not really need the scan plan node to emit it. The extra plan
349 : : * inefficiency seems tiny enough to not be worth spending planner
350 : : * cycles to get rid of it.
351 : : */
352 : : void
344 353 : 6510 : add_vars_to_attr_needed(PlannerInfo *root, List *vars,
354 : : Relids where_needed)
355 : : {
356 : : ListCell *temp;
357 : :
358 [ - + ]: 6510 : Assert(!bms_is_empty(where_needed));
359 : :
360 [ + + + + : 15197 : foreach(temp, vars)
+ + ]
361 : : {
362 : 8687 : Node *node = (Node *) lfirst(temp);
363 : :
364 [ + + ]: 8687 : if (IsA(node, Var))
365 : : {
366 : 8641 : Var *var = (Var *) node;
367 : 8641 : RelOptInfo *rel = find_base_rel(root, var->varno);
368 : 8641 : int attno = var->varattno;
369 : :
370 [ + + ]: 8641 : if (bms_is_subset(where_needed, rel->relids))
371 : 428 : continue;
372 [ + - - + ]: 8213 : Assert(attno >= rel->min_attr && attno <= rel->max_attr);
373 : 8213 : attno -= rel->min_attr;
374 : 8213 : rel->attr_needed[attno] = bms_add_members(rel->attr_needed[attno],
375 : : where_needed);
376 : : }
377 [ + - ]: 46 : else if (IsA(node, PlaceHolderVar))
378 : : {
379 : 46 : PlaceHolderVar *phv = (PlaceHolderVar *) node;
380 : 46 : PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
381 : :
382 : 46 : phinfo->ph_needed = bms_add_members(phinfo->ph_needed,
383 : : where_needed);
384 : : }
385 : : else
344 tgl@sss.pgh.pa.us 386 [ # # ]:UBC 0 : elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
387 : : }
344 tgl@sss.pgh.pa.us 388 :CBC 6510 : }
389 : :
390 : : /*****************************************************************************
391 : : *
392 : : * GROUP BY
393 : : *
394 : : *****************************************************************************/
395 : :
396 : : /*
397 : : * remove_useless_groupby_columns
398 : : * Remove any columns in the GROUP BY clause that are redundant due to
399 : : * being functionally dependent on other GROUP BY columns.
400 : : *
401 : : * Since some other DBMSes do not allow references to ungrouped columns, it's
402 : : * not unusual to find all columns listed in GROUP BY even though listing the
403 : : * primary-key columns, or columns of a unique constraint would be sufficient.
404 : : * Deleting such excess columns avoids redundant sorting or hashing work, so
405 : : * it's worth doing.
406 : : *
407 : : * Relcache invalidations will ensure that cached plans become invalidated
408 : : * when the underlying supporting indexes are dropped or if a column's NOT
409 : : * NULL attribute is removed.
410 : : */
411 : : void
268 drowley@postgresql.o 412 : 159350 : remove_useless_groupby_columns(PlannerInfo *root)
413 : : {
414 : 159350 : Query *parse = root->parse;
415 : : Bitmapset **groupbyattnos;
416 : : Bitmapset **surplusvars;
417 : 159350 : bool tryremove = false;
418 : : ListCell *lc;
419 : : int relid;
420 : :
421 : : /* No chance to do anything if there are less than two GROUP BY items */
422 [ + + ]: 159350 : if (list_length(root->processed_groupClause) < 2)
423 : 158358 : return;
424 : :
425 : : /* Don't fiddle with the GROUP BY clause if the query has grouping sets */
426 [ + + ]: 992 : if (parse->groupingSets)
427 : 331 : return;
428 : :
429 : : /*
430 : : * Scan the GROUP BY clause to find GROUP BY items that are simple Vars.
431 : : * Fill groupbyattnos[k] with a bitmapset of the column attnos of RTE k
432 : : * that are GROUP BY items.
433 : : */
434 : 661 : groupbyattnos = (Bitmapset **) palloc0(sizeof(Bitmapset *) *
435 : 661 : (list_length(parse->rtable) + 1));
436 [ + - + + : 2372 : foreach(lc, root->processed_groupClause)
+ + ]
437 : : {
438 : 1711 : SortGroupClause *sgc = lfirst_node(SortGroupClause, lc);
439 : 1711 : TargetEntry *tle = get_sortgroupclause_tle(sgc, parse->targetList);
440 : 1711 : Var *var = (Var *) tle->expr;
441 : :
442 : : /*
443 : : * Ignore non-Vars and Vars from other query levels.
444 : : *
445 : : * XXX in principle, stable expressions containing Vars could also be
446 : : * removed, if all the Vars are functionally dependent on other GROUP
447 : : * BY items. But it's not clear that such cases occur often enough to
448 : : * be worth troubling over.
449 : : */
450 [ + + ]: 1711 : if (!IsA(var, Var) ||
451 [ - + ]: 1306 : var->varlevelsup > 0)
452 : 405 : continue;
453 : :
454 : : /* OK, remember we have this Var */
455 : 1306 : relid = var->varno;
456 [ - + ]: 1306 : Assert(relid <= list_length(parse->rtable));
457 : :
458 : : /*
459 : : * If this isn't the first column for this relation then we now have
460 : : * multiple columns. That means there might be some that can be
461 : : * removed.
462 : : */
463 : 1306 : tryremove |= !bms_is_empty(groupbyattnos[relid]);
464 : 1306 : groupbyattnos[relid] = bms_add_member(groupbyattnos[relid],
465 : 1306 : var->varattno - FirstLowInvalidHeapAttributeNumber);
466 : : }
467 : :
468 : : /*
469 : : * No Vars or didn't find multiple Vars for any relation in the GROUP BY?
470 : : * If so, nothing can be removed, so don't waste more effort trying.
471 : : */
472 [ + + ]: 661 : if (!tryremove)
473 : 226 : return;
474 : :
475 : : /*
476 : : * Consider each relation and see if it is possible to remove some of its
477 : : * Vars from GROUP BY. For simplicity and speed, we do the actual removal
478 : : * in a separate pass. Here, we just fill surplusvars[k] with a bitmapset
479 : : * of the column attnos of RTE k that are removable GROUP BY items.
480 : : */
481 : 435 : surplusvars = NULL; /* don't allocate array unless required */
482 : 435 : relid = 0;
483 [ + - + + : 1678 : foreach(lc, parse->rtable)
+ + ]
484 : : {
485 : 1243 : RangeTblEntry *rte = lfirst_node(RangeTblEntry, lc);
486 : : RelOptInfo *rel;
487 : : Bitmapset *relattnos;
488 : 1243 : Bitmapset *best_keycolumns = NULL;
489 : 1243 : int32 best_nkeycolumns = PG_INT32_MAX;
490 : :
491 : 1243 : relid++;
492 : :
493 : : /* Only plain relations could have primary-key constraints */
494 [ + + ]: 1243 : if (rte->rtekind != RTE_RELATION)
495 : 635 : continue;
496 : :
497 : : /*
498 : : * We must skip inheritance parent tables as some of the child rels
499 : : * may cause duplicate rows. This cannot happen with partitioned
500 : : * tables, however.
501 : : */
502 [ + + + + ]: 608 : if (rte->inh && rte->relkind != RELKIND_PARTITIONED_TABLE)
503 : 9 : continue;
504 : :
505 : : /* Nothing to do unless this rel has multiple Vars in GROUP BY */
506 : 599 : relattnos = groupbyattnos[relid];
507 [ + + ]: 599 : if (bms_membership(relattnos) != BMS_MULTIPLE)
508 : 182 : continue;
509 : :
510 : 417 : rel = root->simple_rel_array[relid];
511 : :
512 : : /*
513 : : * Now check each index for this relation to see if there are any with
514 : : * columns which are a proper subset of the grouping columns for this
515 : : * relation.
516 : : */
517 [ + + + + : 1195 : foreach_node(IndexOptInfo, index, rel->indexlist)
+ + ]
518 : : {
519 : : Bitmapset *ind_attnos;
520 : : bool nulls_check_ok;
521 : :
522 : : /*
523 : : * Skip any non-unique and deferrable indexes. Predicate indexes
524 : : * have not been checked yet, so we must skip those too as the
525 : : * predOK check that's done later might fail.
526 : : */
527 [ + + + + : 361 : if (!index->unique || !index->immediate || index->indpred != NIL)
- + ]
528 : 151 : continue;
529 : :
530 : : /* For simplicity, we currently don't support expression indexes */
531 [ - + ]: 210 : if (index->indexprs != NIL)
268 drowley@postgresql.o 532 :UBC 0 : continue;
533 : :
268 drowley@postgresql.o 534 :CBC 210 : ind_attnos = NULL;
535 : 210 : nulls_check_ok = true;
536 [ + + ]: 532 : for (int i = 0; i < index->nkeycolumns; i++)
537 : : {
538 : : /*
539 : : * We must insist that the index columns are all defined NOT
540 : : * NULL otherwise duplicate NULLs could exist. However, we
541 : : * can relax this check when the index is defined with NULLS
542 : : * NOT DISTINCT as there can only be 1 NULL row, therefore
543 : : * functional dependency on the unique columns is maintained,
544 : : * despite the NULL.
545 : : */
546 [ + + ]: 325 : if (!index->nullsnotdistinct &&
547 [ + + ]: 322 : !bms_is_member(index->indexkeys[i],
548 : 322 : rel->notnullattnums))
549 : : {
550 : 3 : nulls_check_ok = false;
551 : 3 : break;
552 : : }
553 : :
554 : : ind_attnos =
555 : 322 : bms_add_member(ind_attnos,
556 : 322 : index->indexkeys[i] -
557 : : FirstLowInvalidHeapAttributeNumber);
558 : : }
559 : :
560 [ + + ]: 210 : if (!nulls_check_ok)
561 : 3 : continue;
562 : :
563 : : /*
564 : : * Skip any indexes where the indexed columns aren't a proper
565 : : * subset of the GROUP BY.
566 : : */
567 [ + + ]: 207 : if (bms_subset_compare(ind_attnos, relattnos) != BMS_SUBSET1)
568 : 91 : continue;
569 : :
570 : : /*
571 : : * Record the attribute numbers from the index with the fewest
572 : : * columns. This allows the largest number of columns to be
573 : : * removed from the GROUP BY clause. In the future, we may wish
574 : : * to consider using the narrowest set of columns and looking at
575 : : * pg_statistic.stawidth as it might be better to use an index
576 : : * with, say two INT4s, rather than, say, one long varlena column.
577 : : */
578 [ + + ]: 116 : if (index->nkeycolumns < best_nkeycolumns)
579 : : {
580 : 107 : best_keycolumns = ind_attnos;
581 : 107 : best_nkeycolumns = index->nkeycolumns;
582 : : }
583 : : }
584 : :
585 : : /* Did we find a suitable index? */
586 [ + + ]: 417 : if (!bms_is_empty(best_keycolumns))
587 : : {
588 : : /*
589 : : * To easily remember whether we've found anything to do, we don't
590 : : * allocate the surplusvars[] array until we find something.
591 : : */
592 [ + + ]: 107 : if (surplusvars == NULL)
593 : 104 : surplusvars = (Bitmapset **) palloc0(sizeof(Bitmapset *) *
594 : 104 : (list_length(parse->rtable) + 1));
595 : :
596 : : /* Remember the attnos of the removable columns */
597 : 107 : surplusvars[relid] = bms_difference(relattnos, best_keycolumns);
598 : : }
599 : : }
600 : :
601 : : /*
602 : : * If we found any surplus Vars, build a new GROUP BY clause without them.
603 : : * (Note: this may leave some TLEs with unreferenced ressortgroupref
604 : : * markings, but that's harmless.)
605 : : */
606 [ + + ]: 435 : if (surplusvars != NULL)
607 : : {
608 : 104 : List *new_groupby = NIL;
609 : :
610 [ + - + + : 433 : foreach(lc, root->processed_groupClause)
+ + ]
611 : : {
612 : 329 : SortGroupClause *sgc = lfirst_node(SortGroupClause, lc);
613 : 329 : TargetEntry *tle = get_sortgroupclause_tle(sgc, parse->targetList);
614 : 329 : Var *var = (Var *) tle->expr;
615 : :
616 : : /*
617 : : * New list must include non-Vars, outer Vars, and anything not
618 : : * marked as surplus.
619 : : */
620 [ + - ]: 329 : if (!IsA(var, Var) ||
621 [ + - ]: 329 : var->varlevelsup > 0 ||
622 [ + + ]: 329 : !bms_is_member(var->varattno - FirstLowInvalidHeapAttributeNumber,
623 : 329 : surplusvars[var->varno]))
624 : 201 : new_groupby = lappend(new_groupby, sgc);
625 : : }
626 : :
627 : 104 : root->processed_groupClause = new_groupby;
628 : : }
629 : : }
630 : :
631 : : /*****************************************************************************
632 : : *
633 : : * LATERAL REFERENCES
634 : : *
635 : : *****************************************************************************/
636 : :
637 : : /*
638 : : * find_lateral_references
639 : : * For each LATERAL subquery, extract all its references to Vars and
640 : : * PlaceHolderVars of the current query level, and make sure those values
641 : : * will be available for evaluation of the subquery.
642 : : *
643 : : * While later planning steps ensure that the Var/PHV source rels are on the
644 : : * outside of nestloops relative to the LATERAL subquery, we also need to
645 : : * ensure that the Vars/PHVs propagate up to the nestloop join level; this
646 : : * means setting suitable where_needed values for them.
647 : : *
648 : : * Note that this only deals with lateral references in unflattened LATERAL
649 : : * subqueries. When we flatten a LATERAL subquery, its lateral references
650 : : * become plain Vars in the parent query, but they may have to be wrapped in
651 : : * PlaceHolderVars if they need to be forced NULL by outer joins that don't
652 : : * also null the LATERAL subquery. That's all handled elsewhere.
653 : : *
654 : : * This has to run before deconstruct_jointree, since it might result in
655 : : * creation of PlaceHolderInfos.
656 : : */
657 : : void
4759 tgl@sss.pgh.pa.us 658 : 159350 : find_lateral_references(PlannerInfo *root)
659 : : {
660 : : Index rti;
661 : :
662 : : /* We need do nothing if the query contains no LATERAL RTEs */
663 [ + + ]: 159350 : if (!root->hasLateralRTEs)
664 : 154338 : return;
665 : :
666 : : /*
667 : : * Examine all baserels (the rel array has been set up by now).
668 : : */
669 [ + + ]: 19185 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
670 : : {
671 : 14173 : RelOptInfo *brel = root->simple_rel_array[rti];
672 : :
673 : : /* there may be empty slots corresponding to non-baserel RTEs */
674 [ + + ]: 14173 : if (brel == NULL)
675 : 3078 : continue;
676 : :
2999 677 [ - + ]: 11095 : Assert(brel->relid == rti); /* sanity check on array */
678 : :
679 : : /*
680 : : * This bit is less obvious than it might look. We ignore appendrel
681 : : * otherrels and consider only their parent baserels. In a case where
682 : : * a LATERAL-containing UNION ALL subquery was pulled up, it is the
683 : : * otherrel that is actually going to be in the plan. However, we
684 : : * want to mark all its lateral references as needed by the parent,
685 : : * because it is the parent's relid that will be used for join
686 : : * planning purposes. And the parent's RTE will contain all the
687 : : * lateral references we need to know, since the pulled-up member is
688 : : * nothing but a copy of parts of the original RTE's subquery. We
689 : : * could visit the parent's children instead and transform their
690 : : * references back to the parent's relid, but it would be much more
691 : : * complicated for no real gain. (Important here is that the child
692 : : * members have not yet received any processing beyond being pulled
693 : : * up.) Similarly, in appendrels created by inheritance expansion,
694 : : * it's sufficient to look at the parent relation.
695 : : */
696 : :
697 : : /* ignore RTEs that are "other rels" */
4759 698 [ - + ]: 11095 : if (brel->reloptkind != RELOPT_BASEREL)
4759 tgl@sss.pgh.pa.us 699 :UBC 0 : continue;
700 : :
4759 tgl@sss.pgh.pa.us 701 :CBC 11095 : extract_lateral_references(root, brel, rti);
702 : : }
703 : : }
704 : :
705 : : static void
706 : 11095 : extract_lateral_references(PlannerInfo *root, RelOptInfo *brel, Index rtindex)
707 : : {
4778 708 : 11095 : RangeTblEntry *rte = root->simple_rte_array[rtindex];
709 : : List *vars;
710 : : List *newvars;
711 : : Relids where_needed;
712 : : ListCell *lc;
713 : :
714 : : /* No cross-references are possible if it's not LATERAL */
715 [ + + ]: 11095 : if (!rte->lateral)
716 : 6394 : return;
717 : :
718 : : /* Fetch the appropriate variables */
3696 719 [ + + ]: 4701 : if (rte->rtekind == RTE_RELATION)
720 : 18 : vars = pull_vars_of_level((Node *) rte->tablesample, 0);
721 [ + + ]: 4683 : else if (rte->rtekind == RTE_SUBQUERY)
4778 722 : 394 : vars = pull_vars_of_level((Node *) rte->subquery, 1);
723 [ + + ]: 4289 : else if (rte->rtekind == RTE_FUNCTION)
4307 724 : 4136 : vars = pull_vars_of_level((Node *) rte->functions, 0);
3104 alvherre@alvh.no-ip. 725 [ + + ]: 153 : else if (rte->rtekind == RTE_TABLEFUNC)
726 : 117 : vars = pull_vars_of_level((Node *) rte->tablefunc, 0);
4773 tgl@sss.pgh.pa.us 727 [ + - ]: 36 : else if (rte->rtekind == RTE_VALUES)
728 : 36 : vars = pull_vars_of_level((Node *) rte->values_lists, 0);
729 : : else
730 : : {
4759 tgl@sss.pgh.pa.us 731 :UBC 0 : Assert(false);
732 : : return; /* keep compiler quiet */
733 : : }
734 : :
4759 tgl@sss.pgh.pa.us 735 [ + + ]:CBC 4701 : if (vars == NIL)
736 : 50 : return; /* nothing to do */
737 : :
738 : : /* Copy each Var (or PlaceHolderVar) and adjust it to match our level */
4778 739 : 4651 : newvars = NIL;
740 [ + - + + : 9759 : foreach(lc, vars)
+ + ]
741 : : {
4483 bruce@momjian.us 742 : 5108 : Node *node = (Node *) lfirst(lc);
743 : :
4759 tgl@sss.pgh.pa.us 744 : 5108 : node = copyObject(node);
745 [ + + ]: 5108 : if (IsA(node, Var))
746 : : {
4483 bruce@momjian.us 747 : 5045 : Var *var = (Var *) node;
748 : :
749 : : /* Adjustment is easy since it's just one node */
4759 tgl@sss.pgh.pa.us 750 : 5045 : var->varlevelsup = 0;
751 : : }
752 [ + - ]: 63 : else if (IsA(node, PlaceHolderVar))
753 : : {
754 : 63 : PlaceHolderVar *phv = (PlaceHolderVar *) node;
4483 bruce@momjian.us 755 : 63 : int levelsup = phv->phlevelsup;
756 : :
757 : : /* Have to work harder to adjust the contained expression too */
4759 tgl@sss.pgh.pa.us 758 [ + + ]: 63 : if (levelsup != 0)
759 : 45 : IncrementVarSublevelsUp(node, -levelsup, 0);
760 : :
761 : : /*
762 : : * If we pulled the PHV out of a subquery RTE, its expression
763 : : * needs to be preprocessed. subquery_planner() already did this
764 : : * for level-zero PHVs in function and values RTEs, though.
765 : : */
766 [ + + ]: 63 : if (levelsup > 0)
767 : 45 : phv->phexpr = preprocess_phv_expression(root, phv->phexpr);
768 : : }
769 : : else
4767 tgl@sss.pgh.pa.us 770 :UBC 0 : Assert(false);
4759 tgl@sss.pgh.pa.us 771 :CBC 5108 : newvars = lappend(newvars, node);
772 : : }
773 : :
774 : 4651 : list_free(vars);
775 : :
776 : : /*
777 : : * We mark the Vars as being "needed" at the LATERAL RTE. This is a bit
778 : : * of a cheat: a more formal approach would be to mark each one as needed
779 : : * at the join of the LATERAL RTE with its source RTE. But it will work,
780 : : * and it's much less tedious than computing a separate where_needed for
781 : : * each Var.
782 : : */
4778 783 : 4651 : where_needed = bms_make_singleton(rtindex);
784 : :
785 : : /*
786 : : * Push Vars into their source relations' targetlists, and PHVs into
787 : : * root->placeholder_list.
788 : : */
1116 789 : 4651 : add_vars_to_targetlist(root, newvars, where_needed);
790 : :
791 : : /*
792 : : * Remember the lateral references for rebuild_lateral_attr_needed and
793 : : * create_lateral_join_info.
794 : : */
4759 795 : 4651 : brel->lateral_vars = newvars;
796 : : }
797 : :
798 : : /*
799 : : * rebuild_lateral_attr_needed
800 : : * Put back attr_needed bits for Vars/PHVs needed for lateral references.
801 : : *
802 : : * This is used to rebuild attr_needed/ph_needed sets after removal of a
803 : : * useless outer join. It should match what find_lateral_references did,
804 : : * except that we call add_vars_to_attr_needed not add_vars_to_targetlist.
805 : : */
806 : : void
344 807 : 5583 : rebuild_lateral_attr_needed(PlannerInfo *root)
808 : : {
809 : : Index rti;
810 : :
811 : : /* We need do nothing if the query contains no LATERAL RTEs */
812 [ + + ]: 5583 : if (!root->hasLateralRTEs)
813 : 5267 : return;
814 : :
815 : : /* Examine the same baserels that find_lateral_references did */
816 [ + + ]: 3281 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
817 : : {
818 : 2965 : RelOptInfo *brel = root->simple_rel_array[rti];
819 : : Relids where_needed;
820 : :
821 [ + + ]: 2965 : if (brel == NULL)
822 : 2109 : continue;
823 [ - + ]: 856 : if (brel->reloptkind != RELOPT_BASEREL)
344 tgl@sss.pgh.pa.us 824 :UBC 0 : continue;
825 : :
826 : : /*
827 : : * We don't need to repeat all of extract_lateral_references, since it
828 : : * kindly saved the extracted Vars/PHVs in lateral_vars.
829 : : */
344 tgl@sss.pgh.pa.us 830 [ + + ]:CBC 856 : if (brel->lateral_vars == NIL)
831 : 689 : continue;
832 : :
833 : 167 : where_needed = bms_make_singleton(rti);
834 : :
835 : 167 : add_vars_to_attr_needed(root, brel->lateral_vars, where_needed);
836 : : }
837 : : }
838 : :
839 : : /*
840 : : * create_lateral_join_info
841 : : * Fill in the per-base-relation direct_lateral_relids, lateral_relids
842 : : * and lateral_referencers sets.
843 : : */
844 : : void
4759 845 : 159350 : create_lateral_join_info(PlannerInfo *root)
846 : : {
3557 847 : 159350 : bool found_laterals = false;
848 : : Index rti;
849 : : ListCell *lc;
850 : :
851 : : /* We need do nothing if the query contains no LATERAL RTEs */
4759 852 [ + + ]: 159350 : if (!root->hasLateralRTEs)
853 : 154338 : return;
854 : :
855 : : /* We'll need to have the ph_eval_at values for PlaceHolderVars */
945 856 [ - + ]: 5012 : Assert(root->placeholdersFrozen);
857 : :
858 : : /*
859 : : * Examine all baserels (the rel array has been set up by now).
860 : : */
4759 861 [ + + ]: 19185 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
862 : : {
863 : 14173 : RelOptInfo *brel = root->simple_rel_array[rti];
864 : : Relids lateral_relids;
865 : :
866 : : /* there may be empty slots corresponding to non-baserel RTEs */
867 [ + + ]: 14173 : if (brel == NULL)
868 : 3394 : continue;
869 : :
2999 870 [ - + ]: 10779 : Assert(brel->relid == rti); /* sanity check on array */
871 : :
872 : : /* ignore RTEs that are "other rels" */
4759 873 [ - + ]: 10779 : if (brel->reloptkind != RELOPT_BASEREL)
4759 tgl@sss.pgh.pa.us 874 :UBC 0 : continue;
875 : :
4759 tgl@sss.pgh.pa.us 876 :CBC 10779 : lateral_relids = NULL;
877 : :
878 : : /* consider each laterally-referenced Var or PHV */
879 [ + + + + : 15803 : foreach(lc, brel->lateral_vars)
+ + ]
880 : : {
4483 bruce@momjian.us 881 : 5024 : Node *node = (Node *) lfirst(lc);
882 : :
4759 tgl@sss.pgh.pa.us 883 [ + + ]: 5024 : if (IsA(node, Var))
884 : : {
4483 bruce@momjian.us 885 : 4961 : Var *var = (Var *) node;
886 : :
3557 tgl@sss.pgh.pa.us 887 : 4961 : found_laterals = true;
4759 888 : 4961 : lateral_relids = bms_add_member(lateral_relids,
889 : : var->varno);
890 : : }
891 [ + - ]: 63 : else if (IsA(node, PlaceHolderVar))
892 : : {
893 : 63 : PlaceHolderVar *phv = (PlaceHolderVar *) node;
1116 894 : 63 : PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
895 : :
3557 896 : 63 : found_laterals = true;
4759 897 : 63 : lateral_relids = bms_add_members(lateral_relids,
898 : 63 : phinfo->ph_eval_at);
899 : : }
900 : : else
4759 tgl@sss.pgh.pa.us 901 :UBC 0 : Assert(false);
902 : : }
903 : :
904 : : /* We now have all the simple lateral refs from this rel */
3557 tgl@sss.pgh.pa.us 905 :CBC 10779 : brel->direct_lateral_relids = lateral_relids;
906 : 10779 : brel->lateral_relids = bms_copy(lateral_relids);
907 : : }
908 : :
909 : : /*
910 : : * Now check for lateral references within PlaceHolderVars, and mark their
911 : : * eval_at rels as having lateral references to the source rels.
912 : : *
913 : : * For a PHV that is due to be evaluated at a baserel, mark its source(s)
914 : : * as direct lateral dependencies of the baserel (adding onto the ones
915 : : * recorded above). If it's due to be evaluated at a join, mark its
916 : : * source(s) as indirect lateral dependencies of each baserel in the join,
917 : : * ie put them into lateral_relids but not direct_lateral_relids. This is
918 : : * appropriate because we can't put any such baserel on the outside of a
919 : : * join to one of the PHV's lateral dependencies, but on the other hand we
920 : : * also can't yet join it directly to the dependency.
921 : : */
4403 922 [ + + + + : 5303 : foreach(lc, root->placeholder_list)
+ + ]
923 : : {
924 : 291 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
925 : 291 : Relids eval_at = phinfo->ph_eval_at;
926 : : Relids lateral_refs;
927 : : int varno;
928 : :
3557 929 [ + + ]: 291 : if (phinfo->ph_lateral == NULL)
930 : 160 : continue; /* PHV is uninteresting if no lateral refs */
931 : :
932 : 131 : found_laterals = true;
933 : :
934 : : /*
935 : : * Include only baserels not outer joins in the evaluation sites'
936 : : * lateral relids. This avoids problems when outer join order gets
937 : : * rearranged, and it should still ensure that the lateral values are
938 : : * available when needed.
939 : : */
809 940 : 131 : lateral_refs = bms_intersect(phinfo->ph_lateral, root->all_baserels);
941 [ - + ]: 131 : Assert(!bms_is_empty(lateral_refs));
942 : :
3557 943 [ + + ]: 131 : if (bms_get_singleton_member(eval_at, &varno))
944 : : {
945 : : /* Evaluation site is a baserel */
946 : 98 : RelOptInfo *brel = find_base_rel(root, varno);
947 : :
948 : 98 : brel->direct_lateral_relids =
949 : 98 : bms_add_members(brel->direct_lateral_relids,
950 : : lateral_refs);
951 : 98 : brel->lateral_relids =
952 : 98 : bms_add_members(brel->lateral_relids,
953 : : lateral_refs);
954 : : }
955 : : else
956 : : {
957 : : /* Evaluation site is a join */
958 : 33 : varno = -1;
959 [ + + ]: 99 : while ((varno = bms_next_member(eval_at, varno)) >= 0)
960 : : {
950 961 : 66 : RelOptInfo *brel = find_base_rel_ignore_join(root, varno);
962 : :
963 [ - + ]: 66 : if (brel == NULL)
950 tgl@sss.pgh.pa.us 964 :UBC 0 : continue; /* ignore outer joins in eval_at */
3557 tgl@sss.pgh.pa.us 965 :CBC 66 : brel->lateral_relids = bms_add_members(brel->lateral_relids,
966 : : lateral_refs);
967 : : }
968 : : }
969 : : }
970 : :
971 : : /*
972 : : * If we found no actual lateral references, we're done; but reset the
973 : : * hasLateralRTEs flag to avoid useless work later.
974 : : */
975 [ + + ]: 5012 : if (!found_laterals)
976 : : {
977 : 359 : root->hasLateralRTEs = false;
4403 978 : 359 : return;
979 : : }
980 : :
981 : : /*
982 : : * Calculate the transitive closure of the lateral_relids sets, so that
983 : : * they describe both direct and indirect lateral references. If relation
984 : : * X references Y laterally, and Y references Z laterally, then we will
985 : : * have to scan X on the inside of a nestloop with Z, so for all intents
986 : : * and purposes X is laterally dependent on Z too.
987 : : *
988 : : * This code is essentially Warshall's algorithm for transitive closure.
989 : : * The outer loop considers each baserel, and propagates its lateral
990 : : * dependencies to those baserels that have a lateral dependency on it.
991 : : */
992 [ + + ]: 16484 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
993 : : {
994 : 11831 : RelOptInfo *brel = root->simple_rel_array[rti];
995 : : Relids outer_lateral_relids;
996 : : Index rti2;
997 : :
3557 998 [ + + - + ]: 11831 : if (brel == NULL || brel->reloptkind != RELOPT_BASEREL)
4403 999 : 1792 : continue;
1000 : :
1001 : : /* need not consider baserel further if it has no lateral refs */
3557 1002 : 10039 : outer_lateral_relids = brel->lateral_relids;
1003 [ + + ]: 10039 : if (outer_lateral_relids == NULL)
4403 1004 : 5308 : continue;
1005 : :
1006 : : /* else scan all baserels */
3557 1007 [ + + ]: 17054 : for (rti2 = 1; rti2 < root->simple_rel_array_size; rti2++)
1008 : : {
1009 : 12323 : RelOptInfo *brel2 = root->simple_rel_array[rti2];
1010 : :
1011 [ + + - + ]: 12323 : if (brel2 == NULL || brel2->reloptkind != RELOPT_BASEREL)
1012 : 1999 : continue;
1013 : :
1014 : : /* if brel2 has lateral ref to brel, propagate brel's refs */
1015 [ + + ]: 10324 : if (bms_is_member(rti, brel2->lateral_relids))
1016 : 36 : brel2->lateral_relids = bms_add_members(brel2->lateral_relids,
1017 : : outer_lateral_relids);
1018 : : }
1019 : : }
1020 : :
1021 : : /*
1022 : : * Now that we've identified all lateral references, mark each baserel
1023 : : * with the set of relids of rels that reference it laterally (possibly
1024 : : * indirectly) --- that is, the inverse mapping of lateral_relids.
1025 : : */
1026 [ + + ]: 16484 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
1027 : : {
1028 : 11831 : RelOptInfo *brel = root->simple_rel_array[rti];
1029 : : Relids lateral_relids;
1030 : : int rti2;
1031 : :
1032 [ + + - + ]: 11831 : if (brel == NULL || brel->reloptkind != RELOPT_BASEREL)
1033 : 1792 : continue;
1034 : :
1035 : : /* Nothing to do at rels with no lateral refs */
1036 : 10039 : lateral_relids = brel->lateral_relids;
919 1037 [ + + ]: 10039 : if (bms_is_empty(lateral_relids))
3557 1038 : 5308 : continue;
1039 : :
1040 : : /* No rel should have a lateral dependency on itself */
1041 [ - + ]: 4731 : Assert(!bms_is_member(rti, lateral_relids));
1042 : :
1043 : : /* Mark this rel's referencees */
1044 : 4731 : rti2 = -1;
1045 [ + + ]: 9597 : while ((rti2 = bms_next_member(lateral_relids, rti2)) >= 0)
1046 : : {
1047 : 4866 : RelOptInfo *brel2 = root->simple_rel_array[rti2];
1048 : :
950 1049 [ + + ]: 4866 : if (brel2 == NULL)
1050 : 6 : continue; /* must be an OJ */
1051 : :
1052 [ - + ]: 4860 : Assert(brel2->reloptkind == RELOPT_BASEREL);
3557 1053 : 4860 : brel2->lateral_referencers =
1054 : 4860 : bms_add_member(brel2->lateral_referencers, rti);
1055 : : }
1056 : : }
1057 : : }
1058 : :
1059 : :
1060 : : /*****************************************************************************
1061 : : *
1062 : : * JOIN TREE PROCESSING
1063 : : *
1064 : : *****************************************************************************/
1065 : :
1066 : : /*
1067 : : * deconstruct_jointree
1068 : : * Recursively scan the query's join tree for WHERE and JOIN/ON qual
1069 : : * clauses, and add these to the appropriate restrictinfo and joininfo
1070 : : * lists belonging to base RelOptInfos. Also, add SpecialJoinInfo nodes
1071 : : * to root->join_info_list for any outer joins appearing in the query tree.
1072 : : * Return a "joinlist" data structure showing the join order decisions
1073 : : * that need to be made by make_one_rel().
1074 : : *
1075 : : * The "joinlist" result is a list of items that are either RangeTblRef
1076 : : * jointree nodes or sub-joinlists. All the items at the same level of
1077 : : * joinlist must be joined in an order to be determined by make_one_rel()
1078 : : * (note that legal orders may be constrained by SpecialJoinInfo nodes).
1079 : : * A sub-joinlist represents a subproblem to be planned separately. Currently
1080 : : * sub-joinlists arise only from FULL OUTER JOIN or when collapsing of
1081 : : * subproblems is stopped by join_collapse_limit or from_collapse_limit.
1082 : : */
1083 : : List *
7200 1084 : 159350 : deconstruct_jointree(PlannerInfo *root)
1085 : : {
1086 : : List *result;
1087 : : JoinDomain *top_jdomain;
950 1088 : 159350 : List *item_list = NIL;
1089 : : ListCell *lc;
1090 : :
1091 : : /*
1092 : : * After this point, no more PlaceHolderInfos may be made, because
1093 : : * make_outerjoininfo requires all active placeholders to be present in
1094 : : * root->placeholder_list while we crawl up the join tree.
1095 : : */
1116 1096 : 159350 : root->placeholdersFrozen = true;
1097 : :
1098 : : /* Fetch the already-created top-level join domain for the query */
950 1099 : 159350 : top_jdomain = linitial_node(JoinDomain, root->join_domains);
1100 : 159350 : top_jdomain->jd_relids = NULL; /* filled during deconstruct_recurse */
1101 : :
1102 : : /* Start recursion at top of jointree */
7200 1103 [ + - - + ]: 159350 : Assert(root->parse->jointree != NULL &&
1104 : : IsA(root->parse->jointree, FromExpr));
1105 : :
1106 : : /* These are filled as we scan the jointree */
950 1107 : 159350 : root->all_baserels = NULL;
1108 : 159350 : root->outer_join_rels = NULL;
1109 : :
1110 : : /* Perform the initial scan of the jointree */
1111 : 159350 : result = deconstruct_recurse(root, (Node *) root->parse->jointree,
1112 : : top_jdomain, NULL,
1113 : : &item_list);
1114 : :
1115 : : /* Now we can form the value of all_query_rels, too */
1116 : 159350 : root->all_query_rels = bms_union(root->all_baserels, root->outer_join_rels);
1117 : :
1118 : : /* ... which should match what we computed for the top join domain */
1119 [ - + ]: 159350 : Assert(bms_equal(root->all_query_rels, top_jdomain->jd_relids));
1120 : :
1121 : : /* Now scan all the jointree nodes again, and distribute quals */
1122 [ + - + + : 600927 : foreach(lc, item_list)
+ + ]
1123 : : {
1124 : 441577 : JoinTreeItem *jtitem = (JoinTreeItem *) lfirst(lc);
1125 : :
945 1126 : 441577 : deconstruct_distribute(root, jtitem);
1127 : : }
1128 : :
1129 : : /*
1130 : : * If there were any special joins then we may have some postponed LEFT
1131 : : * JOIN clauses to deal with.
1132 : : */
950 1133 [ + + ]: 159350 : if (root->join_info_list)
1134 : : {
1135 [ + - + + : 127481 : foreach(lc, item_list)
+ + ]
1136 : : {
1137 : 108139 : JoinTreeItem *jtitem = (JoinTreeItem *) lfirst(lc);
1138 : :
1139 [ + + ]: 108139 : if (jtitem->oj_joinclauses != NIL)
1140 : 20835 : deconstruct_distribute_oj_quals(root, item_list, jtitem);
1141 : : }
1142 : : }
1143 : :
1144 : : /* Don't need the JoinTreeItems any more */
1145 : 159350 : list_free_deep(item_list);
1146 : :
4401 1147 : 159350 : return result;
1148 : : }
1149 : :
1150 : : /*
1151 : : * deconstruct_recurse
1152 : : * One recursion level of deconstruct_jointree's initial jointree scan.
1153 : : *
1154 : : * jtnode is the jointree node to examine, and parent_domain is the
1155 : : * enclosing join domain. (We must add all base+OJ relids appearing
1156 : : * here or below to parent_domain.) parent_jtitem is the JoinTreeItem
1157 : : * for the parent jointree node, or NULL at the top of the recursion.
1158 : : *
1159 : : * item_list is an in/out parameter: we add a JoinTreeItem struct to
1160 : : * that list for each jointree node, in depth-first traversal order.
1161 : : * (Hence, after each call, the last list item corresponds to its jtnode.)
1162 : : *
1163 : : * Return value is the appropriate joinlist for this jointree node.
1164 : : */
1165 : : static List *
950 1166 : 441577 : deconstruct_recurse(PlannerInfo *root, Node *jtnode,
1167 : : JoinDomain *parent_domain,
1168 : : JoinTreeItem *parent_jtitem,
1169 : : List **item_list)
1170 : : {
1171 : : List *joinlist;
1172 : : JoinTreeItem *jtitem;
1173 : :
1174 [ - + ]: 441577 : Assert(jtnode != NULL);
1175 : :
1176 : : /* Make the new JoinTreeItem, but don't add it to item_list yet */
1177 : 441577 : jtitem = palloc0_object(JoinTreeItem);
1178 : 441577 : jtitem->jtnode = jtnode;
945 1179 : 441577 : jtitem->jti_parent = parent_jtitem;
1180 : :
9108 1181 [ + + ]: 441577 : if (IsA(jtnode, RangeTblRef))
1182 : : {
1183 : 230116 : int varno = ((RangeTblRef *) jtnode)->rtindex;
1184 : :
1185 : : /* Fill all_baserels as we encounter baserel jointree nodes */
950 1186 : 230116 : root->all_baserels = bms_add_member(root->all_baserels, varno);
1187 : : /* This node belongs to parent_domain */
1188 : 230116 : jtitem->jdomain = parent_domain;
1189 : 230116 : parent_domain->jd_relids = bms_add_member(parent_domain->jd_relids,
1190 : : varno);
1191 : : /* qualscope is just the one RTE */
1192 : 230116 : jtitem->qualscope = bms_make_singleton(varno);
1193 : : /* A single baserel does not create an inner join */
1194 : 230116 : jtitem->inner_join_rels = NULL;
7200 1195 : 230116 : joinlist = list_make1(jtnode);
1196 : : }
9108 1197 [ + + ]: 211461 : else if (IsA(jtnode, FromExpr))
1198 : : {
1199 : 165510 : FromExpr *f = (FromExpr *) jtnode;
1200 : : int remaining;
1201 : : ListCell *l;
1202 : :
1203 : : /* This node belongs to parent_domain, as do its children */
950 1204 : 165510 : jtitem->jdomain = parent_domain;
1205 : :
1206 : : /*
1207 : : * Recurse to handle child nodes, and compute output joinlist. We
1208 : : * collapse subproblems into a single joinlist whenever the resulting
1209 : : * joinlist wouldn't exceed from_collapse_limit members. Also, always
1210 : : * collapse one-element subproblems, since that won't lengthen the
1211 : : * joinlist anyway.
1212 : : */
1213 : 165510 : jtitem->qualscope = NULL;
1214 : 165510 : jtitem->inner_join_rels = NULL;
7200 1215 : 165510 : joinlist = NIL;
1216 : 165510 : remaining = list_length(f->fromlist);
9108 1217 [ + - + + : 355835 : foreach(l, f->fromlist)
+ + ]
1218 : : {
1219 : : JoinTreeItem *sub_item;
1220 : : List *sub_joinlist;
1221 : : int sub_members;
1222 : :
7200 1223 : 190325 : sub_joinlist = deconstruct_recurse(root, lfirst(l),
1224 : : parent_domain,
1225 : : jtitem,
1226 : : item_list);
950 1227 : 190325 : sub_item = (JoinTreeItem *) llast(*item_list);
1228 : 380650 : jtitem->qualscope = bms_add_members(jtitem->qualscope,
1229 : 190325 : sub_item->qualscope);
1230 : 190325 : jtitem->inner_join_rels = sub_item->inner_join_rels;
7200 1231 : 190325 : sub_members = list_length(sub_joinlist);
1232 : 190325 : remaining--;
1233 [ + + ]: 190325 : if (sub_members <= 1 ||
1234 [ + + ]: 29343 : list_length(joinlist) + sub_members + remaining <= from_collapse_limit)
1235 : 190319 : joinlist = list_concat(joinlist, sub_joinlist);
1236 : : else
1237 : 6 : joinlist = lappend(joinlist, sub_joinlist);
1238 : : }
1239 : :
1240 : : /*
1241 : : * A FROM with more than one list element is an inner join subsuming
1242 : : * all below it, so we should report inner_join_rels = qualscope. If
1243 : : * there was exactly one element, we should (and already did) report
1244 : : * whatever its inner_join_rels were. If there were no elements (is
1245 : : * that still possible?) the initialization before the loop fixed it.
1246 : : */
6581 1247 [ + + ]: 165510 : if (list_length(f->fromlist) > 1)
950 1248 : 22502 : jtitem->inner_join_rels = jtitem->qualscope;
1249 : : }
9125 1250 [ + - ]: 45951 : else if (IsA(jtnode, JoinExpr))
1251 : : {
1252 : 45951 : JoinExpr *j = (JoinExpr *) jtnode;
1253 : : JoinDomain *child_domain,
1254 : : *fj_domain;
1255 : : JoinTreeItem *left_item,
1256 : : *right_item;
1257 : : List *leftjoinlist,
1258 : : *rightjoinlist;
1259 : :
1260 [ + + + + : 45951 : switch (j->jointype)
- ]
1261 : : {
1262 : 19345 : case JOIN_INNER:
1263 : : /* This node belongs to parent_domain, as do its children */
950 1264 : 19345 : jtitem->jdomain = parent_domain;
1265 : : /* Recurse */
7200 1266 : 19345 : leftjoinlist = deconstruct_recurse(root, j->larg,
1267 : : parent_domain,
1268 : : jtitem,
1269 : : item_list);
950 1270 : 19345 : left_item = (JoinTreeItem *) llast(*item_list);
7200 1271 : 19345 : rightjoinlist = deconstruct_recurse(root, j->rarg,
1272 : : parent_domain,
1273 : : jtitem,
1274 : : item_list);
950 1275 : 19345 : right_item = (JoinTreeItem *) llast(*item_list);
1276 : : /* Compute qualscope etc */
1277 : 38690 : jtitem->qualscope = bms_union(left_item->qualscope,
1278 : 19345 : right_item->qualscope);
1279 : 19345 : jtitem->inner_join_rels = jtitem->qualscope;
1280 : 19345 : jtitem->left_rels = left_item->qualscope;
1281 : 19345 : jtitem->right_rels = right_item->qualscope;
1282 : : /* Inner join adds no restrictions for quals */
1283 : 19345 : jtitem->nonnullable_rels = NULL;
9125 1284 : 19345 : break;
1285 : 23620 : case JOIN_LEFT:
1286 : : case JOIN_ANTI:
1287 : : /* Make new join domain for my quals and the RHS */
950 1288 : 23620 : child_domain = makeNode(JoinDomain);
1289 : 23620 : child_domain->jd_relids = NULL; /* filled by recursion */
1290 : 23620 : root->join_domains = lappend(root->join_domains, child_domain);
1291 : 23620 : jtitem->jdomain = child_domain;
1292 : : /* Recurse */
7200 1293 : 23620 : leftjoinlist = deconstruct_recurse(root, j->larg,
1294 : : parent_domain,
1295 : : jtitem,
1296 : : item_list);
950 1297 : 23620 : left_item = (JoinTreeItem *) llast(*item_list);
7200 1298 : 23620 : rightjoinlist = deconstruct_recurse(root, j->rarg,
1299 : : child_domain,
1300 : : jtitem,
1301 : : item_list);
950 1302 : 23620 : right_item = (JoinTreeItem *) llast(*item_list);
1303 : : /* Compute join domain contents, qualscope etc */
1304 : 23620 : parent_domain->jd_relids =
1305 : 23620 : bms_add_members(parent_domain->jd_relids,
1306 : 23620 : child_domain->jd_relids);
1307 : 47240 : jtitem->qualscope = bms_union(left_item->qualscope,
1308 : 23620 : right_item->qualscope);
1309 : : /* caution: ANTI join derived from SEMI will lack rtindex */
1310 [ + + ]: 23620 : if (j->rtindex != 0)
1311 : : {
1312 : 22251 : parent_domain->jd_relids =
1313 : 22251 : bms_add_member(parent_domain->jd_relids,
1314 : : j->rtindex);
1315 : 22251 : jtitem->qualscope = bms_add_member(jtitem->qualscope,
1316 : : j->rtindex);
1317 : 22251 : root->outer_join_rels = bms_add_member(root->outer_join_rels,
1318 : : j->rtindex);
1319 : 22251 : mark_rels_nulled_by_join(root, j->rtindex,
1320 : : right_item->qualscope);
1321 : : }
1322 : 47240 : jtitem->inner_join_rels = bms_union(left_item->inner_join_rels,
1323 : 23620 : right_item->inner_join_rels);
1324 : 23620 : jtitem->left_rels = left_item->qualscope;
1325 : 23620 : jtitem->right_rels = right_item->qualscope;
1326 : 23620 : jtitem->nonnullable_rels = left_item->qualscope;
9125 1327 : 23620 : break;
6037 1328 : 2472 : case JOIN_SEMI:
1329 : : /* This node belongs to parent_domain, as do its children */
950 1330 : 2472 : jtitem->jdomain = parent_domain;
1331 : : /* Recurse */
6037 1332 : 2472 : leftjoinlist = deconstruct_recurse(root, j->larg,
1333 : : parent_domain,
1334 : : jtitem,
1335 : : item_list);
950 1336 : 2472 : left_item = (JoinTreeItem *) llast(*item_list);
6037 1337 : 2472 : rightjoinlist = deconstruct_recurse(root, j->rarg,
1338 : : parent_domain,
1339 : : jtitem,
1340 : : item_list);
950 1341 : 2472 : right_item = (JoinTreeItem *) llast(*item_list);
1342 : : /* Compute qualscope etc */
1343 : 4944 : jtitem->qualscope = bms_union(left_item->qualscope,
1344 : 2472 : right_item->qualscope);
1345 : : /* SEMI join never has rtindex, so don't add to anything */
1346 [ - + ]: 2472 : Assert(j->rtindex == 0);
1347 : 4944 : jtitem->inner_join_rels = bms_union(left_item->inner_join_rels,
1348 : 2472 : right_item->inner_join_rels);
1349 : 2472 : jtitem->left_rels = left_item->qualscope;
1350 : 2472 : jtitem->right_rels = right_item->qualscope;
1351 : : /* Semi join adds no restrictions for quals */
1352 : 2472 : jtitem->nonnullable_rels = NULL;
6037 1353 : 2472 : break;
9125 1354 : 514 : case JOIN_FULL:
1355 : : /* The FULL JOIN's quals need their very own domain */
950 1356 : 514 : fj_domain = makeNode(JoinDomain);
1357 : 514 : root->join_domains = lappend(root->join_domains, fj_domain);
1358 : 514 : jtitem->jdomain = fj_domain;
1359 : : /* Recurse, giving each side its own join domain */
1360 : 514 : child_domain = makeNode(JoinDomain);
1361 : 514 : child_domain->jd_relids = NULL; /* filled by recursion */
1362 : 514 : root->join_domains = lappend(root->join_domains, child_domain);
7200 1363 : 514 : leftjoinlist = deconstruct_recurse(root, j->larg,
1364 : : child_domain,
1365 : : jtitem,
1366 : : item_list);
950 1367 : 514 : left_item = (JoinTreeItem *) llast(*item_list);
1368 : 514 : fj_domain->jd_relids = bms_copy(child_domain->jd_relids);
1369 : 514 : child_domain = makeNode(JoinDomain);
1370 : 514 : child_domain->jd_relids = NULL; /* filled by recursion */
1371 : 514 : root->join_domains = lappend(root->join_domains, child_domain);
7200 1372 : 514 : rightjoinlist = deconstruct_recurse(root, j->rarg,
1373 : : child_domain,
1374 : : jtitem,
1375 : : item_list);
950 1376 : 514 : right_item = (JoinTreeItem *) llast(*item_list);
1377 : : /* Compute qualscope etc */
1378 : 1028 : fj_domain->jd_relids = bms_add_members(fj_domain->jd_relids,
1379 : 514 : child_domain->jd_relids);
1380 : 1028 : parent_domain->jd_relids = bms_add_members(parent_domain->jd_relids,
1381 : 514 : fj_domain->jd_relids);
1382 : 1028 : jtitem->qualscope = bms_union(left_item->qualscope,
1383 : 514 : right_item->qualscope);
1384 [ - + ]: 514 : Assert(j->rtindex != 0);
1385 : 514 : parent_domain->jd_relids = bms_add_member(parent_domain->jd_relids,
1386 : : j->rtindex);
1387 : 514 : jtitem->qualscope = bms_add_member(jtitem->qualscope,
1388 : : j->rtindex);
1389 : 514 : root->outer_join_rels = bms_add_member(root->outer_join_rels,
1390 : : j->rtindex);
1391 : 514 : mark_rels_nulled_by_join(root, j->rtindex,
1392 : : left_item->qualscope);
1393 : 514 : mark_rels_nulled_by_join(root, j->rtindex,
1394 : : right_item->qualscope);
1395 : 1028 : jtitem->inner_join_rels = bms_union(left_item->inner_join_rels,
1396 : 514 : right_item->inner_join_rels);
1397 : 514 : jtitem->left_rels = left_item->qualscope;
1398 : 514 : jtitem->right_rels = right_item->qualscope;
1399 : : /* each side is both outer and inner */
1400 : 514 : jtitem->nonnullable_rels = jtitem->qualscope;
9125 1401 : 514 : break;
9125 tgl@sss.pgh.pa.us 1402 :UBC 0 : default:
1403 : : /* JOIN_RIGHT was eliminated during reduce_outer_joins() */
8079 1404 [ # # ]: 0 : elog(ERROR, "unrecognized join type: %d",
1405 : : (int) j->jointype);
1406 : : leftjoinlist = rightjoinlist = NIL; /* keep compiler quiet */
1407 : : break;
1408 : : }
1409 : :
1410 : : /*
1411 : : * Compute the output joinlist. We fold subproblems together except
1412 : : * at a FULL JOIN or where join_collapse_limit would be exceeded.
1413 : : */
950 tgl@sss.pgh.pa.us 1414 [ + + ]:CBC 45951 : if (j->jointype == JOIN_FULL)
1415 : : {
1416 : : /* force the join order exactly at this node */
1417 : 514 : joinlist = list_make1(list_make2(leftjoinlist, rightjoinlist));
1418 : : }
1419 [ + + ]: 45437 : else if (list_length(leftjoinlist) + list_length(rightjoinlist) <=
1420 : : join_collapse_limit)
1421 : : {
1422 : : /* OK to combine subproblems */
1423 : 45353 : joinlist = list_concat(leftjoinlist, rightjoinlist);
1424 : : }
1425 : : else
1426 : : {
1427 : : /* can't combine, but needn't force join order above here */
1428 : : Node *leftpart,
1429 : : *rightpart;
1430 : :
1431 : : /* avoid creating useless 1-element sublists */
1432 [ + + ]: 84 : if (list_length(leftjoinlist) == 1)
1433 : 15 : leftpart = (Node *) linitial(leftjoinlist);
1434 : : else
1435 : 69 : leftpart = (Node *) leftjoinlist;
1436 [ + + ]: 84 : if (list_length(rightjoinlist) == 1)
1437 : 12 : rightpart = (Node *) linitial(rightjoinlist);
1438 : : else
1439 : 72 : rightpart = (Node *) rightjoinlist;
1440 : 84 : joinlist = list_make2(leftpart, rightpart);
1441 : : }
1442 : : }
1443 : : else
1444 : : {
950 tgl@sss.pgh.pa.us 1445 [ # # ]:UBC 0 : elog(ERROR, "unrecognized node type: %d",
1446 : : (int) nodeTag(jtnode));
1447 : : joinlist = NIL; /* keep compiler quiet */
1448 : : }
1449 : :
1450 : : /* Finally, we can add the new JoinTreeItem to item_list */
950 tgl@sss.pgh.pa.us 1451 :CBC 441577 : *item_list = lappend(*item_list, jtitem);
1452 : :
1453 : 441577 : return joinlist;
1454 : : }
1455 : :
1456 : : /*
1457 : : * deconstruct_distribute
1458 : : * Process one jointree node in phase 2 of deconstruct_jointree processing.
1459 : : *
1460 : : * Distribute quals of the node to appropriate restriction and join lists.
1461 : : * In addition, entries will be added to root->join_info_list for outer joins.
1462 : : */
1463 : : static void
945 1464 : 441577 : deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem)
1465 : : {
950 1466 : 441577 : Node *jtnode = jtitem->jtnode;
1467 : :
1468 [ + + ]: 441577 : if (IsA(jtnode, RangeTblRef))
1469 : : {
1470 : 230116 : int varno = ((RangeTblRef *) jtnode)->rtindex;
1471 : :
1472 : : /* Deal with any securityQuals attached to the RTE */
1473 [ + + ]: 230116 : if (root->qual_security_level > 0)
1474 : 1404 : process_security_barrier_quals(root,
1475 : : varno,
1476 : : jtitem);
1477 : : }
1478 [ + + ]: 211461 : else if (IsA(jtnode, FromExpr))
1479 : : {
1480 : 165510 : FromExpr *f = (FromExpr *) jtnode;
1481 : :
1482 : : /*
1483 : : * Process any lateral-referencing quals that were postponed to this
1484 : : * level by children.
1485 : : */
945 1486 : 165510 : distribute_quals_to_rels(root, jtitem->lateral_clauses,
1487 : : jtitem,
1488 : : NULL,
1489 : : root->qual_security_level,
1490 : : jtitem->qualscope,
1491 : : NULL, NULL, NULL,
1492 : : true, false, false,
1493 : : NULL);
1494 : :
1495 : : /*
1496 : : * Now process the top-level quals.
1497 : : */
950 1498 : 165510 : distribute_quals_to_rels(root, (List *) f->quals,
1499 : : jtitem,
1500 : : NULL,
1501 : : root->qual_security_level,
1502 : : jtitem->qualscope,
1503 : : NULL, NULL, NULL,
1504 : : true, false, false,
1505 : : NULL);
1506 : : }
1507 [ + - ]: 45951 : else if (IsA(jtnode, JoinExpr))
1508 : : {
1509 : 45951 : JoinExpr *j = (JoinExpr *) jtnode;
1510 : : Relids ojscope;
1511 : : List *my_quals;
1512 : : SpecialJoinInfo *sjinfo;
1513 : : List **postponed_oj_qual_list;
1514 : :
1515 : : /*
1516 : : * Include lateral-referencing quals postponed from children in
1517 : : * my_quals, so that they'll be handled properly in
1518 : : * make_outerjoininfo. (This is destructive to
1519 : : * jtitem->lateral_clauses, but we won't use that again.)
1520 : : */
945 1521 : 45951 : my_quals = list_concat(jtitem->lateral_clauses,
1522 : 45951 : (List *) j->quals);
1523 : :
1524 : : /*
1525 : : * For an OJ, form the SpecialJoinInfo now, so that we can pass it to
1526 : : * distribute_qual_to_rels. We must compute its ojscope too.
1527 : : *
1528 : : * Semijoins are a bit of a hybrid: we build a SpecialJoinInfo, but we
1529 : : * want ojscope = NULL for distribute_qual_to_rels.
1530 : : */
7200 1531 [ + + ]: 45951 : if (j->jointype != JOIN_INNER)
1532 : : {
6232 1533 : 26606 : sjinfo = make_outerjoininfo(root,
1534 : : jtitem->left_rels,
1535 : : jtitem->right_rels,
1536 : : jtitem->inner_join_rels,
1537 : : j->jointype,
950 1538 : 26606 : j->rtindex,
1539 : : my_quals);
1540 : 26606 : jtitem->sjinfo = sjinfo;
6037 1541 [ + + ]: 26606 : if (j->jointype == JOIN_SEMI)
1542 : 2472 : ojscope = NULL;
1543 : : else
1544 : 24134 : ojscope = bms_union(sjinfo->min_lefthand,
1545 : 24134 : sjinfo->min_righthand);
1546 : : }
1547 : : else
1548 : : {
6232 1549 : 19345 : sjinfo = NULL;
7200 1550 : 19345 : ojscope = NULL;
1551 : : }
1552 : :
1553 : : /*
1554 : : * If it's a left join with a join clause that is strict for the LHS,
1555 : : * then we need to postpone handling of any non-degenerate join
1556 : : * clauses, in case the join is able to commute with another left join
1557 : : * per identity 3. (Degenerate clauses need not be postponed, since
1558 : : * they will drop down below this join anyway.)
1559 : : */
950 1560 [ + + + + ]: 45951 : if (j->jointype == JOIN_LEFT && sjinfo->lhs_strict)
1561 : : {
1562 : 20835 : postponed_oj_qual_list = &jtitem->oj_joinclauses;
1563 : :
1564 : : /*
1565 : : * Add back any commutable lower OJ relids that were removed from
1566 : : * min_lefthand or min_righthand, else the ojscope cross-check in
1567 : : * distribute_qual_to_rels will complain. Since we are postponing
1568 : : * processing of non-degenerate clauses, this addition doesn't
1569 : : * affect anything except that cross-check. Real clause
1570 : : * positioning decisions will be made later, when we revisit the
1571 : : * postponed clauses.
1572 : : */
843 1573 : 20835 : ojscope = bms_add_members(ojscope, sjinfo->commute_below_l);
1574 : 20835 : ojscope = bms_add_members(ojscope, sjinfo->commute_below_r);
1575 : : }
1576 : : else
950 1577 : 25116 : postponed_oj_qual_list = NULL;
1578 : :
1579 : : /* Process the JOIN's qual clauses */
1580 : 45951 : distribute_quals_to_rels(root, my_quals,
1581 : : jtitem,
1582 : : sjinfo,
1583 : : root->qual_security_level,
1584 : : jtitem->qualscope,
1585 : : ojscope, jtitem->nonnullable_rels,
1586 : : NULL, /* incompatible_relids */
1587 : : true, /* allow_equivalence */
1588 : : false, false, /* not clones */
1589 : : postponed_oj_qual_list);
1590 : :
1591 : : /* And add the SpecialJoinInfo to join_info_list */
6232 1592 [ + + ]: 45951 : if (sjinfo)
1593 : 26606 : root->join_info_list = lappend(root->join_info_list, sjinfo);
1594 : : }
1595 : : else
1596 : : {
8079 tgl@sss.pgh.pa.us 1597 [ # # ]:UBC 0 : elog(ERROR, "unrecognized node type: %d",
1598 : : (int) nodeTag(jtnode));
1599 : : }
9125 tgl@sss.pgh.pa.us 1600 :CBC 441577 : }
1601 : :
1602 : : /*
1603 : : * process_security_barrier_quals
1604 : : * Transfer security-barrier quals into relation's baserestrictinfo list.
1605 : : *
1606 : : * The rewriter put any relevant security-barrier conditions into the RTE's
1607 : : * securityQuals field, but it's now time to copy them into the rel's
1608 : : * baserestrictinfo.
1609 : : *
1610 : : * In inheritance cases, we only consider quals attached to the parent rel
1611 : : * here; they will be valid for all children too, so it's okay to consider
1612 : : * them for purposes like equivalence class creation. Quals attached to
1613 : : * individual child rels will be dealt with during path creation.
1614 : : */
1615 : : static void
3153 1616 : 1404 : process_security_barrier_quals(PlannerInfo *root,
1617 : : int rti, JoinTreeItem *jtitem)
1618 : : {
1619 : 1404 : RangeTblEntry *rte = root->simple_rte_array[rti];
1620 : 1404 : Index security_level = 0;
1621 : : ListCell *lc;
1622 : :
1623 : : /*
1624 : : * Each element of the securityQuals list has been preprocessed into an
1625 : : * implicitly-ANDed list of clauses. All the clauses in a given sublist
1626 : : * should get the same security level, but successive sublists get higher
1627 : : * levels.
1628 : : */
1629 [ + + + + : 2852 : foreach(lc, rte->securityQuals)
+ + ]
1630 : : {
1631 : 1448 : List *qualset = (List *) lfirst(lc);
1632 : :
1633 : : /*
1634 : : * We cheat to the extent of passing ojscope = qualscope rather than
1635 : : * its more logical value of NULL. The only effect this has is to
1636 : : * force a Var-free qual to be evaluated at the rel rather than being
1637 : : * pushed up to top of tree, which we don't want.
1638 : : */
950 1639 : 1448 : distribute_quals_to_rels(root, qualset,
1640 : : jtitem,
1641 : : NULL,
1642 : : security_level,
1643 : : jtitem->qualscope,
1644 : : jtitem->qualscope,
1645 : : NULL,
1646 : : NULL,
1647 : : true,
1648 : : false, false, /* not clones */
1649 : : NULL);
3153 1650 : 1448 : security_level++;
1651 : : }
1652 : :
1653 : : /* Assert that qual_security_level is higher than anything we just used */
1654 [ - + ]: 1404 : Assert(security_level <= root->qual_security_level);
1655 : 1404 : }
1656 : :
1657 : : /*
1658 : : * mark_rels_nulled_by_join
1659 : : * Fill RelOptInfo.nulling_relids of baserels nulled by this outer join
1660 : : *
1661 : : * Inputs:
1662 : : * ojrelid: RT index of the join RTE (must not be 0)
1663 : : * lower_rels: the base+OJ Relids syntactically below nullable side of join
1664 : : */
1665 : : static void
950 1666 : 23279 : mark_rels_nulled_by_join(PlannerInfo *root, Index ojrelid,
1667 : : Relids lower_rels)
1668 : : {
1669 : 23279 : int relid = -1;
1670 : :
1671 [ + + ]: 47933 : while ((relid = bms_next_member(lower_rels, relid)) > 0)
1672 : : {
1673 : 24654 : RelOptInfo *rel = root->simple_rel_array[relid];
1674 : :
1675 : : /* ignore the RTE_GROUP RTE */
361 rguo@postgresql.org 1676 [ - + ]: 24654 : if (relid == root->group_rtindex)
361 rguo@postgresql.org 1677 :UBC 0 : continue;
1678 : :
950 tgl@sss.pgh.pa.us 1679 [ + + ]:CBC 24654 : if (rel == NULL) /* must be an outer join */
1680 : : {
1681 [ - + ]: 385 : Assert(bms_is_member(relid, root->outer_join_rels));
1682 : 385 : continue;
1683 : : }
1684 : 24269 : rel->nulling_relids = bms_add_member(rel->nulling_relids, ojrelid);
1685 : : }
1686 : 23279 : }
1687 : :
1688 : : /*
1689 : : * make_outerjoininfo
1690 : : * Build a SpecialJoinInfo for the current outer join
1691 : : *
1692 : : * Inputs:
1693 : : * left_rels: the base+OJ Relids syntactically on outer side of join
1694 : : * right_rels: the base+OJ Relids syntactically on inner side of join
1695 : : * inner_join_rels: base+OJ Relids participating in inner joins below this one
1696 : : * jointype: what it says (must always be LEFT, FULL, SEMI, or ANTI)
1697 : : * ojrelid: RT index of the join RTE (0 for SEMI, which isn't in the RT list)
1698 : : * clause: the outer join's join condition (in implicit-AND format)
1699 : : *
1700 : : * The node should eventually be appended to root->join_info_list, but we
1701 : : * do not do that here.
1702 : : *
1703 : : * Note: we assume that this function is invoked bottom-up, so that
1704 : : * root->join_info_list already contains entries for all outer joins that are
1705 : : * syntactically below this one.
1706 : : */
1707 : : static SpecialJoinInfo *
7200 1708 : 26606 : make_outerjoininfo(PlannerInfo *root,
1709 : : Relids left_rels, Relids right_rels,
1710 : : Relids inner_join_rels,
1711 : : JoinType jointype, Index ojrelid,
1712 : : List *clause)
1713 : : {
6232 1714 : 26606 : SpecialJoinInfo *sjinfo = makeNode(SpecialJoinInfo);
1715 : : Relids clause_relids;
1716 : : Relids strict_relids;
1717 : : Relids min_lefthand;
1718 : : Relids min_righthand;
1719 : : Relids commute_below_l;
1720 : : Relids commute_below_r;
1721 : : ListCell *l;
1722 : :
1723 : : /*
1724 : : * We should not see RIGHT JOIN here because left/right were switched
1725 : : * earlier
1726 : : */
1727 [ - + ]: 26606 : Assert(jointype != JOIN_INNER);
1728 [ - + ]: 26606 : Assert(jointype != JOIN_RIGHT);
1729 : :
1730 : : /*
1731 : : * Presently the executor cannot support FOR [KEY] UPDATE/SHARE marking of
1732 : : * rels appearing on the nullable side of an outer join. (It's somewhat
1733 : : * unclear what that would mean, anyway: what should we mark when a result
1734 : : * row is generated from no element of the nullable relation?) So,
1735 : : * complain if any nullable rel is FOR [KEY] UPDATE/SHARE.
1736 : : *
1737 : : * You might be wondering why this test isn't made far upstream in the
1738 : : * parser. It's because the parser hasn't got enough info --- consider
1739 : : * FOR UPDATE applied to a view. Only after rewriting and flattening do
1740 : : * we know whether the view contains an outer join.
1741 : : *
1742 : : * We use the original RowMarkClause list here; the PlanRowMark list would
1743 : : * list everything.
1744 : : */
6938 1745 [ + + + + : 26628 : foreach(l, root->parse->rowMarks)
+ + ]
1746 : : {
1747 : 22 : RowMarkClause *rc = (RowMarkClause *) lfirst(l);
1748 : :
1749 [ + - + + ]: 22 : if (bms_is_member(rc->rti, right_rels) ||
6232 1750 [ - + ]: 4 : (jointype == JOIN_FULL && bms_is_member(rc->rti, left_rels)))
6938 tgl@sss.pgh.pa.us 1751 [ # # ]:UBC 0 : ereport(ERROR,
1752 : : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1753 : : /*------
1754 : : translator: %s is a SQL row locking clause such as FOR UPDATE */
1755 : : errmsg("%s cannot be applied to the nullable side of an outer join",
1756 : : LCS_asString(rc->strength))));
1757 : : }
1758 : :
6232 tgl@sss.pgh.pa.us 1759 :CBC 26606 : sjinfo->syn_lefthand = left_rels;
1760 : 26606 : sjinfo->syn_righthand = right_rels;
1761 : 26606 : sjinfo->jointype = jointype;
950 1762 : 26606 : sjinfo->ojrelid = ojrelid;
1763 : : /* these fields may get added to later: */
1764 : 26606 : sjinfo->commute_above_l = NULL;
1765 : 26606 : sjinfo->commute_above_r = NULL;
843 1766 : 26606 : sjinfo->commute_below_l = NULL;
1767 : 26606 : sjinfo->commute_below_r = NULL;
1768 : :
1689 1769 : 26606 : compute_semijoin_info(root, sjinfo, clause);
1770 : :
1771 : : /* If it's a full join, no need to be very smart */
6232 1772 [ + + ]: 26606 : if (jointype == JOIN_FULL)
1773 : : {
1774 : 514 : sjinfo->min_lefthand = bms_copy(left_rels);
1775 : 514 : sjinfo->min_righthand = bms_copy(right_rels);
2999 1776 : 514 : sjinfo->lhs_strict = false; /* don't care about this */
6232 1777 : 514 : return sjinfo;
1778 : : }
1779 : :
1780 : : /*
1781 : : * Retrieve all relids mentioned within the join clause.
1782 : : */
1689 1783 : 26092 : clause_relids = pull_varnos(root, (Node *) clause);
1784 : :
1785 : : /*
1786 : : * For which relids is the clause strict, ie, it cannot succeed if the
1787 : : * rel's columns are all NULL?
1788 : : */
6232 1789 : 26092 : strict_relids = find_nonnullable_rels((Node *) clause);
1790 : :
1791 : : /* Remember whether the clause is strict for any LHS relations */
1792 : 26092 : sjinfo->lhs_strict = bms_overlap(strict_relids, left_rels);
1793 : :
1794 : : /*
1795 : : * Required LHS always includes the LHS rels mentioned in the clause. We
1796 : : * may have to add more rels based on lower outer joins; see below.
1797 : : */
6581 1798 : 26092 : min_lefthand = bms_intersect(clause_relids, left_rels);
1799 : :
1800 : : /*
1801 : : * Similarly for required RHS. But here, we must also include any lower
1802 : : * inner joins, to ensure we don't try to commute with any of them.
1803 : : */
1804 : 26092 : min_righthand = bms_int_members(bms_union(clause_relids, inner_join_rels),
1805 : : right_rels);
1806 : :
1807 : : /*
1808 : : * Now check previous outer joins for ordering restrictions.
1809 : : *
1810 : : * commute_below_l and commute_below_r accumulate the relids of lower
1811 : : * outer joins that we think this one can commute with. These decisions
1812 : : * are just tentative within this loop, since we might find an
1813 : : * intermediate outer join that prevents commutation. Surviving relids
1814 : : * will get merged into the SpecialJoinInfo structs afterwards.
1815 : : */
944 1816 : 26092 : commute_below_l = commute_below_r = NULL;
6232 1817 [ + + + + : 34826 : foreach(l, root->join_info_list)
+ + ]
1818 : : {
1819 : 8734 : SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(l);
1820 : : bool have_unsafe_phvs;
1821 : :
1822 : : /*
1823 : : * A full join is an optimization barrier: we can't associate into or
1824 : : * out of it. Hence, if it overlaps either LHS or RHS of the current
1825 : : * rel, expand that side's min relset to cover the whole full join.
1826 : : */
1827 [ + + ]: 8734 : if (otherinfo->jointype == JOIN_FULL)
1828 : : {
944 1829 [ - + ]: 32 : Assert(otherinfo->ojrelid != 0);
3425 1830 [ + + - + ]: 47 : if (bms_overlap(left_rels, otherinfo->syn_lefthand) ||
1831 : 15 : bms_overlap(left_rels, otherinfo->syn_righthand))
1832 : : {
1833 : 17 : min_lefthand = bms_add_members(min_lefthand,
1834 : 17 : otherinfo->syn_lefthand);
1835 : 17 : min_lefthand = bms_add_members(min_lefthand,
1836 : 17 : otherinfo->syn_righthand);
944 1837 : 17 : min_lefthand = bms_add_member(min_lefthand,
1838 : 17 : otherinfo->ojrelid);
1839 : : }
3425 1840 [ + + - + ]: 49 : if (bms_overlap(right_rels, otherinfo->syn_lefthand) ||
1841 : 17 : bms_overlap(right_rels, otherinfo->syn_righthand))
1842 : : {
1843 : 15 : min_righthand = bms_add_members(min_righthand,
1844 : 15 : otherinfo->syn_lefthand);
1845 : 15 : min_righthand = bms_add_members(min_righthand,
1846 : 15 : otherinfo->syn_righthand);
944 1847 : 15 : min_righthand = bms_add_member(min_righthand,
1848 : 15 : otherinfo->ojrelid);
1849 : : }
1850 : : /* Needn't do anything else with the full join */
7200 1851 : 32 : continue;
1852 : : }
1853 : :
1854 : : /*
1855 : : * If our join condition contains any PlaceHolderVars that need to be
1856 : : * evaluated above the lower OJ, then we can't commute with it.
1857 : : */
950 1858 [ + + ]: 8702 : if (otherinfo->ojrelid != 0)
1859 : : have_unsafe_phvs =
1860 : 8526 : contain_placeholder_references_to(root,
1861 : : (Node *) clause,
1862 : 8526 : otherinfo->ojrelid);
1863 : : else
1864 : 176 : have_unsafe_phvs = false;
1865 : :
1866 : : /*
1867 : : * For a lower OJ in our LHS, if our join condition uses the lower
1868 : : * join's RHS and is not strict for that rel, we must preserve the
1869 : : * ordering of the two OJs, so add lower OJ's full syntactic relset to
1870 : : * min_lefthand. (We must use its full syntactic relset, not just its
1871 : : * min_lefthand + min_righthand. This is because there might be other
1872 : : * OJs below this one that this one can commute with, but we cannot
1873 : : * commute with them if we don't with this one.) Also, if we have
1874 : : * unsafe PHVs or the current join is a semijoin or antijoin, we must
1875 : : * preserve ordering regardless of strictness.
1876 : : *
1877 : : * Note: I believe we have to insist on being strict for at least one
1878 : : * rel in the lower OJ's min_righthand, not its whole syn_righthand.
1879 : : *
1880 : : * When we don't need to preserve ordering, check to see if outer join
1881 : : * identity 3 applies, and if so, remove the lower OJ's ojrelid from
1882 : : * our min_lefthand so that commutation is allowed.
1883 : : */
6035 1884 [ + + ]: 8702 : if (bms_overlap(left_rels, otherinfo->syn_righthand))
1885 : : {
1886 [ + + + + ]: 8276 : if (bms_overlap(clause_relids, otherinfo->syn_righthand) &&
950 1887 [ + - ]: 2471 : (have_unsafe_phvs ||
1888 [ + - ]: 2471 : jointype == JOIN_SEMI || jointype == JOIN_ANTI ||
6035 1889 [ + + ]: 2471 : !bms_overlap(strict_relids, otherinfo->min_righthand)))
1890 : : {
1891 : : /* Preserve ordering */
1892 : 21 : min_lefthand = bms_add_members(min_lefthand,
1893 : 21 : otherinfo->syn_lefthand);
1894 : 21 : min_lefthand = bms_add_members(min_lefthand,
1895 : 21 : otherinfo->syn_righthand);
950 1896 [ + - ]: 21 : if (otherinfo->ojrelid != 0)
1897 : 21 : min_lefthand = bms_add_member(min_lefthand,
1898 : 21 : otherinfo->ojrelid);
1899 : : }
1900 [ + + ]: 8255 : else if (jointype == JOIN_LEFT &&
1901 [ + + + + ]: 15884 : otherinfo->jointype == JOIN_LEFT &&
939 1902 : 7941 : bms_overlap(strict_relids, otherinfo->min_righthand) &&
1903 [ + + ]: 2456 : !bms_overlap(clause_relids, otherinfo->syn_lefthand))
1904 : : {
1905 : : /* Identity 3 applies, so remove the ordering restriction */
950 1906 : 2429 : min_lefthand = bms_del_member(min_lefthand, otherinfo->ojrelid);
1907 : : /* Record the (still tentative) commutability relationship */
1908 : : commute_below_l =
944 1909 : 2429 : bms_add_member(commute_below_l, otherinfo->ojrelid);
1910 : : }
1911 : : }
1912 : :
1913 : : /*
1914 : : * For a lower OJ in our RHS, if our join condition does not use the
1915 : : * lower join's RHS and the lower OJ's join condition is strict, we
1916 : : * can interchange the ordering of the two OJs; otherwise we must add
1917 : : * the lower OJ's full syntactic relset to min_righthand.
1918 : : *
1919 : : * Also, if our join condition does not use the lower join's LHS
1920 : : * either, force the ordering to be preserved. Otherwise we can end
1921 : : * up with SpecialJoinInfos with identical min_righthands, which can
1922 : : * confuse join_is_legal (see discussion in backend/optimizer/README).
1923 : : *
1924 : : * Also, we must preserve ordering anyway if we have unsafe PHVs, or
1925 : : * if either this join or the lower OJ is a semijoin or antijoin.
1926 : : *
1927 : : * When we don't need to preserve ordering, check to see if outer join
1928 : : * identity 3 applies, and if so, remove the lower OJ's ojrelid from
1929 : : * our min_righthand so that commutation is allowed.
1930 : : */
6581 1931 [ + + ]: 8702 : if (bms_overlap(right_rels, otherinfo->syn_righthand))
1932 : : {
1933 [ + + ]: 383 : if (bms_overlap(clause_relids, otherinfo->syn_righthand) ||
3684 1934 [ + + + - ]: 359 : !bms_overlap(clause_relids, otherinfo->min_lefthand) ||
950 1935 [ + + ]: 203 : have_unsafe_phvs ||
5966 1936 [ + + ]: 155 : jointype == JOIN_SEMI ||
3787 1937 : 152 : jointype == JOIN_ANTI ||
5891 1938 [ + + ]: 152 : otherinfo->jointype == JOIN_SEMI ||
6035 1939 [ + - ]: 122 : otherinfo->jointype == JOIN_ANTI ||
950 1940 [ + + ]: 122 : !otherinfo->lhs_strict)
1941 : : {
1942 : : /* Preserve ordering */
6581 1943 : 273 : min_righthand = bms_add_members(min_righthand,
1944 : 273 : otherinfo->syn_lefthand);
1945 : 273 : min_righthand = bms_add_members(min_righthand,
1946 : 273 : otherinfo->syn_righthand);
950 1947 [ + + ]: 273 : if (otherinfo->ojrelid != 0)
1948 : 195 : min_righthand = bms_add_member(min_righthand,
1949 : 195 : otherinfo->ojrelid);
1950 : : }
1951 [ + - ]: 110 : else if (jointype == JOIN_LEFT &&
1952 [ + - ]: 110 : otherinfo->jointype == JOIN_LEFT &&
1953 [ + - ]: 110 : otherinfo->lhs_strict)
1954 : : {
1955 : : /* Identity 3 applies, so remove the ordering restriction */
1956 : 110 : min_righthand = bms_del_member(min_righthand,
1957 : 110 : otherinfo->ojrelid);
1958 : : /* Record the (still tentative) commutability relationship */
1959 : : commute_below_r =
944 1960 : 110 : bms_add_member(commute_below_r, otherinfo->ojrelid);
1961 : : }
1962 : : }
1963 : : }
1964 : :
1965 : : /*
1966 : : * Examine PlaceHolderVars. If a PHV is supposed to be evaluated within
1967 : : * this join's nullable side, then ensure that min_righthand contains the
1968 : : * full eval_at set of the PHV. This ensures that the PHV actually can be
1969 : : * evaluated within the RHS. Note that this works only because we should
1970 : : * already have determined the final eval_at level for any PHV
1971 : : * syntactically within this join.
1972 : : */
5457 1973 [ + + + + : 26800 : foreach(l, root->placeholder_list)
+ + ]
1974 : : {
1975 : 708 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
1976 : 708 : Relids ph_syn_level = phinfo->ph_var->phrels;
1977 : :
1978 : : /* Ignore placeholder if it didn't syntactically come from RHS */
1979 [ + + ]: 708 : if (!bms_is_subset(ph_syn_level, right_rels))
1980 : 256 : continue;
1981 : :
1982 : : /* Else, prevent join from being formed before we eval the PHV */
1983 : 452 : min_righthand = bms_add_members(min_righthand, phinfo->ph_eval_at);
1984 : : }
1985 : :
1986 : : /*
1987 : : * If we found nothing to put in min_lefthand, punt and make it the full
1988 : : * LHS, to avoid having an empty min_lefthand which will confuse later
1989 : : * processing. (We don't try to be smart about such cases, just correct.)
1990 : : * Likewise for min_righthand.
1991 : : */
6581 1992 [ + + ]: 26092 : if (bms_is_empty(min_lefthand))
1993 : 795 : min_lefthand = bms_copy(left_rels);
3684 1994 [ + + ]: 26092 : if (bms_is_empty(min_righthand))
1995 : 337 : min_righthand = bms_copy(right_rels);
1996 : :
1997 : : /* Now they'd better be nonempty */
6581 1998 [ - + ]: 26092 : Assert(!bms_is_empty(min_lefthand));
1999 [ - + ]: 26092 : Assert(!bms_is_empty(min_righthand));
2000 : : /* Shouldn't overlap either */
2001 [ - + ]: 26092 : Assert(!bms_overlap(min_lefthand, min_righthand));
2002 : :
6232 2003 : 26092 : sjinfo->min_lefthand = min_lefthand;
2004 : 26092 : sjinfo->min_righthand = min_righthand;
2005 : :
2006 : : /*
2007 : : * Now that we've identified the correct min_lefthand and min_righthand,
2008 : : * any commute_below_l or commute_below_r relids that have not gotten
2009 : : * added back into those sets (due to intervening outer joins) are indeed
2010 : : * commutable with this one.
2011 : : *
2012 : : * First, delete any subsequently-added-back relids (this is easier than
2013 : : * maintaining commute_below_l/r precisely through all the above).
2014 : : */
843 2015 : 26092 : commute_below_l = bms_del_members(commute_below_l, min_lefthand);
2016 : 26092 : commute_below_r = bms_del_members(commute_below_r, min_righthand);
2017 : :
2018 : : /* Anything left? */
944 2019 [ + + + + ]: 26092 : if (commute_below_l || commute_below_r)
2020 : : {
2021 : : /* Yup, so we must update the derived data in the SpecialJoinInfos */
843 2022 : 2500 : sjinfo->commute_below_l = commute_below_l;
2023 : 2500 : sjinfo->commute_below_r = commute_below_r;
2024 [ + - + + : 5459 : foreach(l, root->join_info_list)
+ + ]
2025 : : {
2026 : 2959 : SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(l);
2027 : :
2028 [ + + ]: 2959 : if (bms_is_member(otherinfo->ojrelid, commute_below_l))
2029 : 2429 : otherinfo->commute_above_l =
2030 : 2429 : bms_add_member(otherinfo->commute_above_l, ojrelid);
2031 [ + + ]: 530 : else if (bms_is_member(otherinfo->ojrelid, commute_below_r))
2032 : 95 : otherinfo->commute_above_r =
2033 : 95 : bms_add_member(otherinfo->commute_above_r, ojrelid);
2034 : : }
2035 : : }
2036 : :
6232 2037 : 26092 : return sjinfo;
2038 : : }
2039 : :
2040 : : /*
2041 : : * compute_semijoin_info
2042 : : * Fill semijoin-related fields of a new SpecialJoinInfo
2043 : : *
2044 : : * Note: this relies on only the jointype and syn_righthand fields of the
2045 : : * SpecialJoinInfo; the rest may not be set yet.
2046 : : */
2047 : : static void
1689 2048 : 26606 : compute_semijoin_info(PlannerInfo *root, SpecialJoinInfo *sjinfo, List *clause)
2049 : : {
2050 : : List *semi_operators;
2051 : : List *semi_rhs_exprs;
2052 : : bool all_btree;
2053 : : bool all_hash;
2054 : : ListCell *lc;
2055 : :
2056 : : /* Initialize semijoin-related fields in case we can't unique-ify */
3832 2057 : 26606 : sjinfo->semi_can_btree = false;
2058 : 26606 : sjinfo->semi_can_hash = false;
2059 : 26606 : sjinfo->semi_operators = NIL;
2060 : 26606 : sjinfo->semi_rhs_exprs = NIL;
2061 : :
2062 : : /* Nothing more to do if it's not a semijoin */
2063 [ + + ]: 26606 : if (sjinfo->jointype != JOIN_SEMI)
2064 : 24134 : return;
2065 : :
2066 : : /*
2067 : : * Look to see whether the semijoin's join quals consist of AND'ed
2068 : : * equality operators, with (only) RHS variables on only one side of each
2069 : : * one. If so, we can figure out how to enforce uniqueness for the RHS.
2070 : : *
2071 : : * Note that the input clause list is the list of quals that are
2072 : : * *syntactically* associated with the semijoin, which in practice means
2073 : : * the synthesized comparison list for an IN or the WHERE of an EXISTS.
2074 : : * Particularly in the latter case, it might contain clauses that aren't
2075 : : * *semantically* associated with the join, but refer to just one side or
2076 : : * the other. We can ignore such clauses here, as they will just drop
2077 : : * down to be processed within one side or the other. (It is okay to
2078 : : * consider only the syntactically-associated clauses here because for a
2079 : : * semijoin, no higher-level quals could refer to the RHS, and so there
2080 : : * can be no other quals that are semantically associated with this join.
2081 : : * We do things this way because it is useful to have the set of potential
2082 : : * unique-ification expressions before we can extract the list of quals
2083 : : * that are actually semantically associated with the particular join.)
2084 : : *
2085 : : * Note that the semi_operators list consists of the joinqual operators
2086 : : * themselves (but commuted if needed to put the RHS value on the right).
2087 : : * These could be cross-type operators, in which case the operator
2088 : : * actually needed for uniqueness is a related single-type operator. We
2089 : : * assume here that that operator will be available from the btree or hash
2090 : : * opclass when the time comes ... if not, create_unique_plan() will fail.
2091 : : */
2092 : 2472 : semi_operators = NIL;
2093 : 2472 : semi_rhs_exprs = NIL;
2094 : 2472 : all_btree = true;
2095 : 2472 : all_hash = enable_hashagg; /* don't consider hash if not enabled */
2096 [ + - + + : 5129 : foreach(lc, clause)
+ + ]
2097 : : {
2098 : 2714 : OpExpr *op = (OpExpr *) lfirst(lc);
2099 : : Oid opno;
2100 : : Node *left_expr;
2101 : : Node *right_expr;
2102 : : Relids left_varnos;
2103 : : Relids right_varnos;
2104 : : Relids all_varnos;
2105 : : Oid opinputtype;
2106 : :
2107 : : /* Is it a binary opclause? */
2108 [ + + - + ]: 5374 : if (!IsA(op, OpExpr) ||
2109 : 2660 : list_length(op->args) != 2)
2110 : : {
2111 : : /* No, but does it reference both sides? */
1689 2112 : 54 : all_varnos = pull_varnos(root, (Node *) op);
3832 2113 [ + + + + ]: 102 : if (!bms_overlap(all_varnos, sjinfo->syn_righthand) ||
2114 : 48 : bms_is_subset(all_varnos, sjinfo->syn_righthand))
2115 : : {
2116 : : /*
2117 : : * Clause refers to only one rel, so ignore it --- unless it
2118 : : * contains volatile functions, in which case we'd better
2119 : : * punt.
2120 : : */
2121 [ - + ]: 48 : if (contain_volatile_functions((Node *) op))
2122 : 57 : return;
2123 : 48 : continue;
2124 : : }
2125 : : /* Non-operator clause referencing both sides, must punt */
2126 : 6 : return;
2127 : : }
2128 : :
2129 : : /* Extract data from binary opclause */
2130 : 2660 : opno = op->opno;
2131 : 2660 : left_expr = linitial(op->args);
2132 : 2660 : right_expr = lsecond(op->args);
1689 2133 : 2660 : left_varnos = pull_varnos(root, left_expr);
2134 : 2660 : right_varnos = pull_varnos(root, right_expr);
3832 2135 : 2660 : all_varnos = bms_union(left_varnos, right_varnos);
2136 : 2660 : opinputtype = exprType(left_expr);
2137 : :
2138 : : /* Does it reference both sides? */
2139 [ + + + + ]: 5310 : if (!bms_overlap(all_varnos, sjinfo->syn_righthand) ||
2140 : 2650 : bms_is_subset(all_varnos, sjinfo->syn_righthand))
2141 : : {
2142 : : /*
2143 : : * Clause refers to only one rel, so ignore it --- unless it
2144 : : * contains volatile functions, in which case we'd better punt.
2145 : : */
2146 [ - + ]: 65 : if (contain_volatile_functions((Node *) op))
3832 tgl@sss.pgh.pa.us 2147 :UBC 0 : return;
3832 tgl@sss.pgh.pa.us 2148 :CBC 65 : continue;
2149 : : }
2150 : :
2151 : : /* check rel membership of arguments */
2152 [ + - + + ]: 5190 : if (!bms_is_empty(right_varnos) &&
2153 : 2595 : bms_is_subset(right_varnos, sjinfo->syn_righthand) &&
2154 [ + - ]: 2368 : !bms_overlap(left_varnos, sjinfo->syn_righthand))
2155 : : {
2156 : : /* typical case, right_expr is RHS variable */
2157 : : }
2158 [ + - + + ]: 454 : else if (!bms_is_empty(left_varnos) &&
2159 : 227 : bms_is_subset(left_varnos, sjinfo->syn_righthand) &&
2160 [ + - ]: 224 : !bms_overlap(right_varnos, sjinfo->syn_righthand))
2161 : : {
2162 : : /* flipped case, left_expr is RHS variable */
2163 : 224 : opno = get_commutator(opno);
2164 [ - + ]: 224 : if (!OidIsValid(opno))
3832 tgl@sss.pgh.pa.us 2165 :UBC 0 : return;
3832 tgl@sss.pgh.pa.us 2166 :CBC 224 : right_expr = left_expr;
2167 : : }
2168 : : else
2169 : : {
2170 : : /* mixed membership of args, punt */
2171 : 3 : return;
2172 : : }
2173 : :
2174 : : /* all operators must be btree equality or hash equality */
2175 [ + - ]: 2592 : if (all_btree)
2176 : : {
2177 : : /* oprcanmerge is considered a hint... */
2178 [ + + - + ]: 5136 : if (!op_mergejoinable(opno, opinputtype) ||
2179 : 2544 : get_mergejoin_opfamilies(opno) == NIL)
2180 : 48 : all_btree = false;
2181 : : }
2182 [ + + ]: 2592 : if (all_hash)
2183 : : {
2184 : : /* ... but oprcanhash had better be correct */
2185 [ + + ]: 2556 : if (!op_hashjoinable(opno, opinputtype))
2186 : 48 : all_hash = false;
2187 : : }
2188 [ + + + - ]: 2592 : if (!(all_btree || all_hash))
2189 : 48 : return;
2190 : :
2191 : : /* so far so good, keep building lists */
2192 : 2544 : semi_operators = lappend_oid(semi_operators, opno);
2193 : 2544 : semi_rhs_exprs = lappend(semi_rhs_exprs, copyObject(right_expr));
2194 : : }
2195 : :
2196 : : /* Punt if we didn't find at least one column to unique-ify */
2197 [ + + ]: 2415 : if (semi_rhs_exprs == NIL)
2198 : 6 : return;
2199 : :
2200 : : /*
2201 : : * The expressions we'd need to unique-ify mustn't be volatile.
2202 : : */
2203 [ - + ]: 2409 : if (contain_volatile_functions((Node *) semi_rhs_exprs))
3832 tgl@sss.pgh.pa.us 2204 :UBC 0 : return;
2205 : :
2206 : : /*
2207 : : * If we get here, we can unique-ify the semijoin's RHS using at least one
2208 : : * of sorting and hashing. Save the information about how to do that.
2209 : : */
3832 tgl@sss.pgh.pa.us 2210 :CBC 2409 : sjinfo->semi_can_btree = all_btree;
2211 : 2409 : sjinfo->semi_can_hash = all_hash;
2212 : 2409 : sjinfo->semi_operators = semi_operators;
2213 : 2409 : sjinfo->semi_rhs_exprs = semi_rhs_exprs;
2214 : : }
2215 : :
2216 : : /*
2217 : : * deconstruct_distribute_oj_quals
2218 : : * Adjust LEFT JOIN quals to be suitable for commuted-left-join cases,
2219 : : * then push them into the joinqual lists and EquivalenceClass structures.
2220 : : *
2221 : : * This runs immediately after we've completed the deconstruct_distribute scan.
2222 : : * jtitems contains all the JoinTreeItems (in depth-first order), and jtitem
2223 : : * is one that has postponed oj_joinclauses to deal with.
2224 : : */
2225 : : static void
950 2226 : 20835 : deconstruct_distribute_oj_quals(PlannerInfo *root,
2227 : : List *jtitems,
2228 : : JoinTreeItem *jtitem)
2229 : : {
2230 : 20835 : SpecialJoinInfo *sjinfo = jtitem->sjinfo;
2231 : : Relids qualscope,
2232 : : ojscope,
2233 : : nonnullable_rels;
2234 : :
2235 : : /* Recompute syntactic and semantic scopes of this left join */
2236 : 20835 : qualscope = bms_union(sjinfo->syn_lefthand, sjinfo->syn_righthand);
2237 : 20835 : qualscope = bms_add_member(qualscope, sjinfo->ojrelid);
2238 : 20835 : ojscope = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
2239 : 20835 : nonnullable_rels = sjinfo->syn_lefthand;
2240 : :
2241 : : /*
2242 : : * If this join can commute with any other ones per outer-join identity 3,
2243 : : * and it is the one providing the join clause with flexible semantics,
2244 : : * then we have to generate variants of the join clause with different
2245 : : * nullingrels labeling. Otherwise, just push out the postponed clause
2246 : : * as-is.
2247 : : */
2248 [ - + ]: 20835 : Assert(sjinfo->lhs_strict); /* else we shouldn't be here */
843 2249 [ + + + + ]: 20835 : if (sjinfo->commute_above_r || sjinfo->commute_below_l)
950 2250 : 2506 : {
2251 : : Relids joins_above;
2252 : : Relids joins_below;
2253 : : Relids incompatible_joins;
2254 : : Relids joins_so_far;
2255 : : List *quals;
2256 : : int save_last_rinfo_serial;
2257 : : ListCell *lc;
2258 : :
2259 : : /* Identify the outer joins this one commutes with */
2260 : 2506 : joins_above = sjinfo->commute_above_r;
843 2261 : 2506 : joins_below = sjinfo->commute_below_l;
2262 : :
2263 : : /*
2264 : : * Generate qual variants with different sets of nullingrels bits.
2265 : : *
2266 : : * We only need bit-sets that correspond to the successively less
2267 : : * deeply syntactically-nested subsets of this join and its
2268 : : * commutators. That's true first because obviously only those forms
2269 : : * of the Vars and PHVs could appear elsewhere in the query, and
2270 : : * second because the outer join identities do not provide a way to
2271 : : * re-order such joins in a way that would require different marking.
2272 : : * (That is, while the current join may commute with several others,
2273 : : * none of those others can commute with each other.) To visit the
2274 : : * interesting joins in syntactic nesting order, we rely on the
2275 : : * jtitems list to be ordered that way.
2276 : : *
2277 : : * We first strip out all the nullingrels bits corresponding to
2278 : : * commuting joins below this one, and then successively put them back
2279 : : * as we crawl up the join stack.
2280 : : */
950 2281 : 2506 : quals = jtitem->oj_joinclauses;
2282 [ + + ]: 2506 : if (!bms_is_empty(joins_below))
2283 : 2411 : quals = (List *) remove_nulling_relids((Node *) quals,
2284 : : joins_below,
2285 : : NULL);
2286 : :
2287 : : /*
2288 : : * We'll need to mark the lower versions of the quals as not safe to
2289 : : * apply above not-yet-processed joins of the stack. This prevents
2290 : : * possibly applying a cloned qual at the wrong join level.
2291 : : */
835 2292 : 2506 : incompatible_joins = bms_union(joins_below, joins_above);
2293 : 2506 : incompatible_joins = bms_add_member(incompatible_joins,
2294 : 2506 : sjinfo->ojrelid);
2295 : :
2296 : : /*
2297 : : * Each time we produce RestrictInfo(s) from these quals, reset the
2298 : : * last_rinfo_serial counter, so that the RestrictInfos for the "same"
2299 : : * qual condition get identical serial numbers. (This relies on the
2300 : : * fact that we're not changing the qual list in any way that'd affect
2301 : : * the number of RestrictInfos built from it.) This'll allow us to
2302 : : * detect duplicative qual usage later.
2303 : : */
950 2304 : 2506 : save_last_rinfo_serial = root->last_rinfo_serial;
2305 : :
2306 : 2506 : joins_so_far = NULL;
2307 [ + - + + : 21830 : foreach(lc, jtitems)
+ + ]
2308 : : {
2309 : 19324 : JoinTreeItem *otherjtitem = (JoinTreeItem *) lfirst(lc);
2310 : 19324 : SpecialJoinInfo *othersj = otherjtitem->sjinfo;
2311 : 19324 : bool below_sjinfo = false;
2312 : 19324 : bool above_sjinfo = false;
2313 : : Relids this_qualscope;
2314 : : Relids this_ojscope;
2315 : : bool allow_equivalence,
2316 : : has_clone,
2317 : : is_clone;
2318 : :
2319 [ + + ]: 19324 : if (othersj == NULL)
2320 : 13731 : continue; /* not an outer-join item, ignore */
2321 : :
2322 [ + + ]: 5593 : if (bms_is_member(othersj->ojrelid, joins_below))
2323 : : {
2324 : : /* othersj commutes with sjinfo from below left */
2325 : 2429 : below_sjinfo = true;
2326 : : }
2327 [ + + ]: 3164 : else if (othersj == sjinfo)
2328 : : {
2329 : : /* found our join in syntactic order */
2330 [ - + ]: 2506 : Assert(bms_equal(joins_so_far, joins_below));
2331 : : }
2332 [ + + ]: 658 : else if (bms_is_member(othersj->ojrelid, joins_above))
2333 : : {
2334 : : /* othersj commutes with sjinfo from above */
2335 : 95 : above_sjinfo = true;
2336 : : }
2337 : : else
2338 : : {
2339 : : /* othersj is not relevant, ignore */
2340 : 563 : continue;
2341 : : }
2342 : :
2343 : : /* Reset serial counter for this version of the quals */
2344 : 5030 : root->last_rinfo_serial = save_last_rinfo_serial;
2345 : :
2346 : : /*
2347 : : * When we are looking at joins above sjinfo, we are envisioning
2348 : : * pushing sjinfo to above othersj, so add othersj's nulling bit
2349 : : * before distributing the quals. We should add it to Vars coming
2350 : : * from the current join's LHS: we want to transform the second
2351 : : * form of OJ identity 3 to the first form, in which Vars of
2352 : : * relation B will appear nulled by the syntactically-upper OJ
2353 : : * within the Pbc clause, but those of relation C will not. (In
2354 : : * the notation used by optimizer/README, we're converting a qual
2355 : : * of the form Pbc to Pb*c.) Of course, we must also remove that
2356 : : * bit from the incompatible_joins value, else we'll make a qual
2357 : : * that can't be placed anywhere.
2358 : : */
2359 [ + + ]: 5030 : if (above_sjinfo)
2360 : : {
2361 : : quals = (List *)
2362 : 95 : add_nulling_relids((Node *) quals,
939 2363 : 95 : sjinfo->syn_lefthand,
950 2364 : 95 : bms_make_singleton(othersj->ojrelid));
835 2365 : 95 : incompatible_joins = bms_del_member(incompatible_joins,
2366 : 95 : othersj->ojrelid);
2367 : : }
2368 : :
2369 : : /* Compute qualscope and ojscope for this join level */
950 2370 : 5030 : this_qualscope = bms_union(qualscope, joins_so_far);
2371 : 5030 : this_ojscope = bms_union(ojscope, joins_so_far);
2372 [ + + ]: 5030 : if (above_sjinfo)
2373 : : {
2374 : : /* othersj is not yet in joins_so_far, but we need it */
2375 : 95 : this_qualscope = bms_add_member(this_qualscope,
2376 : 95 : othersj->ojrelid);
2377 : 95 : this_ojscope = bms_add_member(this_ojscope,
2378 : 95 : othersj->ojrelid);
2379 : : /* sjinfo is in joins_so_far, and we don't want it */
2380 : 95 : this_ojscope = bms_del_member(this_ojscope,
2381 : 95 : sjinfo->ojrelid);
2382 : : }
2383 : :
2384 : : /*
2385 : : * We generate EquivalenceClasses only from the first form of the
2386 : : * quals, with the fewest nullingrels bits set. An EC made from
2387 : : * this version of the quals can be useful below the outer-join
2388 : : * nest, whereas versions with some nullingrels bits set would not
2389 : : * be. We cannot generate ECs from more than one version, or
2390 : : * we'll make nonsensical conclusions that Vars with nullingrels
2391 : : * bits set are equal to their versions without. Fortunately,
2392 : : * such ECs wouldn't be very useful anyway, because they'd equate
2393 : : * values not observable outside the join nest. (See
2394 : : * optimizer/README.)
2395 : : *
2396 : : * The first form of the quals is also the only one marked as
2397 : : * has_clone rather than is_clone.
2398 : : */
2399 : 5030 : allow_equivalence = (joins_so_far == NULL);
2400 : 5030 : has_clone = allow_equivalence;
2401 : 5030 : is_clone = !has_clone;
2402 : :
2403 : 5030 : distribute_quals_to_rels(root, quals,
2404 : : otherjtitem,
2405 : : sjinfo,
2406 : : root->qual_security_level,
2407 : : this_qualscope,
2408 : : this_ojscope, nonnullable_rels,
2409 : : bms_copy(incompatible_joins),
2410 : : allow_equivalence,
2411 : : has_clone,
2412 : : is_clone,
2413 : : NULL); /* no more postponement */
2414 : :
2415 : : /*
2416 : : * Adjust qual nulling bits for next level up, if needed. We
2417 : : * don't want to put sjinfo's own bit in at all, and if we're
2418 : : * above sjinfo then we did it already. Here, we should mark all
2419 : : * Vars coming from the lower join's RHS. (Again, we are
2420 : : * converting a qual of the form Pbc to Pb*c, but now we are
2421 : : * putting back bits that were there in the parser output and were
2422 : : * temporarily stripped above.) Update incompatible_joins too.
2423 : : */
2424 [ + + ]: 5030 : if (below_sjinfo)
2425 : : {
2426 : : quals = (List *)
2427 : 2429 : add_nulling_relids((Node *) quals,
939 2428 : 2429 : othersj->syn_righthand,
950 2429 : 2429 : bms_make_singleton(othersj->ojrelid));
835 2430 : 2429 : incompatible_joins = bms_del_member(incompatible_joins,
2431 : 2429 : othersj->ojrelid);
2432 : : }
2433 : :
2434 : : /* ... and track joins processed so far */
950 2435 : 5030 : joins_so_far = bms_add_member(joins_so_far, othersj->ojrelid);
2436 : : }
2437 : : }
2438 : : else
2439 : : {
2440 : : /* No commutation possible, just process the postponed clauses */
2441 : 18329 : distribute_quals_to_rels(root, jtitem->oj_joinclauses,
2442 : : jtitem,
2443 : : sjinfo,
2444 : : root->qual_security_level,
2445 : : qualscope,
2446 : : ojscope, nonnullable_rels,
2447 : : NULL, /* incompatible_relids */
2448 : : true, /* allow_equivalence */
2449 : : false, false, /* not clones */
2450 : : NULL); /* no more postponement */
2451 : : }
2452 : 20835 : }
2453 : :
2454 : :
2455 : : /*****************************************************************************
2456 : : *
2457 : : * QUALIFICATIONS
2458 : : *
2459 : : *****************************************************************************/
2460 : :
2461 : : /*
2462 : : * distribute_quals_to_rels
2463 : : * Convenience routine to apply distribute_qual_to_rels to each element
2464 : : * of an AND'ed list of clauses.
2465 : : */
2466 : : static void
2467 : 401778 : distribute_quals_to_rels(PlannerInfo *root, List *clauses,
2468 : : JoinTreeItem *jtitem,
2469 : : SpecialJoinInfo *sjinfo,
2470 : : Index security_level,
2471 : : Relids qualscope,
2472 : : Relids ojscope,
2473 : : Relids outerjoin_nonnullable,
2474 : : Relids incompatible_relids,
2475 : : bool allow_equivalence,
2476 : : bool has_clone,
2477 : : bool is_clone,
2478 : : List **postponed_oj_qual_list)
2479 : : {
2480 : : ListCell *lc;
2481 : :
2482 [ + + + + : 689835 : foreach(lc, clauses)
+ + ]
2483 : : {
2484 : 288057 : Node *clause = (Node *) lfirst(lc);
2485 : :
2486 : 288057 : distribute_qual_to_rels(root, clause,
2487 : : jtitem,
2488 : : sjinfo,
2489 : : security_level,
2490 : : qualscope,
2491 : : ojscope,
2492 : : outerjoin_nonnullable,
2493 : : incompatible_relids,
2494 : : allow_equivalence,
2495 : : has_clone,
2496 : : is_clone,
2497 : : postponed_oj_qual_list);
2498 : : }
2499 : 401778 : }
2500 : :
2501 : : /*
2502 : : * distribute_qual_to_rels
2503 : : * Add clause information to either the baserestrictinfo or joininfo list
2504 : : * (depending on whether the clause is a join) of each base relation
2505 : : * mentioned in the clause. A RestrictInfo node is created and added to
2506 : : * the appropriate list for each rel. Alternatively, if the clause uses a
2507 : : * mergejoinable operator, enter its left- and right-side expressions into
2508 : : * the query's EquivalenceClasses.
2509 : : *
2510 : : * In some cases, quals will be added to parent jtitems' lateral_clauses
2511 : : * or to postponed_oj_qual_list instead of being processed right away.
2512 : : * These will be dealt with in later calls of deconstruct_distribute.
2513 : : *
2514 : : * 'clause': the qual clause to be distributed
2515 : : * 'jtitem': the JoinTreeItem for the containing jointree node
2516 : : * 'sjinfo': join's SpecialJoinInfo (NULL for an inner join or WHERE clause)
2517 : : * 'security_level': security_level to assign to the qual
2518 : : * 'qualscope': set of base+OJ rels the qual's syntactic scope covers
2519 : : * 'ojscope': NULL if not an outer-join qual, else the minimum set of base+OJ
2520 : : * rels needed to form this join
2521 : : * 'outerjoin_nonnullable': NULL if not an outer-join qual, else the set of
2522 : : * base+OJ rels appearing on the outer (nonnullable) side of the join
2523 : : * (for FULL JOIN this includes both sides of the join, and must in fact
2524 : : * equal qualscope)
2525 : : * 'incompatible_relids': the set of outer-join relid(s) that must not be
2526 : : * computed below this qual. We only bother to compute this for
2527 : : * "clone" quals, otherwise it can be left NULL.
2528 : : * 'allow_equivalence': true if it's okay to convert clause into an
2529 : : * EquivalenceClass
2530 : : * 'has_clone': has_clone property to assign to the qual
2531 : : * 'is_clone': is_clone property to assign to the qual
2532 : : * 'postponed_oj_qual_list': if not NULL, non-degenerate outer join clauses
2533 : : * should be added to this list instead of being processed (list entries
2534 : : * are just the bare clauses)
2535 : : *
2536 : : * 'qualscope' identifies what level of JOIN the qual came from syntactically.
2537 : : * 'ojscope' is needed if we decide to force the qual up to the outer-join
2538 : : * level, which will be ojscope not necessarily qualscope.
2539 : : *
2540 : : * At the time this is called, root->join_info_list must contain entries for
2541 : : * at least those special joins that are syntactically below this qual.
2542 : : * (We now need that only for detection of redundant IS NULL quals.)
2543 : : */
2544 : : static void
7398 2545 : 288057 : distribute_qual_to_rels(PlannerInfo *root, Node *clause,
2546 : : JoinTreeItem *jtitem,
2547 : : SpecialJoinInfo *sjinfo,
2548 : : Index security_level,
2549 : : Relids qualscope,
2550 : : Relids ojscope,
2551 : : Relids outerjoin_nonnullable,
2552 : : Relids incompatible_relids,
2553 : : bool allow_equivalence,
2554 : : bool has_clone,
2555 : : bool is_clone,
2556 : : List **postponed_oj_qual_list)
2557 : : {
2558 : : Relids relids;
2559 : : bool is_pushed_down;
7007 2560 : 288057 : bool pseudoconstant = false;
2561 : : bool maybe_equivalence;
2562 : : bool maybe_outer_join;
2563 : : RestrictInfo *restrictinfo;
2564 : :
2565 : : /*
2566 : : * Retrieve all relids mentioned within the clause.
2567 : : */
1689 2568 : 288057 : relids = pull_varnos(root, clause);
2569 : :
2570 : : /*
2571 : : * In ordinary SQL, a WHERE or JOIN/ON clause can't reference any rels
2572 : : * that aren't within its syntactic scope; however, if we pulled up a
2573 : : * LATERAL subquery then we might find such references in quals that have
2574 : : * been pulled up. We need to treat such quals as belonging to the join
2575 : : * level that includes every rel they reference. Although we could make
2576 : : * pull_up_subqueries() place such quals correctly to begin with, it's
2577 : : * easier to handle it here. When we find a clause that contains Vars
2578 : : * outside its syntactic scope, locate the nearest parent join level that
2579 : : * includes all the required rels and add the clause to that level's
2580 : : * lateral_clauses list. We'll process it when we reach that join level.
2581 : : */
4401 2582 [ + + ]: 288057 : if (!bms_is_subset(relids, qualscope))
2583 : : {
2584 : : JoinTreeItem *pitem;
2585 : :
2586 [ - + ]: 55 : Assert(root->hasLateralRTEs); /* shouldn't happen otherwise */
950 2587 [ - + ]: 55 : Assert(sjinfo == NULL); /* mustn't postpone past outer join */
945 2588 [ + - ]: 58 : for (pitem = jtitem->jti_parent; pitem; pitem = pitem->jti_parent)
2589 : : {
2590 [ + + ]: 58 : if (bms_is_subset(relids, pitem->qualscope))
2591 : : {
2592 : 55 : pitem->lateral_clauses = lappend(pitem->lateral_clauses,
2593 : : clause);
2594 : 202666 : return;
2595 : : }
2596 : :
2597 : : /*
2598 : : * We should not be postponing any quals past an outer join. If
2599 : : * this Assert fires, pull_up_subqueries() messed up.
2600 : : */
2601 [ - + ]: 3 : Assert(pitem->sjinfo == NULL);
2602 : : }
945 tgl@sss.pgh.pa.us 2603 [ # # ]:UBC 0 : elog(ERROR, "failed to postpone qual containing lateral reference");
2604 : : }
2605 : :
2606 : : /*
2607 : : * If it's an outer-join clause, also check that relids is a subset of
2608 : : * ojscope. (This should not fail if the syntactic scope check passed.)
2609 : : */
7200 tgl@sss.pgh.pa.us 2610 [ + + - + ]:CBC 288002 : if (ojscope && !bms_is_subset(relids, ojscope))
6792 bruce@momjian.us 2611 [ # # ]:UBC 0 : elog(ERROR, "JOIN qualification cannot refer to other relations");
2612 : :
2613 : : /*
2614 : : * If the clause is variable-free, our normal heuristic for pushing it
2615 : : * down to just the mentioned rels doesn't work, because there are none.
2616 : : *
2617 : : * If the clause is an outer-join clause, we must force it to the OJ's
2618 : : * semantic level to preserve semantics.
2619 : : *
2620 : : * Otherwise, when the clause contains volatile functions, we force it to
2621 : : * be evaluated at its original syntactic level. This preserves the
2622 : : * expected semantics.
2623 : : *
2624 : : * When the clause contains no volatile functions either, it is actually a
2625 : : * pseudoconstant clause that will not change value during any one
2626 : : * execution of the plan, and hence can be used as a one-time qual in a
2627 : : * gating Result plan node. We put such a clause into the regular
2628 : : * RestrictInfo lists for the moment, but eventually createplan.c will
2629 : : * pull it out and make a gating Result node immediately above whatever
2630 : : * plan node the pseudoconstant clause is assigned to. It's usually best
2631 : : * to put a gating node as high in the plan tree as possible.
2632 : : */
8246 tgl@sss.pgh.pa.us 2633 [ + + ]:CBC 288002 : if (bms_is_empty(relids))
2634 : : {
7007 2635 [ + + ]: 5438 : if (ojscope)
2636 : : {
2637 : : /* clause is attached to outer join, eval it there */
6450 2638 : 196 : relids = bms_copy(ojscope);
2639 : : /* mustn't use as gating qual, so don't mark pseudoconstant */
2640 : : }
950 2641 [ + + ]: 5242 : else if (contain_volatile_functions(clause))
2642 : : {
2643 : : /* eval at original syntactic level */
6450 2644 : 87 : relids = bms_copy(qualscope);
2645 : : /* again, can't mark pseudoconstant */
2646 : : }
2647 : : else
2648 : : {
2649 : : /*
2650 : : * If we are in the top-level join domain, we can push the qual to
2651 : : * the top of the plan tree. Otherwise, be conservative and eval
2652 : : * it at original syntactic level. (Ideally we'd push it to the
2653 : : * top of the current join domain in all cases, but that causes
2654 : : * problems if we later rearrange outer-join evaluation order.
2655 : : * Pseudoconstant quals below the top level are a pretty odd case,
2656 : : * so it's not clear that it's worth working hard on.)
2657 : : */
927 2658 [ + + ]: 5155 : if (jtitem->jdomain == (JoinDomain *) linitial(root->join_domains))
2659 : 5125 : relids = bms_copy(jtitem->jdomain->jd_relids);
2660 : : else
2661 : 30 : relids = bms_copy(qualscope);
2662 : : /* mark as gating qual */
950 2663 : 5155 : pseudoconstant = true;
2664 : : /* tell createplan.c to check for gating quals */
2665 : 5155 : root->hasPseudoConstantQuals = true;
2666 : : }
2667 : : }
2668 : :
2669 : : /*----------
2670 : : * Check to see if clause application must be delayed by outer-join
2671 : : * considerations.
2672 : : *
2673 : : * A word about is_pushed_down: we mark the qual as "pushed down" if
2674 : : * it is (potentially) applicable at a level different from its original
2675 : : * syntactic level. This flag is used to distinguish OUTER JOIN ON quals
2676 : : * from other quals pushed down to the same joinrel. The rules are:
2677 : : * WHERE quals and INNER JOIN quals: is_pushed_down = true.
2678 : : * Non-degenerate OUTER JOIN quals: is_pushed_down = false.
2679 : : * Degenerate OUTER JOIN quals: is_pushed_down = true.
2680 : : * A "degenerate" OUTER JOIN qual is one that doesn't mention the
2681 : : * non-nullable side, and hence can be pushed down into the nullable side
2682 : : * without changing the join result. It is correct to treat it as a
2683 : : * regular filter condition at the level where it is evaluated.
2684 : : *
2685 : : * Note: it is not immediately obvious that a simple boolean is enough
2686 : : * for this: if for some reason we were to attach a degenerate qual to
2687 : : * its original join level, it would need to be treated as an outer join
2688 : : * qual there. However, this cannot happen, because all the rels the
2689 : : * clause mentions must be in the outer join's min_righthand, therefore
2690 : : * the join it needs must be formed before the outer join; and we always
2691 : : * attach quals to the lowest level where they can be evaluated. But
2692 : : * if we were ever to re-introduce a mechanism for delaying evaluation
2693 : : * of "expensive" quals, this area would need work.
2694 : : *
2695 : : * Note: generally, use of is_pushed_down has to go through the macro
2696 : : * RINFO_IS_PUSHED_DOWN, because that flag alone is not always sufficient
2697 : : * to tell whether a clause must be treated as pushed-down in context.
2698 : : * This seems like another reason why it should perhaps be rethought.
2699 : : *----------
2700 : : */
1774 2701 [ + + ]: 288002 : if (bms_overlap(relids, outerjoin_nonnullable))
2702 : : {
2703 : : /*
2704 : : * The qual is attached to an outer join and mentions (some of the)
2705 : : * rels on the nonnullable side, so it's not degenerate. If the
2706 : : * caller wants to postpone handling such clauses, just add it to
2707 : : * postponed_oj_qual_list and return. (The work we've done up to here
2708 : : * will have to be redone later, but there's not much of it.)
2709 : : */
950 2710 [ + + ]: 52350 : if (postponed_oj_qual_list != NULL)
2711 : : {
2712 : 23156 : *postponed_oj_qual_list = lappend(*postponed_oj_qual_list, clause);
2713 : 23156 : return;
2714 : : }
2715 : :
2716 : : /*
2717 : : * We can't use such a clause to deduce equivalence (the left and
2718 : : * right sides might be unequal above the join because one of them has
2719 : : * gone to NULL) ... but we might be able to use it for more limited
2720 : : * deductions, if it is mergejoinable. So consider adding it to the
2721 : : * lists of set-aside outer-join clauses.
2722 : : */
6450 2723 : 29194 : is_pushed_down = false;
6804 2724 : 29194 : maybe_equivalence = false;
6450 2725 : 29194 : maybe_outer_join = true;
2726 : :
2727 : : /*
2728 : : * Now force the qual to be evaluated exactly at the level of joining
2729 : : * corresponding to the outer join. We cannot let it get pushed down
2730 : : * into the nonnullable side, since then we'd produce no output rows,
2731 : : * rather than the intended single null-extended row, for any
2732 : : * nonnullable-side rows failing the qual.
2733 : : */
7200 2734 [ - + ]: 29194 : Assert(ojscope);
2735 : 29194 : relids = ojscope;
7007 2736 [ - + ]: 29194 : Assert(!pseudoconstant);
2737 : : }
2738 : : else
2739 : : {
2740 : : /*
2741 : : * Normal qual clause or degenerate outer-join clause. Either way, we
2742 : : * can mark it as pushed-down.
2743 : : */
6777 2744 : 235652 : is_pushed_down = true;
2745 : :
2746 : : /*
2747 : : * It's possible that this is an IS NULL clause that's redundant with
2748 : : * a lower antijoin; if so we can just discard it. We need not test
2749 : : * in any of the other cases, because this will only be possible for
2750 : : * pushed-down clauses.
2751 : : */
950 2752 [ + + ]: 235652 : if (check_redundant_nullability_qual(root, clause))
2753 : 577 : return;
2754 : :
2755 : : /* Feed qual to the equivalence machinery, if allowed by caller */
2756 : 235075 : maybe_equivalence = allow_equivalence;
2757 : :
2758 : : /*
2759 : : * Since it doesn't mention the LHS, it's certainly not useful as a
2760 : : * set-aside OJ clause, even if it's in an OJ.
2761 : : */
7371 2762 : 235075 : maybe_outer_join = false;
2763 : : }
2764 : :
2765 : : /*
2766 : : * Build the RestrictInfo node itself.
2767 : : */
1689 2768 : 264269 : restrictinfo = make_restrictinfo(root,
2769 : : (Expr *) clause,
2770 : : is_pushed_down,
2771 : : has_clone,
2772 : : is_clone,
2773 : : pseudoconstant,
2774 : : security_level,
2775 : : relids,
2776 : : incompatible_relids,
2777 : : outerjoin_nonnullable);
2778 : :
2779 : : /*
2780 : : * If it's a join clause, add vars used in the clause to targetlists of
2781 : : * their relations, so that they will be emitted by the plan nodes that
2782 : : * scan those relations (else they won't be available at the join node!).
2783 : : *
2784 : : * Normally we mark the vars as needed at the join identified by "relids".
2785 : : * However, if this is a clone clause then ignore the outer-join relids in
2786 : : * that set. Otherwise, vars appearing in a cloned clause would end up
2787 : : * marked as having to propagate to the highest one of the commuting
2788 : : * joins, which would often be an overestimate. For such clauses, correct
2789 : : * var propagation is ensured by making ojscope include input rels from
2790 : : * both sides of the join.
2791 : : *
2792 : : * See also rebuild_joinclause_attr_needed, which has to partially repeat
2793 : : * this work after removal of an outer join.
2794 : : *
2795 : : * Note: if the clause gets absorbed into an EquivalenceClass then this
2796 : : * may be unnecessary, but for now we have to do it to cover the case
2797 : : * where the EC becomes ec_broken and we end up reinserting the original
2798 : : * clauses into the plan.
2799 : : */
6804 2800 [ + + ]: 264269 : if (bms_membership(relids) == BMS_MULTIPLE)
2801 : : {
5170 2802 : 75128 : List *vars = pull_var_clause(clause,
2803 : : PVC_RECURSE_AGGREGATES |
2804 : : PVC_RECURSE_WINDOWFUNCS |
2805 : : PVC_INCLUDE_PLACEHOLDERS);
2806 : : Relids where_needed;
2807 : :
950 2808 [ + + ]: 75128 : if (is_clone)
2809 : 2729 : where_needed = bms_intersect(relids, root->all_baserels);
2810 : : else
2811 : 72399 : where_needed = relids;
2812 : 75128 : add_vars_to_targetlist(root, vars, where_needed);
6804 2813 : 75128 : list_free(vars);
2814 : : }
2815 : :
2816 : : /*
2817 : : * We check "mergejoinability" of every clause, not only join clauses,
2818 : : * because we want to know about equivalences between vars of the same
2819 : : * relation, or between vars and consts.
2820 : : */
2821 : 264269 : check_mergejoinable(restrictinfo);
2822 : :
2823 : : /*
2824 : : * If it is a true equivalence clause, send it to the EquivalenceClass
2825 : : * machinery. We do *not* attach it directly to any restriction or join
2826 : : * lists. The EC code will propagate it to the appropriate places later.
2827 : : *
2828 : : * If the clause has a mergejoinable operator, yet isn't an equivalence
2829 : : * because it is an outer-join clause, the EC code may still be able to do
2830 : : * something with it. We add it to appropriate lists for further
2831 : : * consideration later. Specifically:
2832 : : *
2833 : : * If it is a left or right outer-join qualification that relates the two
2834 : : * sides of the outer join (no funny business like leftvar1 = leftvar2 +
2835 : : * rightvar), we add it to root->left_join_clauses or
2836 : : * root->right_join_clauses according to which side the nonnullable
2837 : : * variable appears on.
2838 : : *
2839 : : * If it is a full outer-join qualification, we add it to
2840 : : * root->full_join_clauses. (Ideally we'd discard cases that aren't
2841 : : * leftvar = rightvar, as we do for left/right joins, but this routine
2842 : : * doesn't have the info needed to do that; and the current usage of the
2843 : : * full_join_clauses list doesn't require that, so it's not currently
2844 : : * worth complicating this routine's API to make it possible.)
2845 : : *
2846 : : * If none of the above hold, pass it off to
2847 : : * distribute_restrictinfo_to_rels().
2848 : : *
2849 : : * In all cases, it's important to initialize the left_ec and right_ec
2850 : : * fields of a mergejoinable clause, so that all possibly mergejoinable
2851 : : * expressions have representations in EquivalenceClasses. If
2852 : : * process_equivalence is successful, it will take care of that;
2853 : : * otherwise, we have to call initialize_mergeclause_eclasses to do it.
2854 : : */
2855 [ + + ]: 264269 : if (restrictinfo->mergeopfamilies)
2856 : : {
2857 [ + + ]: 179459 : if (maybe_equivalence)
2858 : : {
945 2859 [ + + ]: 151002 : if (process_equivalence(root, &restrictinfo, jtitem->jdomain))
6804 2860 : 150871 : return;
2861 : : /* EC rejected it, so set left_ec/right_ec the hard way ... */
2890 2862 [ + + ]: 131 : if (restrictinfo->mergeopfamilies) /* EC might have changed this */
2863 : 104 : initialize_mergeclause_eclasses(root, restrictinfo);
2864 : : /* ... and fall through to distribute_restrictinfo_to_rels */
2865 : : }
7371 2866 [ + - + + ]: 28457 : else if (maybe_outer_join && restrictinfo->can_join)
2867 : : {
2868 : : /* we need to set up left_ec/right_ec the hard way */
5426 2869 : 28105 : initialize_mergeclause_eclasses(root, restrictinfo);
2870 : : /* now see if it should go to any outer-join lists */
950 2871 [ - + ]: 28105 : Assert(sjinfo != NULL);
7371 2872 [ + + ]: 28105 : if (bms_is_subset(restrictinfo->left_relids,
2873 : 13749 : outerjoin_nonnullable) &&
2874 [ + + ]: 13749 : !bms_overlap(restrictinfo->right_relids,
2875 : : outerjoin_nonnullable))
2876 : : {
2877 : : /* we have outervar = innervar */
950 2878 : 13108 : OuterJoinClauseInfo *ojcinfo = makeNode(OuterJoinClauseInfo);
2879 : :
2880 : 13108 : ojcinfo->rinfo = restrictinfo;
2881 : 13108 : ojcinfo->sjinfo = sjinfo;
7371 2882 : 13108 : root->left_join_clauses = lappend(root->left_join_clauses,
2883 : : ojcinfo);
6804 2884 : 13108 : return;
2885 : : }
2886 [ + + ]: 14997 : if (bms_is_subset(restrictinfo->right_relids,
6505 bruce@momjian.us 2887 : 14917 : outerjoin_nonnullable) &&
2888 [ + + ]: 14917 : !bms_overlap(restrictinfo->left_relids,
2889 : : outerjoin_nonnullable))
2890 : : {
2891 : : /* we have innervar = outervar */
950 tgl@sss.pgh.pa.us 2892 : 14276 : OuterJoinClauseInfo *ojcinfo = makeNode(OuterJoinClauseInfo);
2893 : :
2894 : 14276 : ojcinfo->rinfo = restrictinfo;
2895 : 14276 : ojcinfo->sjinfo = sjinfo;
7371 2896 : 14276 : root->right_join_clauses = lappend(root->right_join_clauses,
2897 : : ojcinfo);
6804 2898 : 14276 : return;
2899 : : }
950 2900 [ + + ]: 721 : if (sjinfo->jointype == JOIN_FULL)
2901 : : {
2902 : : /* FULL JOIN (above tests cannot match in this case) */
2903 : 623 : OuterJoinClauseInfo *ojcinfo = makeNode(OuterJoinClauseInfo);
2904 : :
2905 : 623 : ojcinfo->rinfo = restrictinfo;
2906 : 623 : ojcinfo->sjinfo = sjinfo;
7371 2907 : 623 : root->full_join_clauses = lappend(root->full_join_clauses,
2908 : : ojcinfo);
6804 2909 : 623 : return;
2910 : : }
2911 : : /* nope, so fall through to distribute_restrictinfo_to_rels */
2912 : : }
2913 : : else
2914 : : {
2915 : : /* we still need to set up left_ec/right_ec */
5426 2916 : 352 : initialize_mergeclause_eclasses(root, restrictinfo);
2917 : : }
2918 : : }
2919 : :
2920 : : /* No EC special case applies, so push it into the clause lists */
6804 2921 : 85391 : distribute_restrictinfo_to_rels(root, restrictinfo);
2922 : : }
2923 : :
2924 : : /*
2925 : : * check_redundant_nullability_qual
2926 : : * Check to see if the qual is an IS NULL qual that is redundant with
2927 : : * a lower JOIN_ANTI join.
2928 : : *
2929 : : * We want to suppress redundant IS NULL quals, not so much to save cycles
2930 : : * as to avoid generating bogus selectivity estimates for them. So if
2931 : : * redundancy is detected here, distribute_qual_to_rels() just throws away
2932 : : * the qual.
2933 : : */
2934 : : static bool
6232 2935 : 235652 : check_redundant_nullability_qual(PlannerInfo *root, Node *clause)
2936 : : {
2937 : : Var *forced_null_var;
2938 : : ListCell *lc;
2939 : :
2940 : : /* Check for IS NULL, and identify the Var forced to NULL */
2941 : 235652 : forced_null_var = find_forced_null_var(clause);
2942 [ + + ]: 235652 : if (forced_null_var == NULL)
2943 : 234299 : return false;
2944 : :
2945 : : /*
2946 : : * If the Var comes from the nullable side of a lower antijoin, the IS
2947 : : * NULL condition is necessarily true. If it's not nulled by anything,
2948 : : * there is no point in searching the join_info_list. Otherwise, we need
2949 : : * to find out whether the nulling rel is an antijoin.
2950 : : */
950 2951 [ + + ]: 1353 : if (forced_null_var->varnullingrels == NULL)
2952 : 723 : return false;
2953 : :
6232 2954 [ + - + + : 705 : foreach(lc, root->join_info_list)
+ + ]
2955 : : {
2956 : 652 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
2957 : :
2958 : : /*
2959 : : * This test will not succeed if sjinfo->ojrelid is zero, which is
2960 : : * possible for an antijoin that was converted from a semijoin; but in
2961 : : * such a case the Var couldn't have come from its nullable side.
2962 : : */
950 2963 [ + + + - : 1229 : if (sjinfo->jointype == JOIN_ANTI && sjinfo->ojrelid != 0 &&
+ - ]
2964 : 577 : bms_is_member(sjinfo->ojrelid, forced_null_var->varnullingrels))
6042 2965 : 577 : return true;
2966 : : }
2967 : :
2968 : 53 : return false;
2969 : : }
2970 : :
2971 : : /*
2972 : : * add_base_clause_to_rel
2973 : : * Add 'restrictinfo' as a baserestrictinfo to the base relation denoted
2974 : : * by 'relid'. We offer some simple prechecks to try to determine if the
2975 : : * qual is always true, in which case we ignore it rather than add it.
2976 : : * If we detect the qual is always false, we replace it with
2977 : : * constant-FALSE.
2978 : : */
2979 : : static void
592 drowley@postgresql.o 2980 : 198197 : add_base_clause_to_rel(PlannerInfo *root, Index relid,
2981 : : RestrictInfo *restrictinfo)
2982 : : {
2983 : 198197 : RelOptInfo *rel = find_base_rel(root, relid);
512 2984 : 198197 : RangeTblEntry *rte = root->simple_rte_array[relid];
2985 : :
592 2986 [ - + ]: 198197 : Assert(bms_membership(restrictinfo->required_relids) == BMS_SINGLETON);
2987 : :
2988 : : /*
2989 : : * For inheritance parent tables, we must always record the RestrictInfo
2990 : : * in baserestrictinfo as is. If we were to transform or skip adding it,
2991 : : * then the original wouldn't be available in apply_child_basequals. Since
2992 : : * there are two RangeTblEntries for inheritance parents, one with
2993 : : * inh==true and the other with inh==false, we're still able to apply this
2994 : : * optimization to the inh==false one. The inh==true one is what
2995 : : * apply_child_basequals() sees, whereas the inh==false one is what's used
2996 : : * for the scan node in the final plan.
2997 : : *
2998 : : * We make an exception to this for partitioned tables. For these, we
2999 : : * always apply the constant-TRUE and constant-FALSE transformations. A
3000 : : * qual which is either of these for a partitioned table must also be that
3001 : : * for all of its child partitions.
3002 : : */
512 3003 [ + + + + ]: 198197 : if (!rte->inh || rte->relkind == RELKIND_PARTITIONED_TABLE)
3004 : : {
3005 : : /* Don't add the clause if it is always true */
3006 [ + + ]: 197197 : if (restriction_is_always_true(root, restrictinfo))
3007 : 228 : return;
3008 : :
3009 : : /*
3010 : : * Substitute the origin qual with constant-FALSE if it is provably
3011 : : * always false.
3012 : : *
3013 : : * Note that we need to keep the same rinfo_serial, since it is in
3014 : : * practice the same condition. We also need to reset the
3015 : : * last_rinfo_serial counter, which is essential to ensure that the
3016 : : * RestrictInfos for the "same" qual condition get identical serial
3017 : : * numbers (see deconstruct_distribute_oj_quals).
3018 : : */
3019 [ - + ]: 196969 : if (restriction_is_always_false(root, restrictinfo))
3020 : : {
512 drowley@postgresql.o 3021 :LBC (21) : int save_rinfo_serial = restrictinfo->rinfo_serial;
302 rguo@postgresql.org 3022 : (21) : int save_last_rinfo_serial = root->last_rinfo_serial;
3023 : :
512 drowley@postgresql.o 3024 : (21) : restrictinfo = make_restrictinfo(root,
3025 : (21) : (Expr *) makeBoolConst(false, false),
3026 : (21) : restrictinfo->is_pushed_down,
3027 : (21) : restrictinfo->has_clone,
3028 : (21) : restrictinfo->is_clone,
3029 : (21) : restrictinfo->pseudoconstant,
3030 : : 0, /* security_level */
3031 : : restrictinfo->required_relids,
3032 : : restrictinfo->incompatible_relids,
3033 : : restrictinfo->outer_relids);
3034 : (21) : restrictinfo->rinfo_serial = save_rinfo_serial;
302 rguo@postgresql.org 3035 : (21) : root->last_rinfo_serial = save_last_rinfo_serial;
3036 : : }
3037 : : }
3038 : :
3039 : : /* Add clause to rel's restriction list */
592 drowley@postgresql.o 3040 :CBC 197969 : rel->baserestrictinfo = lappend(rel->baserestrictinfo, restrictinfo);
3041 : :
3042 : : /* Update security level info */
3043 : 197969 : rel->baserestrict_min_security = Min(rel->baserestrict_min_security,
3044 : : restrictinfo->security_level);
3045 : : }
3046 : :
3047 : : /*
3048 : : * expr_is_nonnullable
3049 : : * Check to see if the Expr cannot be NULL
3050 : : *
3051 : : * Currently we only support simple Vars.
3052 : : */
3053 : : static bool
3054 : 5567 : expr_is_nonnullable(PlannerInfo *root, Expr *expr)
3055 : : {
3056 : : /* For now only check simple Vars */
3057 [ + + ]: 5567 : if (!IsA(expr, Var))
3058 : 337 : return false;
3059 : :
46 rguo@postgresql.org 3060 :GNC 5230 : return var_is_nonnullable(root, (Var *) expr, true);
3061 : : }
3062 : :
3063 : : /*
3064 : : * restriction_is_always_true
3065 : : * Check to see if the RestrictInfo is always true.
3066 : : *
3067 : : * Currently we only check for NullTest quals and OR clauses that include
3068 : : * NullTest quals. We may extend it in the future.
3069 : : */
3070 : : bool
592 drowley@postgresql.o 3071 :CBC 255807 : restriction_is_always_true(PlannerInfo *root,
3072 : : RestrictInfo *restrictinfo)
3073 : : {
3074 : : /*
3075 : : * For a clone clause, we don't have a reliable way to determine if the
3076 : : * input expression of a NullTest is non-nullable: nullingrel bits in
3077 : : * clone clauses may not reflect reality, so we dare not draw conclusions
3078 : : * from clones about whether Vars are guaranteed not-null.
3079 : : */
186 rguo@postgresql.org 3080 [ + + + + ]: 255807 : if (restrictinfo->has_clone || restrictinfo->is_clone)
3081 : 5440 : return false;
3082 : :
3083 : : /* Check for NullTest qual */
592 drowley@postgresql.o 3084 [ + + ]: 250367 : if (IsA(restrictinfo->clause, NullTest))
3085 : : {
3086 : 5905 : NullTest *nulltest = (NullTest *) restrictinfo->clause;
3087 : :
3088 : : /* is this NullTest an IS_NOT_NULL qual? */
3089 [ + + ]: 5905 : if (nulltest->nulltesttype != IS_NOT_NULL)
3090 : 1519 : return false;
3091 : :
3092 : : /*
3093 : : * Empty rows can appear NULL in some contexts and NOT NULL in others,
3094 : : * so avoid this optimization for row expressions.
3095 : : */
152 bruce@momjian.us 3096 [ + + ]: 4386 : if (nulltest->argisrow)
3097 : 78 : return false;
3098 : :
592 drowley@postgresql.o 3099 : 4308 : return expr_is_nonnullable(root, nulltest->arg);
3100 : : }
3101 : :
3102 : : /* If it's an OR, check its sub-clauses */
3103 [ + + ]: 244462 : if (restriction_is_or_clause(restrictinfo))
3104 : : {
3105 : : ListCell *lc;
3106 : :
3107 [ - + ]: 4623 : Assert(is_orclause(restrictinfo->orclause));
3108 : :
3109 : : /*
3110 : : * if any of the given OR branches is provably always true then the
3111 : : * entire condition is true.
3112 : : */
3113 [ + - + + : 15439 : foreach(lc, ((BoolExpr *) restrictinfo->orclause)->args)
+ + ]
3114 : : {
3115 : 10816 : Node *orarg = (Node *) lfirst(lc);
3116 : :
3117 [ + + ]: 10816 : if (!IsA(orarg, RestrictInfo))
3118 : 1547 : continue;
3119 : :
3120 [ - + ]: 9269 : if (restriction_is_always_true(root, (RestrictInfo *) orarg))
592 drowley@postgresql.o 3121 :LBC (6) : return true;
3122 : : }
3123 : : }
3124 : :
592 drowley@postgresql.o 3125 :CBC 244462 : return false;
3126 : : }
3127 : :
3128 : : /*
3129 : : * restriction_is_always_false
3130 : : * Check to see if the RestrictInfo is always false.
3131 : : *
3132 : : * Currently we only check for NullTest quals and OR clauses that include
3133 : : * NullTest quals. We may extend it in the future.
3134 : : */
3135 : : bool
3136 : 250215 : restriction_is_always_false(PlannerInfo *root,
3137 : : RestrictInfo *restrictinfo)
3138 : : {
3139 : : /*
3140 : : * For a clone clause, we don't have a reliable way to determine if the
3141 : : * input expression of a NullTest is non-nullable: nullingrel bits in
3142 : : * clone clauses may not reflect reality, so we dare not draw conclusions
3143 : : * from clones about whether Vars are guaranteed not-null.
3144 : : */
186 rguo@postgresql.org 3145 [ + + + + ]: 250215 : if (restrictinfo->has_clone || restrictinfo->is_clone)
3146 : 5440 : return false;
3147 : :
3148 : : /* Check for NullTest qual */
592 drowley@postgresql.o 3149 [ + + ]: 244775 : if (IsA(restrictinfo->clause, NullTest))
3150 : : {
3151 : 5080 : NullTest *nulltest = (NullTest *) restrictinfo->clause;
3152 : :
3153 : : /* is this NullTest an IS_NULL qual? */
3154 [ + + ]: 5080 : if (nulltest->nulltesttype != IS_NULL)
3155 : 3761 : return false;
3156 : :
3157 : : /*
3158 : : * Empty rows can appear NULL in some contexts and NOT NULL in others,
3159 : : * so avoid this optimization for row expressions.
3160 : : */
152 bruce@momjian.us 3161 [ + + ]: 1319 : if (nulltest->argisrow)
3162 : 60 : return false;
3163 : :
592 drowley@postgresql.o 3164 : 1259 : return expr_is_nonnullable(root, nulltest->arg);
3165 : : }
3166 : :
3167 : : /* If it's an OR, check its sub-clauses */
3168 [ + + ]: 239695 : if (restriction_is_or_clause(restrictinfo))
3169 : : {
3170 : : ListCell *lc;
3171 : :
3172 [ - + ]: 4623 : Assert(is_orclause(restrictinfo->orclause));
3173 : :
3174 : : /*
3175 : : * Currently, when processing OR expressions, we only return true when
3176 : : * all of the OR branches are always false. This could perhaps be
3177 : : * expanded to remove OR branches that are provably false. This may
3178 : : * be a useful thing to do as it could result in the OR being left
3179 : : * with a single arg. That's useful as it would allow the OR
3180 : : * condition to be replaced with its single argument which may allow
3181 : : * use of an index for faster filtering on the remaining condition.
3182 : : */
3183 [ + - + - : 4623 : foreach(lc, ((BoolExpr *) restrictinfo->orclause)->args)
+ - ]
3184 : : {
3185 : 4623 : Node *orarg = (Node *) lfirst(lc);
3186 : :
3187 [ + + ]: 4623 : if (!IsA(orarg, RestrictInfo) ||
3188 [ + - ]: 3905 : !restriction_is_always_false(root, (RestrictInfo *) orarg))
3189 : 4623 : return false;
3190 : : }
592 drowley@postgresql.o 3191 :LBC (6) : return true;
3192 : : }
3193 : :
592 drowley@postgresql.o 3194 :CBC 235072 : return false;
3195 : : }
3196 : :
3197 : : /*
3198 : : * distribute_restrictinfo_to_rels
3199 : : * Push a completed RestrictInfo into the proper restriction or join
3200 : : * clause list(s).
3201 : : *
3202 : : * This is the last step of distribute_qual_to_rels() for ordinary qual
3203 : : * clauses. Clauses that are interesting for equivalence-class processing
3204 : : * are diverted to the EC machinery, but may ultimately get fed back here.
3205 : : */
3206 : : void
6804 tgl@sss.pgh.pa.us 3207 : 232849 : distribute_restrictinfo_to_rels(PlannerInfo *root,
3208 : : RestrictInfo *restrictinfo)
3209 : : {
3210 : 232849 : Relids relids = restrictinfo->required_relids;
3211 : :
648 drowley@postgresql.o 3212 [ + - ]: 232849 : if (!bms_is_empty(relids))
3213 : : {
3214 : : int relid;
3215 : :
3216 [ + + ]: 232849 : if (bms_get_singleton_member(relids, &relid))
3217 : : {
3218 : : /*
3219 : : * There is only one relation participating in the clause, so it
3220 : : * is a restriction clause for that relation.
3221 : : */
592 3222 : 198197 : add_base_clause_to_rel(root, relid, restrictinfo);
3223 : : }
3224 : : else
3225 : : {
3226 : : /*
3227 : : * The clause is a join clause, since there is more than one rel
3228 : : * in its relid set.
3229 : : */
3230 : :
3231 : : /*
3232 : : * Check for hashjoinable operators. (We don't bother setting the
3233 : : * hashjoin info except in true join clauses.)
3234 : : */
5364 tgl@sss.pgh.pa.us 3235 : 34652 : check_hashjoinable(restrictinfo);
3236 : :
3237 : : /*
3238 : : * Likewise, check if the clause is suitable to be used with a
3239 : : * Memoize node to cache inner tuples during a parameterized
3240 : : * nested loop.
3241 : : */
1515 drowley@postgresql.o 3242 : 34652 : check_memoizable(restrictinfo);
3243 : :
3244 : : /*
3245 : : * Add clause to the join lists of all the relevant relations.
3246 : : */
6804 tgl@sss.pgh.pa.us 3247 : 34652 : add_join_clause_to_rels(root, restrictinfo, relids);
3248 : : }
3249 : : }
3250 : : else
3251 : : {
3252 : : /*
3253 : : * clause references no rels, and therefore we have no place to attach
3254 : : * it. Shouldn't get here if callers are working properly.
3255 : : */
648 drowley@postgresql.o 3256 [ # # ]:UBC 0 : elog(ERROR, "cannot cope with variable-free clause");
3257 : : }
6804 tgl@sss.pgh.pa.us 3258 :CBC 232849 : }
3259 : :
3260 : : /*
3261 : : * process_implied_equality
3262 : : * Create a restrictinfo item that says "item1 op item2", and push it
3263 : : * into the appropriate lists. (In practice opno is always a btree
3264 : : * equality operator.)
3265 : : *
3266 : : * "qualscope" is the nominal syntactic level to impute to the restrictinfo.
3267 : : * This must contain at least all the rels used in the expressions, but it
3268 : : * is used only to set the qual application level when both exprs are
3269 : : * variable-free. (Hence, it should usually match the join domain in which
3270 : : * the clause applies.) Otherwise the qual is applied at the lowest join
3271 : : * level that provides all its variables.
3272 : : *
3273 : : * "security_level" is the security level to assign to the new restrictinfo.
3274 : : *
3275 : : * "both_const" indicates whether both items are known pseudo-constant;
3276 : : * in this case it is worth applying eval_const_expressions() in case we
3277 : : * can produce constant TRUE or constant FALSE. (Otherwise it's not,
3278 : : * because the expressions went through eval_const_expressions already.)
3279 : : *
3280 : : * Returns the generated RestrictInfo, if any. The result will be NULL
3281 : : * if both_const is true and we successfully reduced the clause to
3282 : : * constant TRUE.
3283 : : *
3284 : : * Note: this function will copy item1 and item2, but it is caller's
3285 : : * responsibility to make sure that the Relids parameters are fresh copies
3286 : : * not shared with other uses.
3287 : : *
3288 : : * Note: we do not do initialize_mergeclause_eclasses() here. It is
3289 : : * caller's responsibility that left_ec/right_ec be set as necessary.
3290 : : */
3291 : : RestrictInfo *
3292 : 18705 : process_implied_equality(PlannerInfo *root,
3293 : : Oid opno,
3294 : : Oid collation,
3295 : : Expr *item1,
3296 : : Expr *item2,
3297 : : Relids qualscope,
3298 : : Index security_level,
3299 : : bool both_const)
3300 : : {
3301 : : RestrictInfo *restrictinfo;
3302 : : Node *clause;
3303 : : Relids relids;
1774 3304 : 18705 : bool pseudoconstant = false;
3305 : :
3306 : : /*
3307 : : * Build the new clause. Copy to ensure it shares no substructure with
3308 : : * original (this is necessary in case there are subselects in there...)
3309 : : */
3310 : 18705 : clause = (Node *) make_opclause(opno,
3311 : : BOOLOID, /* opresulttype */
3312 : : false, /* opretset */
3313 : 18705 : copyObject(item1),
3314 : 18705 : copyObject(item2),
3315 : : InvalidOid,
3316 : : collation);
3317 : :
3318 : : /* If both constant, try to reduce to a boolean constant. */
6804 3319 [ + + ]: 18705 : if (both_const)
3320 : : {
1774 3321 : 66 : clause = eval_const_expressions(root, clause);
3322 : :
3323 : : /* If we produced const TRUE, just drop the clause */
6804 3324 [ + - + + ]: 66 : if (clause && IsA(clause, Const))
3325 : : {
6505 bruce@momjian.us 3326 : 63 : Const *cclause = (Const *) clause;
3327 : :
6804 tgl@sss.pgh.pa.us 3328 [ - + ]: 63 : Assert(cclause->consttype == BOOLOID);
3329 [ + - - + ]: 63 : if (!cclause->constisnull && DatumGetBool(cclause->constvalue))
1774 tgl@sss.pgh.pa.us 3330 :UBC 0 : return NULL;
3331 : : }
3332 : : }
3333 : :
3334 : : /*
3335 : : * The rest of this is a very cut-down version of distribute_qual_to_rels.
3336 : : * We can skip most of the work therein, but there are a couple of special
3337 : : * cases we still have to handle.
3338 : : *
3339 : : * Retrieve all relids mentioned within the possibly-simplified clause.
3340 : : */
1689 tgl@sss.pgh.pa.us 3341 :CBC 18705 : relids = pull_varnos(root, clause);
1774 3342 [ - + ]: 18705 : Assert(bms_is_subset(relids, qualscope));
3343 : :
3344 : : /*
3345 : : * If the clause is variable-free, our normal heuristic for pushing it
3346 : : * down to just the mentioned rels doesn't work, because there are none.
3347 : : * Apply it as a gating qual at the appropriate level (see comments for
3348 : : * get_join_domain_min_rels).
3349 : : */
3350 [ + + ]: 18705 : if (bms_is_empty(relids))
3351 : : {
3352 : : /* eval at join domain's safe level */
927 3353 : 66 : relids = get_join_domain_min_rels(root, qualscope);
3354 : : /* mark as gating qual */
950 3355 : 66 : pseudoconstant = true;
3356 : : /* tell createplan.c to check for gating quals */
3357 : 66 : root->hasPseudoConstantQuals = true;
3358 : : }
3359 : :
3360 : : /*
3361 : : * Build the RestrictInfo node itself.
3362 : : */
1689 3363 : 18705 : restrictinfo = make_restrictinfo(root,
3364 : : (Expr *) clause,
3365 : : true, /* is_pushed_down */
3366 : : false, /* !has_clone */
3367 : : false, /* !is_clone */
3368 : : pseudoconstant,
3369 : : security_level,
3370 : : relids,
3371 : : NULL, /* incompatible_relids */
3372 : : NULL); /* outer_relids */
3373 : :
3374 : : /*
3375 : : * If it's a join clause, add vars used in the clause to targetlists of
3376 : : * their relations, so that they will be emitted by the plan nodes that
3377 : : * scan those relations (else they won't be available at the join node!).
3378 : : *
3379 : : * Typically, we'd have already done this when the component expressions
3380 : : * were first seen by distribute_qual_to_rels; but it is possible that
3381 : : * some of the Vars could have missed having that done because they only
3382 : : * appeared in single-relation clauses originally. So do it here for
3383 : : * safety.
3384 : : *
3385 : : * See also rebuild_joinclause_attr_needed, which has to partially repeat
3386 : : * this work after removal of an outer join. (Since we will put this
3387 : : * clause into the joininfo lists, that function needn't do any extra work
3388 : : * to find it.)
3389 : : */
1774 3390 [ + + ]: 18705 : if (bms_membership(relids) == BMS_MULTIPLE)
3391 : : {
3392 : 30 : List *vars = pull_var_clause(clause,
3393 : : PVC_RECURSE_AGGREGATES |
3394 : : PVC_RECURSE_WINDOWFUNCS |
3395 : : PVC_INCLUDE_PLACEHOLDERS);
3396 : :
1116 3397 : 30 : add_vars_to_targetlist(root, vars, relids);
1774 3398 : 30 : list_free(vars);
3399 : : }
3400 : :
3401 : : /*
3402 : : * Check mergejoinability. This will usually succeed, since the op came
3403 : : * from an EquivalenceClass; but we could have reduced the original clause
3404 : : * to a constant.
3405 : : */
3406 : 18705 : check_mergejoinable(restrictinfo);
3407 : :
3408 : : /*
3409 : : * Note we don't do initialize_mergeclause_eclasses(); the caller can
3410 : : * handle that much more cheaply than we can. It's okay to call
3411 : : * distribute_restrictinfo_to_rels() before that happens.
3412 : : */
3413 : :
3414 : : /*
3415 : : * Push the new clause into all the appropriate restrictinfo lists.
3416 : : */
3417 : 18705 : distribute_restrictinfo_to_rels(root, restrictinfo);
3418 : :
3419 : 18705 : return restrictinfo;
3420 : : }
3421 : :
3422 : : /*
3423 : : * build_implied_join_equality --- build a RestrictInfo for a derived equality
3424 : : *
3425 : : * This overlaps the functionality of process_implied_equality(), but we
3426 : : * must not push the RestrictInfo into the joininfo tree.
3427 : : *
3428 : : * Note: this function will copy item1 and item2, but it is caller's
3429 : : * responsibility to make sure that the Relids parameters are fresh copies
3430 : : * not shared with other uses.
3431 : : *
3432 : : * Note: we do not do initialize_mergeclause_eclasses() here. It is
3433 : : * caller's responsibility that left_ec/right_ec be set as necessary.
3434 : : */
3435 : : RestrictInfo *
1689 3436 : 36918 : build_implied_join_equality(PlannerInfo *root,
3437 : : Oid opno,
3438 : : Oid collation,
3439 : : Expr *item1,
3440 : : Expr *item2,
3441 : : Relids qualscope,
3442 : : Index security_level)
3443 : : {
3444 : : RestrictInfo *restrictinfo;
3445 : : Expr *clause;
3446 : :
3447 : : /*
3448 : : * Build the new clause. Copy to ensure it shares no substructure with
3449 : : * original (this is necessary in case there are subselects in there...)
3450 : : */
6804 3451 : 36918 : clause = make_opclause(opno,
3452 : : BOOLOID, /* opresulttype */
3453 : : false, /* opretset */
3103 peter_e@gmx.net 3454 : 36918 : copyObject(item1),
3455 : 36918 : copyObject(item2),
3456 : : InvalidOid,
3457 : : collation);
3458 : :
3459 : : /*
3460 : : * Build the RestrictInfo node itself.
3461 : : */
1689 tgl@sss.pgh.pa.us 3462 : 36918 : restrictinfo = make_restrictinfo(root,
3463 : : clause,
3464 : : true, /* is_pushed_down */
3465 : : false, /* !has_clone */
3466 : : false, /* !is_clone */
3467 : : false, /* pseudoconstant */
3468 : : security_level, /* security_level */
3469 : : qualscope, /* required_relids */
3470 : : NULL, /* incompatible_relids */
3471 : : NULL); /* outer_relids */
3472 : :
3473 : : /* Set mergejoinability/hashjoinability flags */
6804 3474 : 36918 : check_mergejoinable(restrictinfo);
5364 3475 : 36918 : check_hashjoinable(restrictinfo);
1515 drowley@postgresql.o 3476 : 36918 : check_memoizable(restrictinfo);
3477 : :
6804 tgl@sss.pgh.pa.us 3478 : 36918 : return restrictinfo;
3479 : : }
3480 : :
3481 : : /*
3482 : : * get_join_domain_min_rels
3483 : : * Identify the appropriate join level for derived quals belonging
3484 : : * to the join domain with the given relids.
3485 : : *
3486 : : * When we derive a pseudoconstant (Var-free) clause from an EquivalenceClass,
3487 : : * we'd ideally apply the clause at the top level of the EC's join domain.
3488 : : * However, if there are any outer joins inside that domain that get commuted
3489 : : * with joins outside it, that leads to not finding a correct place to apply
3490 : : * the clause. Instead, remove any lower outer joins from the relid set,
3491 : : * and apply the clause to just the remaining rels. This still results in a
3492 : : * correct answer, since if the clause produces FALSE then the LHS of these
3493 : : * joins will be empty leading to an empty join result.
3494 : : *
3495 : : * However, there's no need to remove outer joins if this is the top-level
3496 : : * join domain of the query, since then there's nothing else to commute with.
3497 : : *
3498 : : * Note: it's tempting to use this in distribute_qual_to_rels where it's
3499 : : * dealing with pseudoconstant quals; but we can't because the necessary
3500 : : * SpecialJoinInfos aren't all formed at that point.
3501 : : *
3502 : : * The result is always freshly palloc'd; we do not modify domain_relids.
3503 : : */
3504 : : static Relids
927 3505 : 66 : get_join_domain_min_rels(PlannerInfo *root, Relids domain_relids)
3506 : : {
3507 : 66 : Relids result = bms_copy(domain_relids);
3508 : : ListCell *lc;
3509 : :
3510 : : /* Top-level join domain? */
3511 [ + + ]: 66 : if (bms_equal(result, root->all_query_rels))
3512 : 33 : return result;
3513 : :
3514 : : /* Nope, look for lower outer joins that could potentially commute out */
3515 [ + - + + : 69 : foreach(lc, root->join_info_list)
+ + ]
3516 : : {
3517 : 36 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
3518 : :
3519 [ + - + + ]: 72 : if (sjinfo->jointype == JOIN_LEFT &&
3520 : 36 : bms_is_member(sjinfo->ojrelid, result))
3521 : : {
3522 : 3 : result = bms_del_member(result, sjinfo->ojrelid);
3523 : 3 : result = bms_del_members(result, sjinfo->syn_righthand);
3524 : : }
3525 : : }
3526 : 33 : return result;
3527 : : }
3528 : :
3529 : :
3530 : : /*
3531 : : * rebuild_joinclause_attr_needed
3532 : : * Put back attr_needed bits for Vars/PHVs needed for join clauses.
3533 : : *
3534 : : * This is used to rebuild attr_needed/ph_needed sets after removal of a
3535 : : * useless outer join. It should match what distribute_qual_to_rels did,
3536 : : * except that we call add_vars_to_attr_needed not add_vars_to_targetlist.
3537 : : */
3538 : : void
344 3539 : 5583 : rebuild_joinclause_attr_needed(PlannerInfo *root)
3540 : : {
3541 : : /*
3542 : : * We must examine all join clauses, but there's no value in processing
3543 : : * any join clause more than once. So it's slightly annoying that we have
3544 : : * to find them via the per-base-relation joininfo lists. Avoid duplicate
3545 : : * processing by tracking the rinfo_serial numbers of join clauses we've
3546 : : * already seen. (This doesn't work for is_clone clauses, so we must
3547 : : * waste effort on them.)
3548 : : */
3549 : 5583 : Bitmapset *seen_serials = NULL;
3550 : : Index rti;
3551 : :
3552 : : /* Scan all baserels for join clauses */
3553 [ + + ]: 35656 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
3554 : : {
3555 : 30073 : RelOptInfo *brel = root->simple_rel_array[rti];
3556 : : ListCell *lc;
3557 : :
3558 [ + + ]: 30073 : if (brel == NULL)
3559 : 20433 : continue;
3560 [ - + ]: 9640 : if (brel->reloptkind != RELOPT_BASEREL)
344 tgl@sss.pgh.pa.us 3561 :UBC 0 : continue;
3562 : :
344 tgl@sss.pgh.pa.us 3563 [ + + + + :CBC 14528 : foreach(lc, brel->joininfo)
+ + ]
3564 : : {
3565 : 4888 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3566 : 4888 : Relids relids = rinfo->required_relids;
3567 : :
3568 [ + + ]: 4888 : if (!rinfo->is_clone) /* else serial number is not unique */
3569 : : {
3570 [ + + ]: 4840 : if (bms_is_member(rinfo->rinfo_serial, seen_serials))
3571 : 2597 : continue; /* saw it already */
3572 : 2243 : seen_serials = bms_add_member(seen_serials,
3573 : : rinfo->rinfo_serial);
3574 : : }
3575 : :
3576 [ + - ]: 2291 : if (bms_membership(relids) == BMS_MULTIPLE)
3577 : : {
3578 : 2291 : List *vars = pull_var_clause((Node *) rinfo->clause,
3579 : : PVC_RECURSE_AGGREGATES |
3580 : : PVC_RECURSE_WINDOWFUNCS |
3581 : : PVC_INCLUDE_PLACEHOLDERS);
3582 : : Relids where_needed;
3583 : :
3584 [ + + ]: 2291 : if (rinfo->is_clone)
3585 : 48 : where_needed = bms_intersect(relids, root->all_baserels);
3586 : : else
3587 : 2243 : where_needed = relids;
3588 : 2291 : add_vars_to_attr_needed(root, vars, where_needed);
3589 : 2291 : list_free(vars);
3590 : : }
3591 : : }
3592 : : }
3593 : 5583 : }
3594 : :
3595 : :
3596 : : /*
3597 : : * match_foreign_keys_to_quals
3598 : : * Match foreign-key constraints to equivalence classes and join quals
3599 : : *
3600 : : * The idea here is to see which query join conditions match equality
3601 : : * constraints of a foreign-key relationship. For such join conditions,
3602 : : * we can use the FK semantics to make selectivity estimates that are more
3603 : : * reliable than estimating from statistics, especially for multiple-column
3604 : : * FKs, where the normal assumption of independent conditions tends to fail.
3605 : : *
3606 : : * In this function we annotate the ForeignKeyOptInfos in root->fkey_list
3607 : : * with info about which eclasses and join qual clauses they match, and
3608 : : * discard any ForeignKeyOptInfos that are irrelevant for the query.
3609 : : */
3610 : : void
3367 3611 : 159350 : match_foreign_keys_to_quals(PlannerInfo *root)
3612 : : {
3613 : 159350 : List *newlist = NIL;
3614 : : ListCell *lc;
3615 : :
3616 [ + + + + : 160240 : foreach(lc, root->fkey_list)
+ + ]
3617 : : {
3618 : 890 : ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
3619 : : RelOptInfo *con_rel;
3620 : : RelOptInfo *ref_rel;
3621 : : int colno;
3622 : :
3623 : : /*
3624 : : * Either relid might identify a rel that is in the query's rtable but
3625 : : * isn't referenced by the jointree, or has been removed by join
3626 : : * removal, so that it won't have a RelOptInfo. Hence don't use
3627 : : * find_base_rel() here. We can ignore such FKs.
3628 : : */
3356 3629 [ + - ]: 890 : if (fkinfo->con_relid >= root->simple_rel_array_size ||
3630 [ - + ]: 890 : fkinfo->ref_relid >= root->simple_rel_array_size)
3356 tgl@sss.pgh.pa.us 3631 :UBC 0 : continue; /* just paranoia */
3356 tgl@sss.pgh.pa.us 3632 :CBC 890 : con_rel = root->simple_rel_array[fkinfo->con_relid];
3633 [ + + ]: 890 : if (con_rel == NULL)
3634 : 6 : continue;
3635 : 884 : ref_rel = root->simple_rel_array[fkinfo->ref_relid];
3636 [ + + ]: 884 : if (ref_rel == NULL)
3637 : 12 : continue;
3638 : :
3639 : : /*
3640 : : * Ignore FK unless both rels are baserels. This gets rid of FKs that
3641 : : * link to inheritance child rels (otherrels).
3642 : : */
3367 3643 [ + - ]: 872 : if (con_rel->reloptkind != RELOPT_BASEREL ||
3644 [ - + ]: 872 : ref_rel->reloptkind != RELOPT_BASEREL)
3367 tgl@sss.pgh.pa.us 3645 :UBC 0 : continue;
3646 : :
3647 : : /*
3648 : : * Scan the columns and try to match them to eclasses and quals.
3649 : : *
3650 : : * Note: for simple inner joins, any match should be in an eclass.
3651 : : * "Loose" quals that syntactically match an FK equality must have
3652 : : * been rejected for EC status because they are outer-join quals or
3653 : : * similar. We can still consider them to match the FK.
3654 : : */
3367 tgl@sss.pgh.pa.us 3655 [ + + ]:CBC 2022 : for (colno = 0; colno < fkinfo->nkeys; colno++)
3656 : : {
3657 : : EquivalenceClass *ec;
3658 : : AttrNumber con_attno,
3659 : : ref_attno;
3660 : : Oid fpeqop;
3661 : : ListCell *lc2;
3662 : :
1774 3663 : 1150 : ec = match_eclasses_to_foreign_key_col(root, fkinfo, colno);
3664 : : /* Don't bother looking for loose quals if we got an EC match */
3665 [ + + ]: 1150 : if (ec != NULL)
3666 : : {
3367 3667 : 171 : fkinfo->nmatched_ec++;
1774 3668 [ + + ]: 171 : if (ec->ec_has_const)
3669 : 37 : fkinfo->nconst_ec++;
3367 3670 : 171 : continue;
3671 : : }
3672 : :
3673 : : /*
3674 : : * Scan joininfo list for relevant clauses. Either rel's joininfo
3675 : : * list would do equally well; we use con_rel's.
3676 : : */
3677 : 979 : con_attno = fkinfo->conkey[colno];
3678 : 979 : ref_attno = fkinfo->confkey[colno];
3679 : 979 : fpeqop = InvalidOid; /* we'll look this up only if needed */
3680 : :
3681 [ + + + + : 2556 : foreach(lc2, con_rel->joininfo)
+ + ]
3682 : : {
3683 : 1577 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc2);
3684 : 1577 : OpExpr *clause = (OpExpr *) rinfo->clause;
3685 : : Var *leftvar;
3686 : : Var *rightvar;
3687 : :
3688 : : /* Only binary OpExprs are useful for consideration */
3689 [ + - - + ]: 3154 : if (!IsA(clause, OpExpr) ||
3690 : 1577 : list_length(clause->args) != 2)
3367 tgl@sss.pgh.pa.us 3691 :UBC 0 : continue;
3367 tgl@sss.pgh.pa.us 3692 :CBC 1577 : leftvar = (Var *) get_leftop((Expr *) clause);
3693 : 1577 : rightvar = (Var *) get_rightop((Expr *) clause);
3694 : :
3695 : : /* Operands must be Vars, possibly with RelabelType */
3696 [ + - + + ]: 1700 : while (leftvar && IsA(leftvar, RelabelType))
3697 : 123 : leftvar = (Var *) ((RelabelType *) leftvar)->arg;
3698 [ + - - + ]: 1577 : if (!(leftvar && IsA(leftvar, Var)))
3367 tgl@sss.pgh.pa.us 3699 :UBC 0 : continue;
3367 tgl@sss.pgh.pa.us 3700 [ + - + + ]:CBC 1691 : while (rightvar && IsA(rightvar, RelabelType))
3701 : 114 : rightvar = (Var *) ((RelabelType *) rightvar)->arg;
3702 [ + - + + ]: 1577 : if (!(rightvar && IsA(rightvar, Var)))
3703 : 15 : continue;
3704 : :
3705 : : /* Now try to match the vars to the current foreign key cols */
3706 [ + + ]: 1562 : if (fkinfo->ref_relid == leftvar->varno &&
3707 [ + + ]: 1499 : ref_attno == leftvar->varattno &&
3708 [ + - ]: 856 : fkinfo->con_relid == rightvar->varno &&
3709 [ + + ]: 856 : con_attno == rightvar->varattno)
3710 : : {
3711 : : /* Vars match, but is it the right operator? */
3712 [ + - ]: 817 : if (clause->opno == fkinfo->conpfeqop[colno])
3713 : : {
3714 : 817 : fkinfo->rinfos[colno] = lappend(fkinfo->rinfos[colno],
3715 : : rinfo);
3716 : 817 : fkinfo->nmatched_ri++;
3717 : : }
3718 : : }
3719 [ + + ]: 745 : else if (fkinfo->ref_relid == rightvar->varno &&
3720 [ + + ]: 45 : ref_attno == rightvar->varattno &&
3721 [ + - ]: 18 : fkinfo->con_relid == leftvar->varno &&
3722 [ + - ]: 18 : con_attno == leftvar->varattno)
3723 : : {
3724 : : /*
3725 : : * Reverse match, must check commutator operator. Look it
3726 : : * up if we didn't already. (In the worst case we might
3727 : : * do multiple lookups here, but that would require an FK
3728 : : * equality operator without commutator, which is
3729 : : * unlikely.)
3730 : : */
3731 [ + - ]: 18 : if (!OidIsValid(fpeqop))
3732 : 18 : fpeqop = get_commutator(fkinfo->conpfeqop[colno]);
3733 [ + - ]: 18 : if (clause->opno == fpeqop)
3734 : : {
3735 : 18 : fkinfo->rinfos[colno] = lappend(fkinfo->rinfos[colno],
3736 : : rinfo);
3737 : 18 : fkinfo->nmatched_ri++;
3738 : : }
3739 : : }
3740 : : }
3741 : : /* If we found any matching loose quals, count col as matched */
3742 [ + + ]: 979 : if (fkinfo->rinfos[colno])
3743 : 835 : fkinfo->nmatched_rcols++;
3744 : : }
3745 : :
3746 : : /*
3747 : : * Currently, we drop multicolumn FKs that aren't fully matched to the
3748 : : * query. Later we might figure out how to derive some sort of
3749 : : * estimate from them, in which case this test should be weakened to
3750 : : * "if ((fkinfo->nmatched_ec + fkinfo->nmatched_rcols) > 0)".
3751 : : */
3752 [ + + ]: 872 : if ((fkinfo->nmatched_ec + fkinfo->nmatched_rcols) == fkinfo->nkeys)
3753 : 740 : newlist = lappend(newlist, fkinfo);
3754 : : }
3755 : : /* Replace fkey_list, thereby discarding any useless entries */
3756 : 159350 : root->fkey_list = newlist;
3757 : 159350 : }
3758 : :
3759 : :
3760 : : /*****************************************************************************
3761 : : *
3762 : : * CHECKS FOR MERGEJOINABLE AND HASHJOINABLE CLAUSES
3763 : : *
3764 : : *****************************************************************************/
3765 : :
3766 : : /*
3767 : : * check_mergejoinable
3768 : : * If the restrictinfo's clause is mergejoinable, set the mergejoin
3769 : : * info fields in the restrictinfo.
3770 : : *
3771 : : * Currently, we support mergejoin for binary opclauses where
3772 : : * the operator is a mergejoinable operator. The arguments can be
3773 : : * anything --- as long as there are no volatile functions in them.
3774 : : */
3775 : : static void
9518 3776 : 319892 : check_mergejoinable(RestrictInfo *restrictinfo)
3777 : : {
3778 : 319892 : Expr *clause = restrictinfo->clause;
3779 : : Oid opno;
3780 : : Node *leftarg;
3781 : :
7007 3782 [ + + ]: 319892 : if (restrictinfo->pseudoconstant)
3783 : 5221 : return;
8304 3784 [ + + ]: 314671 : if (!is_opclause(clause))
9518 3785 : 40806 : return;
7769 neilc@samurai.com 3786 [ + + ]: 273865 : if (list_length(((OpExpr *) clause)->args) != 2)
9518 tgl@sss.pgh.pa.us 3787 : 12 : return;
3788 : :
8304 3789 : 273853 : opno = ((OpExpr *) clause)->opno;
5425 3790 : 273853 : leftarg = linitial(((OpExpr *) clause)->args);
3791 : :
3792 [ + + ]: 273853 : if (op_mergejoinable(opno, exprType(leftarg)) &&
1622 drowley@postgresql.o 3793 [ + + ]: 235032 : !contain_volatile_functions((Node *) restrictinfo))
6804 tgl@sss.pgh.pa.us 3794 : 235016 : restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);
3795 : :
3796 : : /*
3797 : : * Note: op_mergejoinable is just a hint; if we fail to find the operator
3798 : : * in any btree opfamilies, mergeopfamilies remains NIL and so the clause
3799 : : * is not treated as mergejoinable.
3800 : : */
3801 : : }
3802 : :
3803 : : /*
3804 : : * check_hashjoinable
3805 : : * If the restrictinfo's clause is hashjoinable, set the hashjoin
3806 : : * info fields in the restrictinfo.
3807 : : *
3808 : : * Currently, we support hashjoin for binary opclauses where
3809 : : * the operator is a hashjoinable operator. The arguments can be
3810 : : * anything --- as long as there are no volatile functions in them.
3811 : : */
3812 : : static void
9518 3813 : 71570 : check_hashjoinable(RestrictInfo *restrictinfo)
3814 : : {
3815 : 71570 : Expr *clause = restrictinfo->clause;
3816 : : Oid opno;
3817 : : Node *leftarg;
3818 : :
7007 3819 [ + + ]: 71570 : if (restrictinfo->pseudoconstant)
3820 : 1736 : return;
8304 3821 [ + + ]: 69834 : if (!is_opclause(clause))
9518 3822 : 3760 : return;
7769 neilc@samurai.com 3823 [ - + ]: 66074 : if (list_length(((OpExpr *) clause)->args) != 2)
9518 tgl@sss.pgh.pa.us 3824 :UBC 0 : return;
3825 : :
8304 tgl@sss.pgh.pa.us 3826 :CBC 66074 : opno = ((OpExpr *) clause)->opno;
5425 3827 : 66074 : leftarg = linitial(((OpExpr *) clause)->args);
3828 : :
3829 [ + + ]: 66074 : if (op_hashjoinable(opno, exprType(leftarg)) &&
1622 drowley@postgresql.o 3830 [ + + ]: 64392 : !contain_volatile_functions((Node *) restrictinfo))
9518 tgl@sss.pgh.pa.us 3831 : 64388 : restrictinfo->hashjoinoperator = opno;
3832 : : }
3833 : :
3834 : : /*
3835 : : * check_memoizable
3836 : : * If the restrictinfo's clause is suitable to be used for a Memoize node,
3837 : : * set the left_hasheqoperator and right_hasheqoperator to the hash equality
3838 : : * operator that will be needed during caching.
3839 : : */
3840 : : static void
1515 drowley@postgresql.o 3841 : 71570 : check_memoizable(RestrictInfo *restrictinfo)
3842 : : {
3843 : : TypeCacheEntry *typentry;
1618 3844 : 71570 : Expr *clause = restrictinfo->clause;
3845 : : Oid lefttype;
3846 : : Oid righttype;
3847 : :
3848 [ + + ]: 71570 : if (restrictinfo->pseudoconstant)
3849 : 1736 : return;
3850 [ + + ]: 69834 : if (!is_opclause(clause))
3851 : 3760 : return;
3852 [ - + ]: 66074 : if (list_length(((OpExpr *) clause)->args) != 2)
1618 drowley@postgresql.o 3853 :UBC 0 : return;
3854 : :
1398 drowley@postgresql.o 3855 :CBC 66074 : lefttype = exprType(linitial(((OpExpr *) clause)->args));
3856 : :
3857 : 66074 : typentry = lookup_type_cache(lefttype, TYPECACHE_HASH_PROC |
3858 : : TYPECACHE_EQ_OPR);
3859 : :
3860 [ + + + - ]: 66074 : if (OidIsValid(typentry->hash_proc) && OidIsValid(typentry->eq_opr))
3861 : 65870 : restrictinfo->left_hasheqoperator = typentry->eq_opr;
3862 : :
3863 : 66074 : righttype = exprType(lsecond(((OpExpr *) clause)->args));
3864 : :
3865 : : /*
3866 : : * Lookup the right type, unless it's the same as the left type, in which
3867 : : * case typentry is already pointing to the required TypeCacheEntry.
3868 : : */
3869 [ + + ]: 66074 : if (lefttype != righttype)
3870 : 978 : typentry = lookup_type_cache(righttype, TYPECACHE_HASH_PROC |
3871 : : TYPECACHE_EQ_OPR);
3872 : :
3873 [ + + + - ]: 66074 : if (OidIsValid(typentry->hash_proc) && OidIsValid(typentry->eq_opr))
3874 : 65768 : restrictinfo->right_hasheqoperator = typentry->eq_opr;
3875 : : }
|
