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