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