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