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