Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * initsplan.c
4 : * Target list, qualification, joininfo initialization routines
5 : *
6 : * Portions Copyright (c) 1996-2017, 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/nodeFuncs.h"
19 : #include "optimizer/clauses.h"
20 : #include "optimizer/cost.h"
21 : #include "optimizer/joininfo.h"
22 : #include "optimizer/pathnode.h"
23 : #include "optimizer/paths.h"
24 : #include "optimizer/placeholder.h"
25 : #include "optimizer/planmain.h"
26 : #include "optimizer/planner.h"
27 : #include "optimizer/prep.h"
28 : #include "optimizer/restrictinfo.h"
29 : #include "optimizer/var.h"
30 : #include "parser/analyze.h"
31 : #include "rewrite/rewriteManip.h"
32 : #include "utils/lsyscache.h"
33 :
34 :
35 : /* These parameters are set by GUC */
36 : int from_collapse_limit;
37 : int join_collapse_limit;
38 :
39 :
40 : /* Elements of the postponed_qual_list used during deconstruct_recurse */
41 : typedef struct PostponedQual
42 : {
43 : Node *qual; /* a qual clause waiting to be processed */
44 : Relids relids; /* the set of baserels it references */
45 : } PostponedQual;
46 :
47 :
48 : static void extract_lateral_references(PlannerInfo *root, RelOptInfo *brel,
49 : Index rtindex);
50 : static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode,
51 : bool below_outer_join,
52 : Relids *qualscope, Relids *inner_join_rels,
53 : List **postponed_qual_list);
54 : static void process_security_barrier_quals(PlannerInfo *root,
55 : int rti, Relids qualscope,
56 : bool below_outer_join);
57 : static SpecialJoinInfo *make_outerjoininfo(PlannerInfo *root,
58 : Relids left_rels, Relids right_rels,
59 : Relids inner_join_rels,
60 : JoinType jointype, List *clause);
61 : static void compute_semijoin_info(SpecialJoinInfo *sjinfo, List *clause);
62 : static void distribute_qual_to_rels(PlannerInfo *root, Node *clause,
63 : bool is_deduced,
64 : bool below_outer_join,
65 : JoinType jointype,
66 : Index security_level,
67 : Relids qualscope,
68 : Relids ojscope,
69 : Relids outerjoin_nonnullable,
70 : Relids deduced_nullable_relids,
71 : List **postponed_qual_list);
72 : static bool check_outerjoin_delay(PlannerInfo *root, Relids *relids_p,
73 : Relids *nullable_relids_p, bool is_pushed_down);
74 : static bool check_equivalence_delay(PlannerInfo *root,
75 : RestrictInfo *restrictinfo);
76 : static bool check_redundant_nullability_qual(PlannerInfo *root, Node *clause);
77 : static void check_mergejoinable(RestrictInfo *restrictinfo);
78 : static void check_hashjoinable(RestrictInfo *restrictinfo);
79 :
80 :
81 : /*****************************************************************************
82 : *
83 : * JOIN TREES
84 : *
85 : *****************************************************************************/
86 :
87 : /*
88 : * add_base_rels_to_query
89 : *
90 : * Scan the query's jointree and create baserel RelOptInfos for all
91 : * the base relations (ie, table, subquery, and function RTEs)
92 : * appearing in the jointree.
93 : *
94 : * The initial invocation must pass root->parse->jointree as the value of
95 : * jtnode. Internally, the function recurses through the jointree.
96 : *
97 : * At the end of this process, there should be one baserel RelOptInfo for
98 : * every non-join RTE that is used in the query. Therefore, this routine
99 : * is the only place that should call build_simple_rel with reloptkind
100 : * RELOPT_BASEREL. (Note: build_simple_rel recurses internally to build
101 : * "other rel" RelOptInfos for the members of any appendrels we find here.)
102 : */
103 : void
104 36206 : add_base_rels_to_query(PlannerInfo *root, Node *jtnode)
105 : {
106 36206 : if (jtnode == NULL)
107 36202 : return;
108 36206 : if (IsA(jtnode, RangeTblRef))
109 : {
110 17954 : int varno = ((RangeTblRef *) jtnode)->rtindex;
111 :
112 17954 : (void) build_simple_rel(root, varno, NULL);
113 : }
114 18252 : else if (IsA(jtnode, FromExpr))
115 : {
116 15610 : FromExpr *f = (FromExpr *) jtnode;
117 : ListCell *l;
118 :
119 32710 : foreach(l, f->fromlist)
120 17102 : add_base_rels_to_query(root, lfirst(l));
121 : }
122 2642 : else if (IsA(jtnode, JoinExpr))
123 : {
124 2642 : JoinExpr *j = (JoinExpr *) jtnode;
125 :
126 2642 : add_base_rels_to_query(root, j->larg);
127 2642 : add_base_rels_to_query(root, j->rarg);
128 : }
129 : else
130 0 : elog(ERROR, "unrecognized node type: %d",
131 : (int) nodeTag(jtnode));
132 : }
133 :
134 :
135 : /*****************************************************************************
136 : *
137 : * TARGET LISTS
138 : *
139 : *****************************************************************************/
140 :
141 : /*
142 : * build_base_rel_tlists
143 : * Add targetlist entries for each var needed in the query's final tlist
144 : * (and HAVING clause, if any) to the appropriate base relations.
145 : *
146 : * We mark such vars as needed by "relation 0" to ensure that they will
147 : * propagate up through all join plan steps.
148 : */
149 : void
150 13818 : build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
151 : {
152 13818 : List *tlist_vars = pull_var_clause((Node *) final_tlist,
153 : PVC_RECURSE_AGGREGATES |
154 : PVC_RECURSE_WINDOWFUNCS |
155 : PVC_INCLUDE_PLACEHOLDERS);
156 :
157 13818 : if (tlist_vars != NIL)
158 : {
159 13035 : add_vars_to_targetlist(root, tlist_vars, bms_make_singleton(0), true);
160 13035 : list_free(tlist_vars);
161 : }
162 :
163 : /*
164 : * If there's a HAVING clause, we'll need the Vars it uses, too. Note
165 : * that HAVING can contain Aggrefs but not WindowFuncs.
166 : */
167 13818 : if (root->parse->havingQual)
168 : {
169 24 : List *having_vars = pull_var_clause(root->parse->havingQual,
170 : PVC_RECURSE_AGGREGATES |
171 : PVC_INCLUDE_PLACEHOLDERS);
172 :
173 24 : if (having_vars != NIL)
174 : {
175 13 : add_vars_to_targetlist(root, having_vars,
176 : bms_make_singleton(0), true);
177 13 : list_free(having_vars);
178 : }
179 : }
180 13818 : }
181 :
182 : /*
183 : * add_vars_to_targetlist
184 : * For each variable appearing in the list, add it to the owning
185 : * relation's targetlist if not already present, and mark the variable
186 : * as being needed for the indicated join (or for final output if
187 : * where_needed includes "relation 0").
188 : *
189 : * The list may also contain PlaceHolderVars. These don't necessarily
190 : * have a single owning relation; we keep their attr_needed info in
191 : * root->placeholder_list instead. If create_new_ph is true, it's OK
192 : * to create new PlaceHolderInfos; otherwise, the PlaceHolderInfos must
193 : * already exist, and we should only update their ph_needed. (This should
194 : * be true before deconstruct_jointree begins, and false after that.)
195 : */
196 : void
197 21059 : add_vars_to_targetlist(PlannerInfo *root, List *vars,
198 : Relids where_needed, bool create_new_ph)
199 : {
200 : ListCell *temp;
201 :
202 21059 : Assert(!bms_is_empty(where_needed));
203 :
204 71996 : foreach(temp, vars)
205 : {
206 50937 : Node *node = (Node *) lfirst(temp);
207 :
208 50937 : if (IsA(node, Var))
209 : {
210 50855 : Var *var = (Var *) node;
211 50855 : RelOptInfo *rel = find_base_rel(root, var->varno);
212 50855 : int attno = var->varattno;
213 :
214 50855 : if (bms_is_subset(where_needed, rel->relids))
215 39 : continue;
216 50816 : Assert(attno >= rel->min_attr && attno <= rel->max_attr);
217 50816 : attno -= rel->min_attr;
218 50816 : if (rel->attr_needed[attno] == NULL)
219 : {
220 : /* Variable not yet requested, so add to rel's targetlist */
221 : /* XXX is copyObject necessary here? */
222 40142 : rel->reltarget->exprs = lappend(rel->reltarget->exprs,
223 : copyObject(var));
224 : /* reltarget cost and width will be computed later */
225 : }
226 50816 : rel->attr_needed[attno] = bms_add_members(rel->attr_needed[attno],
227 : where_needed);
228 : }
229 82 : else if (IsA(node, PlaceHolderVar))
230 : {
231 82 : PlaceHolderVar *phv = (PlaceHolderVar *) node;
232 82 : PlaceHolderInfo *phinfo = find_placeholder_info(root, phv,
233 : create_new_ph);
234 :
235 82 : phinfo->ph_needed = bms_add_members(phinfo->ph_needed,
236 : where_needed);
237 : }
238 : else
239 0 : elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
240 : }
241 21059 : }
242 :
243 :
244 : /*****************************************************************************
245 : *
246 : * LATERAL REFERENCES
247 : *
248 : *****************************************************************************/
249 :
250 : /*
251 : * find_lateral_references
252 : * For each LATERAL subquery, extract all its references to Vars and
253 : * PlaceHolderVars of the current query level, and make sure those values
254 : * will be available for evaluation of the subquery.
255 : *
256 : * While later planning steps ensure that the Var/PHV source rels are on the
257 : * outside of nestloops relative to the LATERAL subquery, we also need to
258 : * ensure that the Vars/PHVs propagate up to the nestloop join level; this
259 : * means setting suitable where_needed values for them.
260 : *
261 : * Note that this only deals with lateral references in unflattened LATERAL
262 : * subqueries. When we flatten a LATERAL subquery, its lateral references
263 : * become plain Vars in the parent query, but they may have to be wrapped in
264 : * PlaceHolderVars if they need to be forced NULL by outer joins that don't
265 : * also null the LATERAL subquery. That's all handled elsewhere.
266 : *
267 : * This has to run before deconstruct_jointree, since it might result in
268 : * creation of PlaceHolderInfos.
269 : */
270 : void
271 13818 : find_lateral_references(PlannerInfo *root)
272 : {
273 : Index rti;
274 :
275 : /* We need do nothing if the query contains no LATERAL RTEs */
276 13818 : if (!root->hasLateralRTEs)
277 27486 : return;
278 :
279 : /*
280 : * Examine all baserels (the rel array has been set up by now).
281 : */
282 762 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
283 : {
284 612 : RelOptInfo *brel = root->simple_rel_array[rti];
285 :
286 : /* there may be empty slots corresponding to non-baserel RTEs */
287 612 : if (brel == NULL)
288 247 : continue;
289 :
290 365 : Assert(brel->relid == rti); /* sanity check on array */
291 :
292 : /*
293 : * This bit is less obvious than it might look. We ignore appendrel
294 : * otherrels and consider only their parent baserels. In a case where
295 : * a LATERAL-containing UNION ALL subquery was pulled up, it is the
296 : * otherrel that is actually going to be in the plan. However, we
297 : * want to mark all its lateral references as needed by the parent,
298 : * because it is the parent's relid that will be used for join
299 : * planning purposes. And the parent's RTE will contain all the
300 : * lateral references we need to know, since the pulled-up member is
301 : * nothing but a copy of parts of the original RTE's subquery. We
302 : * could visit the parent's children instead and transform their
303 : * references back to the parent's relid, but it would be much more
304 : * complicated for no real gain. (Important here is that the child
305 : * members have not yet received any processing beyond being pulled
306 : * up.) Similarly, in appendrels created by inheritance expansion,
307 : * it's sufficient to look at the parent relation.
308 : */
309 :
310 : /* ignore RTEs that are "other rels" */
311 365 : if (brel->reloptkind != RELOPT_BASEREL)
312 10 : continue;
313 :
314 355 : extract_lateral_references(root, brel, rti);
315 : }
316 : }
317 :
318 : static void
319 355 : extract_lateral_references(PlannerInfo *root, RelOptInfo *brel, Index rtindex)
320 : {
321 355 : RangeTblEntry *rte = root->simple_rte_array[rtindex];
322 : List *vars;
323 : List *newvars;
324 : Relids where_needed;
325 : ListCell *lc;
326 :
327 : /* No cross-references are possible if it's not LATERAL */
328 355 : if (!rte->lateral)
329 231 : return;
330 :
331 : /* Fetch the appropriate variables */
332 124 : if (rte->rtekind == RTE_RELATION)
333 3 : vars = pull_vars_of_level((Node *) rte->tablesample, 0);
334 121 : else if (rte->rtekind == RTE_SUBQUERY)
335 41 : vars = pull_vars_of_level((Node *) rte->subquery, 1);
336 80 : else if (rte->rtekind == RTE_FUNCTION)
337 52 : vars = pull_vars_of_level((Node *) rte->functions, 0);
338 28 : else if (rte->rtekind == RTE_TABLEFUNC)
339 22 : vars = pull_vars_of_level((Node *) rte->tablefunc, 0);
340 6 : else if (rte->rtekind == RTE_VALUES)
341 6 : vars = pull_vars_of_level((Node *) rte->values_lists, 0);
342 : else
343 : {
344 0 : Assert(false);
345 : return; /* keep compiler quiet */
346 : }
347 :
348 124 : if (vars == NIL)
349 2 : return; /* nothing to do */
350 :
351 : /* Copy each Var (or PlaceHolderVar) and adjust it to match our level */
352 122 : newvars = NIL;
353 309 : foreach(lc, vars)
354 : {
355 187 : Node *node = (Node *) lfirst(lc);
356 :
357 187 : node = copyObject(node);
358 187 : if (IsA(node, Var))
359 : {
360 181 : Var *var = (Var *) node;
361 :
362 : /* Adjustment is easy since it's just one node */
363 181 : var->varlevelsup = 0;
364 : }
365 6 : else if (IsA(node, PlaceHolderVar))
366 : {
367 6 : PlaceHolderVar *phv = (PlaceHolderVar *) node;
368 6 : int levelsup = phv->phlevelsup;
369 :
370 : /* Have to work harder to adjust the contained expression too */
371 6 : if (levelsup != 0)
372 6 : IncrementVarSublevelsUp(node, -levelsup, 0);
373 :
374 : /*
375 : * If we pulled the PHV out of a subquery RTE, its expression
376 : * needs to be preprocessed. subquery_planner() already did this
377 : * for level-zero PHVs in function and values RTEs, though.
378 : */
379 6 : if (levelsup > 0)
380 6 : phv->phexpr = preprocess_phv_expression(root, phv->phexpr);
381 : }
382 : else
383 0 : Assert(false);
384 187 : newvars = lappend(newvars, node);
385 : }
386 :
387 122 : list_free(vars);
388 :
389 : /*
390 : * We mark the Vars as being "needed" at the LATERAL RTE. This is a bit
391 : * of a cheat: a more formal approach would be to mark each one as needed
392 : * at the join of the LATERAL RTE with its source RTE. But it will work,
393 : * and it's much less tedious than computing a separate where_needed for
394 : * each Var.
395 : */
396 122 : where_needed = bms_make_singleton(rtindex);
397 :
398 : /*
399 : * Push Vars into their source relations' targetlists, and PHVs into
400 : * root->placeholder_list.
401 : */
402 122 : add_vars_to_targetlist(root, newvars, where_needed, true);
403 :
404 : /* Remember the lateral references for create_lateral_join_info */
405 122 : brel->lateral_vars = newvars;
406 : }
407 :
408 : /*
409 : * create_lateral_join_info
410 : * Fill in the per-base-relation direct_lateral_relids, lateral_relids
411 : * and lateral_referencers sets.
412 : *
413 : * This has to run after deconstruct_jointree, because we need to know the
414 : * final ph_eval_at values for PlaceHolderVars.
415 : */
416 : void
417 13818 : create_lateral_join_info(PlannerInfo *root)
418 : {
419 13818 : bool found_laterals = false;
420 : Index rti;
421 : ListCell *lc;
422 :
423 : /* We need do nothing if the query contains no LATERAL RTEs */
424 13818 : if (!root->hasLateralRTEs)
425 13668 : return;
426 :
427 : /*
428 : * Examine all baserels (the rel array has been set up by now).
429 : */
430 762 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
431 : {
432 612 : RelOptInfo *brel = root->simple_rel_array[rti];
433 : Relids lateral_relids;
434 :
435 : /* there may be empty slots corresponding to non-baserel RTEs */
436 612 : if (brel == NULL)
437 247 : continue;
438 :
439 365 : Assert(brel->relid == rti); /* sanity check on array */
440 :
441 : /* ignore RTEs that are "other rels" */
442 365 : if (brel->reloptkind != RELOPT_BASEREL)
443 10 : continue;
444 :
445 355 : lateral_relids = NULL;
446 :
447 : /* consider each laterally-referenced Var or PHV */
448 542 : foreach(lc, brel->lateral_vars)
449 : {
450 187 : Node *node = (Node *) lfirst(lc);
451 :
452 187 : if (IsA(node, Var))
453 : {
454 181 : Var *var = (Var *) node;
455 :
456 181 : found_laterals = true;
457 181 : lateral_relids = bms_add_member(lateral_relids,
458 181 : var->varno);
459 : }
460 6 : else if (IsA(node, PlaceHolderVar))
461 : {
462 6 : PlaceHolderVar *phv = (PlaceHolderVar *) node;
463 6 : PlaceHolderInfo *phinfo = find_placeholder_info(root, phv,
464 : false);
465 :
466 6 : found_laterals = true;
467 6 : lateral_relids = bms_add_members(lateral_relids,
468 6 : phinfo->ph_eval_at);
469 : }
470 : else
471 0 : Assert(false);
472 : }
473 :
474 : /* We now have all the simple lateral refs from this rel */
475 355 : brel->direct_lateral_relids = lateral_relids;
476 355 : brel->lateral_relids = bms_copy(lateral_relids);
477 : }
478 :
479 : /*
480 : * Now check for lateral references within PlaceHolderVars, and mark their
481 : * eval_at rels as having lateral references to the source rels.
482 : *
483 : * For a PHV that is due to be evaluated at a baserel, mark its source(s)
484 : * as direct lateral dependencies of the baserel (adding onto the ones
485 : * recorded above). If it's due to be evaluated at a join, mark its
486 : * source(s) as indirect lateral dependencies of each baserel in the join,
487 : * ie put them into lateral_relids but not direct_lateral_relids. This is
488 : * appropriate because we can't put any such baserel on the outside of a
489 : * join to one of the PHV's lateral dependencies, but on the other hand we
490 : * also can't yet join it directly to the dependency.
491 : */
492 170 : foreach(lc, root->placeholder_list)
493 : {
494 20 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
495 20 : Relids eval_at = phinfo->ph_eval_at;
496 : int varno;
497 :
498 20 : if (phinfo->ph_lateral == NULL)
499 10 : continue; /* PHV is uninteresting if no lateral refs */
500 :
501 10 : found_laterals = true;
502 :
503 10 : if (bms_get_singleton_member(eval_at, &varno))
504 : {
505 : /* Evaluation site is a baserel */
506 8 : RelOptInfo *brel = find_base_rel(root, varno);
507 :
508 8 : brel->direct_lateral_relids =
509 8 : bms_add_members(brel->direct_lateral_relids,
510 8 : phinfo->ph_lateral);
511 8 : brel->lateral_relids =
512 8 : bms_add_members(brel->lateral_relids,
513 8 : phinfo->ph_lateral);
514 : }
515 : else
516 : {
517 : /* Evaluation site is a join */
518 2 : varno = -1;
519 8 : while ((varno = bms_next_member(eval_at, varno)) >= 0)
520 : {
521 4 : RelOptInfo *brel = find_base_rel(root, varno);
522 :
523 4 : brel->lateral_relids = bms_add_members(brel->lateral_relids,
524 4 : phinfo->ph_lateral);
525 : }
526 : }
527 : }
528 :
529 : /*
530 : * If we found no actual lateral references, we're done; but reset the
531 : * hasLateralRTEs flag to avoid useless work later.
532 : */
533 150 : if (!found_laterals)
534 : {
535 24 : root->hasLateralRTEs = false;
536 24 : return;
537 : }
538 :
539 : /*
540 : * Calculate the transitive closure of the lateral_relids sets, so that
541 : * they describe both direct and indirect lateral references. If relation
542 : * X references Y laterally, and Y references Z laterally, then we will
543 : * have to scan X on the inside of a nestloop with Z, so for all intents
544 : * and purposes X is laterally dependent on Z too.
545 : *
546 : * This code is essentially Warshall's algorithm for transitive closure.
547 : * The outer loop considers each baserel, and propagates its lateral
548 : * dependencies to those baserels that have a lateral dependency on it.
549 : */
550 638 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
551 : {
552 512 : RelOptInfo *brel = root->simple_rel_array[rti];
553 : Relids outer_lateral_relids;
554 : Index rti2;
555 :
556 512 : if (brel == NULL || brel->reloptkind != RELOPT_BASEREL)
557 200 : continue;
558 :
559 : /* need not consider baserel further if it has no lateral refs */
560 312 : outer_lateral_relids = brel->lateral_relids;
561 312 : if (outer_lateral_relids == NULL)
562 178 : continue;
563 :
564 : /* else scan all baserels */
565 689 : for (rti2 = 1; rti2 < root->simple_rel_array_size; rti2++)
566 : {
567 555 : RelOptInfo *brel2 = root->simple_rel_array[rti2];
568 :
569 555 : if (brel2 == NULL || brel2->reloptkind != RELOPT_BASEREL)
570 213 : continue;
571 :
572 : /* if brel2 has lateral ref to brel, propagate brel's refs */
573 342 : if (bms_is_member(rti, brel2->lateral_relids))
574 6 : brel2->lateral_relids = bms_add_members(brel2->lateral_relids,
575 : outer_lateral_relids);
576 : }
577 : }
578 :
579 : /*
580 : * Now that we've identified all lateral references, mark each baserel
581 : * with the set of relids of rels that reference it laterally (possibly
582 : * indirectly) --- that is, the inverse mapping of lateral_relids.
583 : */
584 638 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
585 : {
586 512 : RelOptInfo *brel = root->simple_rel_array[rti];
587 : Relids lateral_relids;
588 : int rti2;
589 :
590 512 : if (brel == NULL || brel->reloptkind != RELOPT_BASEREL)
591 200 : continue;
592 :
593 : /* Nothing to do at rels with no lateral refs */
594 312 : lateral_relids = brel->lateral_relids;
595 312 : if (lateral_relids == NULL)
596 178 : continue;
597 :
598 : /*
599 : * We should not have broken the invariant that lateral_relids is
600 : * exactly NULL if empty.
601 : */
602 134 : Assert(!bms_is_empty(lateral_relids));
603 :
604 : /* Also, no rel should have a lateral dependency on itself */
605 134 : Assert(!bms_is_member(rti, lateral_relids));
606 :
607 : /* Mark this rel's referencees */
608 134 : rti2 = -1;
609 421 : while ((rti2 = bms_next_member(lateral_relids, rti2)) >= 0)
610 : {
611 153 : RelOptInfo *brel2 = root->simple_rel_array[rti2];
612 :
613 153 : Assert(brel2 != NULL && brel2->reloptkind == RELOPT_BASEREL);
614 153 : brel2->lateral_referencers =
615 153 : bms_add_member(brel2->lateral_referencers, rti);
616 : }
617 : }
618 :
619 : /*
620 : * Lastly, propagate lateral_relids and lateral_referencers from appendrel
621 : * parent rels to their child rels. We intentionally give each child rel
622 : * the same minimum parameterization, even though it's quite possible that
623 : * some don't reference all the lateral rels. This is because any append
624 : * path for the parent will have to have the same parameterization for
625 : * every child anyway, and there's no value in forcing extra
626 : * reparameterize_path() calls. Similarly, a lateral reference to the
627 : * parent prevents use of otherwise-movable join rels for each child.
628 : */
629 638 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
630 : {
631 512 : RelOptInfo *brel = root->simple_rel_array[rti];
632 :
633 512 : if (brel == NULL || brel->reloptkind != RELOPT_BASEREL)
634 200 : continue;
635 :
636 312 : if (root->simple_rte_array[rti]->inh)
637 : {
638 15 : foreach(lc, root->append_rel_list)
639 : {
640 10 : AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
641 : RelOptInfo *childrel;
642 :
643 10 : if (appinfo->parent_relid != rti)
644 0 : continue;
645 10 : childrel = root->simple_rel_array[appinfo->child_relid];
646 10 : Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL);
647 10 : Assert(childrel->direct_lateral_relids == NULL);
648 10 : childrel->direct_lateral_relids = brel->direct_lateral_relids;
649 10 : Assert(childrel->lateral_relids == NULL);
650 10 : childrel->lateral_relids = brel->lateral_relids;
651 10 : Assert(childrel->lateral_referencers == NULL);
652 10 : childrel->lateral_referencers = brel->lateral_referencers;
653 : }
654 : }
655 : }
656 : }
657 :
658 :
659 : /*****************************************************************************
660 : *
661 : * JOIN TREE PROCESSING
662 : *
663 : *****************************************************************************/
664 :
665 : /*
666 : * deconstruct_jointree
667 : * Recursively scan the query's join tree for WHERE and JOIN/ON qual
668 : * clauses, and add these to the appropriate restrictinfo and joininfo
669 : * lists belonging to base RelOptInfos. Also, add SpecialJoinInfo nodes
670 : * to root->join_info_list for any outer joins appearing in the query tree.
671 : * Return a "joinlist" data structure showing the join order decisions
672 : * that need to be made by make_one_rel().
673 : *
674 : * The "joinlist" result is a list of items that are either RangeTblRef
675 : * jointree nodes or sub-joinlists. All the items at the same level of
676 : * joinlist must be joined in an order to be determined by make_one_rel()
677 : * (note that legal orders may be constrained by SpecialJoinInfo nodes).
678 : * A sub-joinlist represents a subproblem to be planned separately. Currently
679 : * sub-joinlists arise only from FULL OUTER JOIN or when collapsing of
680 : * subproblems is stopped by join_collapse_limit or from_collapse_limit.
681 : *
682 : * NOTE: when dealing with inner joins, it is appropriate to let a qual clause
683 : * be evaluated at the lowest level where all the variables it mentions are
684 : * available. However, we cannot push a qual down into the nullable side(s)
685 : * of an outer join since the qual might eliminate matching rows and cause a
686 : * NULL row to be incorrectly emitted by the join. Therefore, we artificially
687 : * OR the minimum-relids of such an outer join into the required_relids of
688 : * clauses appearing above it. This forces those clauses to be delayed until
689 : * application of the outer join (or maybe even higher in the join tree).
690 : */
691 : List *
692 13818 : deconstruct_jointree(PlannerInfo *root)
693 : {
694 : List *result;
695 : Relids qualscope;
696 : Relids inner_join_rels;
697 13818 : List *postponed_qual_list = NIL;
698 :
699 : /* Start recursion at top of jointree */
700 13818 : Assert(root->parse->jointree != NULL &&
701 : IsA(root->parse->jointree, FromExpr));
702 :
703 : /* this is filled as we scan the jointree */
704 13818 : root->nullable_baserels = NULL;
705 :
706 13818 : result = deconstruct_recurse(root, (Node *) root->parse->jointree, false,
707 : &qualscope, &inner_join_rels,
708 : &postponed_qual_list);
709 :
710 : /* Shouldn't be any leftover quals */
711 13818 : Assert(postponed_qual_list == NIL);
712 :
713 13818 : return result;
714 : }
715 :
716 : /*
717 : * deconstruct_recurse
718 : * One recursion level of deconstruct_jointree processing.
719 : *
720 : * Inputs:
721 : * jtnode is the jointree node to examine
722 : * below_outer_join is TRUE if this node is within the nullable side of a
723 : * higher-level outer join
724 : * Outputs:
725 : * *qualscope gets the set of base Relids syntactically included in this
726 : * jointree node (do not modify or free this, as it may also be pointed
727 : * to by RestrictInfo and SpecialJoinInfo nodes)
728 : * *inner_join_rels gets the set of base Relids syntactically included in
729 : * inner joins appearing at or below this jointree node (do not modify
730 : * or free this, either)
731 : * *postponed_qual_list is a list of PostponedQual structs, which we can
732 : * add quals to if they turn out to belong to a higher join level
733 : * Return value is the appropriate joinlist for this jointree node
734 : *
735 : * In addition, entries will be added to root->join_info_list for outer joins.
736 : */
737 : static List *
738 36202 : deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
739 : Relids *qualscope, Relids *inner_join_rels,
740 : List **postponed_qual_list)
741 : {
742 : List *joinlist;
743 :
744 36202 : if (jtnode == NULL)
745 : {
746 0 : *qualscope = NULL;
747 0 : *inner_join_rels = NULL;
748 0 : return NIL;
749 : }
750 36202 : if (IsA(jtnode, RangeTblRef))
751 : {
752 17952 : int varno = ((RangeTblRef *) jtnode)->rtindex;
753 :
754 : /* qualscope is just the one RTE */
755 17952 : *qualscope = bms_make_singleton(varno);
756 : /* Deal with any securityQuals attached to the RTE */
757 17952 : if (root->qual_security_level > 0)
758 329 : process_security_barrier_quals(root,
759 : varno,
760 : *qualscope,
761 : below_outer_join);
762 : /* A single baserel does not create an inner join */
763 17952 : *inner_join_rels = NULL;
764 17952 : joinlist = list_make1(jtnode);
765 : }
766 18250 : else if (IsA(jtnode, FromExpr))
767 : {
768 15608 : FromExpr *f = (FromExpr *) jtnode;
769 15608 : List *child_postponed_quals = NIL;
770 : int remaining;
771 : ListCell *l;
772 :
773 : /*
774 : * First, recurse to handle child joins. We collapse subproblems into
775 : * a single joinlist whenever the resulting joinlist wouldn't exceed
776 : * from_collapse_limit members. Also, always collapse one-element
777 : * subproblems, since that won't lengthen the joinlist anyway.
778 : */
779 15608 : *qualscope = NULL;
780 15608 : *inner_join_rels = NULL;
781 15608 : joinlist = NIL;
782 15608 : remaining = list_length(f->fromlist);
783 32708 : foreach(l, f->fromlist)
784 : {
785 : Relids sub_qualscope;
786 : List *sub_joinlist;
787 : int sub_members;
788 :
789 17100 : sub_joinlist = deconstruct_recurse(root, lfirst(l),
790 : below_outer_join,
791 : &sub_qualscope,
792 : inner_join_rels,
793 : &child_postponed_quals);
794 17100 : *qualscope = bms_add_members(*qualscope, sub_qualscope);
795 17100 : sub_members = list_length(sub_joinlist);
796 17100 : remaining--;
797 19738 : if (sub_members <= 1 ||
798 2638 : list_length(joinlist) + sub_members + remaining <= from_collapse_limit)
799 17100 : joinlist = list_concat(joinlist, sub_joinlist);
800 : else
801 0 : joinlist = lappend(joinlist, sub_joinlist);
802 : }
803 :
804 : /*
805 : * A FROM with more than one list element is an inner join subsuming
806 : * all below it, so we should report inner_join_rels = qualscope. If
807 : * there was exactly one element, we should (and already did) report
808 : * whatever its inner_join_rels were. If there were no elements (is
809 : * that possible?) the initialization before the loop fixed it.
810 : */
811 15608 : if (list_length(f->fromlist) > 1)
812 1321 : *inner_join_rels = *qualscope;
813 :
814 : /*
815 : * Try to process any quals postponed by children. If they need
816 : * further postponement, add them to my output postponed_qual_list.
817 : */
818 15615 : foreach(l, child_postponed_quals)
819 : {
820 7 : PostponedQual *pq = (PostponedQual *) lfirst(l);
821 :
822 7 : if (bms_is_subset(pq->relids, *qualscope))
823 7 : distribute_qual_to_rels(root, pq->qual,
824 : false, below_outer_join, JOIN_INNER,
825 : root->qual_security_level,
826 : *qualscope, NULL, NULL, NULL,
827 : NULL);
828 : else
829 0 : *postponed_qual_list = lappend(*postponed_qual_list, pq);
830 : }
831 :
832 : /*
833 : * Now process the top-level quals.
834 : */
835 29703 : foreach(l, (List *) f->quals)
836 : {
837 14095 : Node *qual = (Node *) lfirst(l);
838 :
839 14095 : distribute_qual_to_rels(root, qual,
840 : false, below_outer_join, JOIN_INNER,
841 : root->qual_security_level,
842 : *qualscope, NULL, NULL, NULL,
843 : postponed_qual_list);
844 : }
845 : }
846 2642 : else if (IsA(jtnode, JoinExpr))
847 : {
848 2642 : JoinExpr *j = (JoinExpr *) jtnode;
849 2642 : List *child_postponed_quals = NIL;
850 : Relids leftids,
851 : rightids,
852 : left_inners,
853 : right_inners,
854 : nonnullable_rels,
855 : nullable_rels,
856 : ojscope;
857 : List *leftjoinlist,
858 : *rightjoinlist;
859 : List *my_quals;
860 : SpecialJoinInfo *sjinfo;
861 : ListCell *l;
862 :
863 : /*
864 : * Order of operations here is subtle and critical. First we recurse
865 : * to handle sub-JOINs. Their join quals will be placed without
866 : * regard for whether this level is an outer join, which is correct.
867 : * Then we place our own join quals, which are restricted by lower
868 : * outer joins in any case, and are forced to this level if this is an
869 : * outer join and they mention the outer side. Finally, if this is an
870 : * outer join, we create a join_info_list entry for the join. This
871 : * will prevent quals above us in the join tree that use those rels
872 : * from being pushed down below this level. (It's okay for upper
873 : * quals to be pushed down to the outer side, however.)
874 : */
875 2642 : switch (j->jointype)
876 : {
877 : case JOIN_INNER:
878 1121 : leftjoinlist = deconstruct_recurse(root, j->larg,
879 : below_outer_join,
880 : &leftids, &left_inners,
881 : &child_postponed_quals);
882 1121 : rightjoinlist = deconstruct_recurse(root, j->rarg,
883 : below_outer_join,
884 : &rightids, &right_inners,
885 : &child_postponed_quals);
886 1121 : *qualscope = bms_union(leftids, rightids);
887 1121 : *inner_join_rels = *qualscope;
888 : /* Inner join adds no restrictions for quals */
889 1121 : nonnullable_rels = NULL;
890 : /* and it doesn't force anything to null, either */
891 1121 : nullable_rels = NULL;
892 1121 : break;
893 : case JOIN_LEFT:
894 : case JOIN_ANTI:
895 1420 : leftjoinlist = deconstruct_recurse(root, j->larg,
896 : below_outer_join,
897 : &leftids, &left_inners,
898 : &child_postponed_quals);
899 1420 : rightjoinlist = deconstruct_recurse(root, j->rarg,
900 : true,
901 : &rightids, &right_inners,
902 : &child_postponed_quals);
903 1420 : *qualscope = bms_union(leftids, rightids);
904 1420 : *inner_join_rels = bms_union(left_inners, right_inners);
905 1420 : nonnullable_rels = leftids;
906 1420 : nullable_rels = rightids;
907 1420 : break;
908 : case JOIN_SEMI:
909 73 : leftjoinlist = deconstruct_recurse(root, j->larg,
910 : below_outer_join,
911 : &leftids, &left_inners,
912 : &child_postponed_quals);
913 73 : rightjoinlist = deconstruct_recurse(root, j->rarg,
914 : below_outer_join,
915 : &rightids, &right_inners,
916 : &child_postponed_quals);
917 73 : *qualscope = bms_union(leftids, rightids);
918 73 : *inner_join_rels = bms_union(left_inners, right_inners);
919 : /* Semi join adds no restrictions for quals */
920 73 : nonnullable_rels = NULL;
921 :
922 : /*
923 : * Theoretically, a semijoin would null the RHS; but since the
924 : * RHS can't be accessed above the join, this is immaterial
925 : * and we needn't account for it.
926 : */
927 73 : nullable_rels = NULL;
928 73 : break;
929 : case JOIN_FULL:
930 28 : leftjoinlist = deconstruct_recurse(root, j->larg,
931 : true,
932 : &leftids, &left_inners,
933 : &child_postponed_quals);
934 28 : rightjoinlist = deconstruct_recurse(root, j->rarg,
935 : true,
936 : &rightids, &right_inners,
937 : &child_postponed_quals);
938 28 : *qualscope = bms_union(leftids, rightids);
939 28 : *inner_join_rels = bms_union(left_inners, right_inners);
940 : /* each side is both outer and inner */
941 28 : nonnullable_rels = *qualscope;
942 28 : nullable_rels = *qualscope;
943 28 : break;
944 : default:
945 : /* JOIN_RIGHT was eliminated during reduce_outer_joins() */
946 0 : elog(ERROR, "unrecognized join type: %d",
947 : (int) j->jointype);
948 : nonnullable_rels = NULL; /* keep compiler quiet */
949 : nullable_rels = NULL;
950 : leftjoinlist = rightjoinlist = NIL;
951 : break;
952 : }
953 :
954 : /* Report all rels that will be nulled anywhere in the jointree */
955 2642 : root->nullable_baserels = bms_add_members(root->nullable_baserels,
956 : nullable_rels);
957 :
958 : /*
959 : * Try to process any quals postponed by children. If they need
960 : * further postponement, add them to my output postponed_qual_list.
961 : * Quals that can be processed now must be included in my_quals, so
962 : * that they'll be handled properly in make_outerjoininfo.
963 : */
964 2642 : my_quals = NIL;
965 2650 : foreach(l, child_postponed_quals)
966 : {
967 8 : PostponedQual *pq = (PostponedQual *) lfirst(l);
968 :
969 8 : if (bms_is_subset(pq->relids, *qualscope))
970 8 : my_quals = lappend(my_quals, pq->qual);
971 : else
972 : {
973 : /*
974 : * We should not be postponing any quals past an outer join.
975 : * If this Assert fires, pull_up_subqueries() messed up.
976 : */
977 0 : Assert(j->jointype == JOIN_INNER);
978 0 : *postponed_qual_list = lappend(*postponed_qual_list, pq);
979 : }
980 : }
981 : /* list_concat is nondestructive of its second argument */
982 2642 : my_quals = list_concat(my_quals, (List *) j->quals);
983 :
984 : /*
985 : * For an OJ, form the SpecialJoinInfo now, because we need the OJ's
986 : * semantic scope (ojscope) to pass to distribute_qual_to_rels. But
987 : * we mustn't add it to join_info_list just yet, because we don't want
988 : * distribute_qual_to_rels to think it is an outer join below us.
989 : *
990 : * Semijoins are a bit of a hybrid: we build a SpecialJoinInfo, but we
991 : * want ojscope = NULL for distribute_qual_to_rels.
992 : */
993 2642 : if (j->jointype != JOIN_INNER)
994 : {
995 1521 : sjinfo = make_outerjoininfo(root,
996 : leftids, rightids,
997 : *inner_join_rels,
998 : j->jointype,
999 : my_quals);
1000 1521 : if (j->jointype == JOIN_SEMI)
1001 73 : ojscope = NULL;
1002 : else
1003 1448 : ojscope = bms_union(sjinfo->min_lefthand,
1004 1448 : sjinfo->min_righthand);
1005 : }
1006 : else
1007 : {
1008 1121 : sjinfo = NULL;
1009 1121 : ojscope = NULL;
1010 : }
1011 :
1012 : /* Process the JOIN's qual clauses */
1013 6179 : foreach(l, my_quals)
1014 : {
1015 3537 : Node *qual = (Node *) lfirst(l);
1016 :
1017 3537 : distribute_qual_to_rels(root, qual,
1018 : false, below_outer_join, j->jointype,
1019 : root->qual_security_level,
1020 : *qualscope,
1021 : ojscope, nonnullable_rels, NULL,
1022 : postponed_qual_list);
1023 : }
1024 :
1025 : /* Now we can add the SpecialJoinInfo to join_info_list */
1026 2642 : if (sjinfo)
1027 : {
1028 1521 : root->join_info_list = lappend(root->join_info_list, sjinfo);
1029 : /* Each time we do that, recheck placeholder eval levels */
1030 1521 : update_placeholder_eval_levels(root, sjinfo);
1031 : }
1032 :
1033 : /*
1034 : * Finally, compute the output joinlist. We fold subproblems together
1035 : * except at a FULL JOIN or where join_collapse_limit would be
1036 : * exceeded.
1037 : */
1038 2642 : if (j->jointype == JOIN_FULL)
1039 : {
1040 : /* force the join order exactly at this node */
1041 28 : joinlist = list_make1(list_make2(leftjoinlist, rightjoinlist));
1042 : }
1043 2614 : else if (list_length(leftjoinlist) + list_length(rightjoinlist) <=
1044 : join_collapse_limit)
1045 : {
1046 : /* OK to combine subproblems */
1047 2596 : joinlist = list_concat(leftjoinlist, rightjoinlist);
1048 : }
1049 : else
1050 : {
1051 : /* can't combine, but needn't force join order above here */
1052 : Node *leftpart,
1053 : *rightpart;
1054 :
1055 : /* avoid creating useless 1-element sublists */
1056 18 : if (list_length(leftjoinlist) == 1)
1057 0 : leftpart = (Node *) linitial(leftjoinlist);
1058 : else
1059 18 : leftpart = (Node *) leftjoinlist;
1060 18 : if (list_length(rightjoinlist) == 1)
1061 0 : rightpart = (Node *) linitial(rightjoinlist);
1062 : else
1063 18 : rightpart = (Node *) rightjoinlist;
1064 18 : joinlist = list_make2(leftpart, rightpart);
1065 : }
1066 : }
1067 : else
1068 : {
1069 0 : elog(ERROR, "unrecognized node type: %d",
1070 : (int) nodeTag(jtnode));
1071 : joinlist = NIL; /* keep compiler quiet */
1072 : }
1073 36202 : return joinlist;
1074 : }
1075 :
1076 : /*
1077 : * process_security_barrier_quals
1078 : * Transfer security-barrier quals into relation's baserestrictinfo list.
1079 : *
1080 : * The rewriter put any relevant security-barrier conditions into the RTE's
1081 : * securityQuals field, but it's now time to copy them into the rel's
1082 : * baserestrictinfo.
1083 : *
1084 : * In inheritance cases, we only consider quals attached to the parent rel
1085 : * here; they will be valid for all children too, so it's okay to consider
1086 : * them for purposes like equivalence class creation. Quals attached to
1087 : * individual child rels will be dealt with during path creation.
1088 : */
1089 : static void
1090 329 : process_security_barrier_quals(PlannerInfo *root,
1091 : int rti, Relids qualscope,
1092 : bool below_outer_join)
1093 : {
1094 329 : RangeTblEntry *rte = root->simple_rte_array[rti];
1095 329 : Index security_level = 0;
1096 : ListCell *lc;
1097 :
1098 : /*
1099 : * Each element of the securityQuals list has been preprocessed into an
1100 : * implicitly-ANDed list of clauses. All the clauses in a given sublist
1101 : * should get the same security level, but successive sublists get higher
1102 : * levels.
1103 : */
1104 667 : foreach(lc, rte->securityQuals)
1105 : {
1106 338 : List *qualset = (List *) lfirst(lc);
1107 : ListCell *lc2;
1108 :
1109 690 : foreach(lc2, qualset)
1110 : {
1111 352 : Node *qual = (Node *) lfirst(lc2);
1112 :
1113 : /*
1114 : * We cheat to the extent of passing ojscope = qualscope rather
1115 : * than its more logical value of NULL. The only effect this has
1116 : * is to force a Var-free qual to be evaluated at the rel rather
1117 : * than being pushed up to top of tree, which we don't want.
1118 : */
1119 352 : distribute_qual_to_rels(root, qual,
1120 : false,
1121 : below_outer_join,
1122 : JOIN_INNER,
1123 : security_level,
1124 : qualscope,
1125 : qualscope,
1126 : NULL,
1127 : NULL,
1128 : NULL);
1129 : }
1130 338 : security_level++;
1131 : }
1132 :
1133 : /* Assert that qual_security_level is higher than anything we just used */
1134 329 : Assert(security_level <= root->qual_security_level);
1135 329 : }
1136 :
1137 : /*
1138 : * make_outerjoininfo
1139 : * Build a SpecialJoinInfo for the current outer join
1140 : *
1141 : * Inputs:
1142 : * left_rels: the base Relids syntactically on outer side of join
1143 : * right_rels: the base Relids syntactically on inner side of join
1144 : * inner_join_rels: base Relids participating in inner joins below this one
1145 : * jointype: what it says (must always be LEFT, FULL, SEMI, or ANTI)
1146 : * clause: the outer join's join condition (in implicit-AND format)
1147 : *
1148 : * The node should eventually be appended to root->join_info_list, but we
1149 : * do not do that here.
1150 : *
1151 : * Note: we assume that this function is invoked bottom-up, so that
1152 : * root->join_info_list already contains entries for all outer joins that are
1153 : * syntactically below this one.
1154 : */
1155 : static SpecialJoinInfo *
1156 1521 : make_outerjoininfo(PlannerInfo *root,
1157 : Relids left_rels, Relids right_rels,
1158 : Relids inner_join_rels,
1159 : JoinType jointype, List *clause)
1160 : {
1161 1521 : SpecialJoinInfo *sjinfo = makeNode(SpecialJoinInfo);
1162 : Relids clause_relids;
1163 : Relids strict_relids;
1164 : Relids min_lefthand;
1165 : Relids min_righthand;
1166 : ListCell *l;
1167 :
1168 : /*
1169 : * We should not see RIGHT JOIN here because left/right were switched
1170 : * earlier
1171 : */
1172 1521 : Assert(jointype != JOIN_INNER);
1173 1521 : Assert(jointype != JOIN_RIGHT);
1174 :
1175 : /*
1176 : * Presently the executor cannot support FOR [KEY] UPDATE/SHARE marking of
1177 : * rels appearing on the nullable side of an outer join. (It's somewhat
1178 : * unclear what that would mean, anyway: what should we mark when a result
1179 : * row is generated from no element of the nullable relation?) So,
1180 : * complain if any nullable rel is FOR [KEY] UPDATE/SHARE.
1181 : *
1182 : * You might be wondering why this test isn't made far upstream in the
1183 : * parser. It's because the parser hasn't got enough info --- consider
1184 : * FOR UPDATE applied to a view. Only after rewriting and flattening do
1185 : * we know whether the view contains an outer join.
1186 : *
1187 : * We use the original RowMarkClause list here; the PlanRowMark list would
1188 : * list everything.
1189 : */
1190 1521 : foreach(l, root->parse->rowMarks)
1191 : {
1192 0 : RowMarkClause *rc = (RowMarkClause *) lfirst(l);
1193 :
1194 0 : if (bms_is_member(rc->rti, right_rels) ||
1195 0 : (jointype == JOIN_FULL && bms_is_member(rc->rti, left_rels)))
1196 0 : ereport(ERROR,
1197 : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1198 : /*------
1199 : translator: %s is a SQL row locking clause such as FOR UPDATE */
1200 : errmsg("%s cannot be applied to the nullable side of an outer join",
1201 : LCS_asString(rc->strength))));
1202 : }
1203 :
1204 1521 : sjinfo->syn_lefthand = left_rels;
1205 1521 : sjinfo->syn_righthand = right_rels;
1206 1521 : sjinfo->jointype = jointype;
1207 : /* this always starts out false */
1208 1521 : sjinfo->delay_upper_joins = false;
1209 :
1210 1521 : compute_semijoin_info(sjinfo, clause);
1211 :
1212 : /* If it's a full join, no need to be very smart */
1213 1521 : if (jointype == JOIN_FULL)
1214 : {
1215 28 : sjinfo->min_lefthand = bms_copy(left_rels);
1216 28 : sjinfo->min_righthand = bms_copy(right_rels);
1217 28 : sjinfo->lhs_strict = false; /* don't care about this */
1218 28 : return sjinfo;
1219 : }
1220 :
1221 : /*
1222 : * Retrieve all relids mentioned within the join clause.
1223 : */
1224 1493 : clause_relids = pull_varnos((Node *) clause);
1225 :
1226 : /*
1227 : * For which relids is the clause strict, ie, it cannot succeed if the
1228 : * rel's columns are all NULL?
1229 : */
1230 1493 : strict_relids = find_nonnullable_rels((Node *) clause);
1231 :
1232 : /* Remember whether the clause is strict for any LHS relations */
1233 1493 : sjinfo->lhs_strict = bms_overlap(strict_relids, left_rels);
1234 :
1235 : /*
1236 : * Required LHS always includes the LHS rels mentioned in the clause. We
1237 : * may have to add more rels based on lower outer joins; see below.
1238 : */
1239 1493 : min_lefthand = bms_intersect(clause_relids, left_rels);
1240 :
1241 : /*
1242 : * Similarly for required RHS. But here, we must also include any lower
1243 : * inner joins, to ensure we don't try to commute with any of them.
1244 : */
1245 1493 : min_righthand = bms_int_members(bms_union(clause_relids, inner_join_rels),
1246 : right_rels);
1247 :
1248 : /*
1249 : * Now check previous outer joins for ordering restrictions.
1250 : */
1251 1755 : foreach(l, root->join_info_list)
1252 : {
1253 262 : SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(l);
1254 :
1255 : /*
1256 : * A full join is an optimization barrier: we can't associate into or
1257 : * out of it. Hence, if it overlaps either LHS or RHS of the current
1258 : * rel, expand that side's min relset to cover the whole full join.
1259 : */
1260 262 : if (otherinfo->jointype == JOIN_FULL)
1261 : {
1262 4 : if (bms_overlap(left_rels, otherinfo->syn_lefthand) ||
1263 2 : bms_overlap(left_rels, otherinfo->syn_righthand))
1264 : {
1265 0 : min_lefthand = bms_add_members(min_lefthand,
1266 0 : otherinfo->syn_lefthand);
1267 0 : min_lefthand = bms_add_members(min_lefthand,
1268 0 : otherinfo->syn_righthand);
1269 : }
1270 2 : if (bms_overlap(right_rels, otherinfo->syn_lefthand) ||
1271 0 : bms_overlap(right_rels, otherinfo->syn_righthand))
1272 : {
1273 2 : min_righthand = bms_add_members(min_righthand,
1274 2 : otherinfo->syn_lefthand);
1275 2 : min_righthand = bms_add_members(min_righthand,
1276 2 : otherinfo->syn_righthand);
1277 : }
1278 : /* Needn't do anything else with the full join */
1279 2 : continue;
1280 : }
1281 :
1282 : /*
1283 : * For a lower OJ in our LHS, if our join condition uses the lower
1284 : * join's RHS and is not strict for that rel, we must preserve the
1285 : * ordering of the two OJs, so add lower OJ's full syntactic relset to
1286 : * min_lefthand. (We must use its full syntactic relset, not just its
1287 : * min_lefthand + min_righthand. This is because there might be other
1288 : * OJs below this one that this one can commute with, but we cannot
1289 : * commute with them if we don't with this one.) Also, if the current
1290 : * join is a semijoin or antijoin, we must preserve ordering
1291 : * regardless of strictness.
1292 : *
1293 : * Note: I believe we have to insist on being strict for at least one
1294 : * rel in the lower OJ's min_righthand, not its whole syn_righthand.
1295 : */
1296 260 : if (bms_overlap(left_rels, otherinfo->syn_righthand))
1297 : {
1298 205 : if (bms_overlap(clause_relids, otherinfo->syn_righthand) &&
1299 56 : (jointype == JOIN_SEMI || jointype == JOIN_ANTI ||
1300 28 : !bms_overlap(strict_relids, otherinfo->min_righthand)))
1301 : {
1302 4 : min_lefthand = bms_add_members(min_lefthand,
1303 4 : otherinfo->syn_lefthand);
1304 4 : min_lefthand = bms_add_members(min_lefthand,
1305 4 : otherinfo->syn_righthand);
1306 : }
1307 : }
1308 :
1309 : /*
1310 : * For a lower OJ in our RHS, if our join condition does not use the
1311 : * lower join's RHS and the lower OJ's join condition is strict, we
1312 : * can interchange the ordering of the two OJs; otherwise we must add
1313 : * the lower OJ's full syntactic relset to min_righthand.
1314 : *
1315 : * Also, if our join condition does not use the lower join's LHS
1316 : * either, force the ordering to be preserved. Otherwise we can end
1317 : * up with SpecialJoinInfos with identical min_righthands, which can
1318 : * confuse join_is_legal (see discussion in backend/optimizer/README).
1319 : *
1320 : * Also, we must preserve ordering anyway if either the current join
1321 : * or the lower OJ is either a semijoin or an antijoin.
1322 : *
1323 : * Here, we have to consider that "our join condition" includes any
1324 : * clauses that syntactically appeared above the lower OJ and below
1325 : * ours; those are equivalent to degenerate clauses in our OJ and must
1326 : * be treated as such. Such clauses obviously can't reference our
1327 : * LHS, and they must be non-strict for the lower OJ's RHS (else
1328 : * reduce_outer_joins would have reduced the lower OJ to a plain
1329 : * join). Hence the other ways in which we handle clauses within our
1330 : * join condition are not affected by them. The net effect is
1331 : * therefore sufficiently represented by the delay_upper_joins flag
1332 : * saved for us by check_outerjoin_delay.
1333 : */
1334 260 : if (bms_overlap(right_rels, otherinfo->syn_righthand))
1335 : {
1336 102 : if (bms_overlap(clause_relids, otherinfo->syn_righthand) ||
1337 78 : !bms_overlap(clause_relids, otherinfo->min_lefthand) ||
1338 26 : jointype == JOIN_SEMI ||
1339 24 : jointype == JOIN_ANTI ||
1340 46 : otherinfo->jointype == JOIN_SEMI ||
1341 44 : otherinfo->jointype == JOIN_ANTI ||
1342 44 : !otherinfo->lhs_strict || otherinfo->delay_upper_joins)
1343 : {
1344 32 : min_righthand = bms_add_members(min_righthand,
1345 32 : otherinfo->syn_lefthand);
1346 32 : min_righthand = bms_add_members(min_righthand,
1347 32 : otherinfo->syn_righthand);
1348 : }
1349 : }
1350 : }
1351 :
1352 : /*
1353 : * Examine PlaceHolderVars. If a PHV is supposed to be evaluated within
1354 : * this join's nullable side, then ensure that min_righthand contains the
1355 : * full eval_at set of the PHV. This ensures that the PHV actually can be
1356 : * evaluated within the RHS. Note that this works only because we should
1357 : * already have determined the final eval_at level for any PHV
1358 : * syntactically within this join.
1359 : */
1360 1576 : foreach(l, root->placeholder_list)
1361 : {
1362 83 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
1363 83 : Relids ph_syn_level = phinfo->ph_var->phrels;
1364 :
1365 : /* Ignore placeholder if it didn't syntactically come from RHS */
1366 83 : if (!bms_is_subset(ph_syn_level, right_rels))
1367 26 : continue;
1368 :
1369 : /* Else, prevent join from being formed before we eval the PHV */
1370 57 : min_righthand = bms_add_members(min_righthand, phinfo->ph_eval_at);
1371 : }
1372 :
1373 : /*
1374 : * If we found nothing to put in min_lefthand, punt and make it the full
1375 : * LHS, to avoid having an empty min_lefthand which will confuse later
1376 : * processing. (We don't try to be smart about such cases, just correct.)
1377 : * Likewise for min_righthand.
1378 : */
1379 1493 : if (bms_is_empty(min_lefthand))
1380 19 : min_lefthand = bms_copy(left_rels);
1381 1493 : if (bms_is_empty(min_righthand))
1382 10 : min_righthand = bms_copy(right_rels);
1383 :
1384 : /* Now they'd better be nonempty */
1385 1493 : Assert(!bms_is_empty(min_lefthand));
1386 1493 : Assert(!bms_is_empty(min_righthand));
1387 : /* Shouldn't overlap either */
1388 1493 : Assert(!bms_overlap(min_lefthand, min_righthand));
1389 :
1390 1493 : sjinfo->min_lefthand = min_lefthand;
1391 1493 : sjinfo->min_righthand = min_righthand;
1392 :
1393 1493 : return sjinfo;
1394 : }
1395 :
1396 : /*
1397 : * compute_semijoin_info
1398 : * Fill semijoin-related fields of a new SpecialJoinInfo
1399 : *
1400 : * Note: this relies on only the jointype and syn_righthand fields of the
1401 : * SpecialJoinInfo; the rest may not be set yet.
1402 : */
1403 : static void
1404 1521 : compute_semijoin_info(SpecialJoinInfo *sjinfo, List *clause)
1405 : {
1406 : List *semi_operators;
1407 : List *semi_rhs_exprs;
1408 : bool all_btree;
1409 : bool all_hash;
1410 : ListCell *lc;
1411 :
1412 : /* Initialize semijoin-related fields in case we can't unique-ify */
1413 1521 : sjinfo->semi_can_btree = false;
1414 1521 : sjinfo->semi_can_hash = false;
1415 1521 : sjinfo->semi_operators = NIL;
1416 1521 : sjinfo->semi_rhs_exprs = NIL;
1417 :
1418 : /* Nothing more to do if it's not a semijoin */
1419 1521 : if (sjinfo->jointype != JOIN_SEMI)
1420 1448 : return;
1421 :
1422 : /*
1423 : * Look to see whether the semijoin's join quals consist of AND'ed
1424 : * equality operators, with (only) RHS variables on only one side of each
1425 : * one. If so, we can figure out how to enforce uniqueness for the RHS.
1426 : *
1427 : * Note that the input clause list is the list of quals that are
1428 : * *syntactically* associated with the semijoin, which in practice means
1429 : * the synthesized comparison list for an IN or the WHERE of an EXISTS.
1430 : * Particularly in the latter case, it might contain clauses that aren't
1431 : * *semantically* associated with the join, but refer to just one side or
1432 : * the other. We can ignore such clauses here, as they will just drop
1433 : * down to be processed within one side or the other. (It is okay to
1434 : * consider only the syntactically-associated clauses here because for a
1435 : * semijoin, no higher-level quals could refer to the RHS, and so there
1436 : * can be no other quals that are semantically associated with this join.
1437 : * We do things this way because it is useful to have the set of potential
1438 : * unique-ification expressions before we can extract the list of quals
1439 : * that are actually semantically associated with the particular join.)
1440 : *
1441 : * Note that the semi_operators list consists of the joinqual operators
1442 : * themselves (but commuted if needed to put the RHS value on the right).
1443 : * These could be cross-type operators, in which case the operator
1444 : * actually needed for uniqueness is a related single-type operator. We
1445 : * assume here that that operator will be available from the btree or hash
1446 : * opclass when the time comes ... if not, create_unique_plan() will fail.
1447 : */
1448 73 : semi_operators = NIL;
1449 73 : semi_rhs_exprs = NIL;
1450 73 : all_btree = true;
1451 73 : all_hash = enable_hashagg; /* don't consider hash if not enabled */
1452 157 : foreach(lc, clause)
1453 : {
1454 91 : OpExpr *op = (OpExpr *) lfirst(lc);
1455 : Oid opno;
1456 : Node *left_expr;
1457 : Node *right_expr;
1458 : Relids left_varnos;
1459 : Relids right_varnos;
1460 : Relids all_varnos;
1461 : Oid opinputtype;
1462 :
1463 : /* Is it a binary opclause? */
1464 174 : if (!IsA(op, OpExpr) ||
1465 83 : list_length(op->args) != 2)
1466 : {
1467 : /* No, but does it reference both sides? */
1468 8 : all_varnos = pull_varnos((Node *) op);
1469 15 : if (!bms_overlap(all_varnos, sjinfo->syn_righthand) ||
1470 7 : bms_is_subset(all_varnos, sjinfo->syn_righthand))
1471 : {
1472 : /*
1473 : * Clause refers to only one rel, so ignore it --- unless it
1474 : * contains volatile functions, in which case we'd better
1475 : * punt.
1476 : */
1477 7 : if (contain_volatile_functions((Node *) op))
1478 0 : return;
1479 7 : continue;
1480 : }
1481 : /* Non-operator clause referencing both sides, must punt */
1482 1 : return;
1483 : }
1484 :
1485 : /* Extract data from binary opclause */
1486 83 : opno = op->opno;
1487 83 : left_expr = linitial(op->args);
1488 83 : right_expr = lsecond(op->args);
1489 83 : left_varnos = pull_varnos(left_expr);
1490 83 : right_varnos = pull_varnos(right_expr);
1491 83 : all_varnos = bms_union(left_varnos, right_varnos);
1492 83 : opinputtype = exprType(left_expr);
1493 :
1494 : /* Does it reference both sides? */
1495 166 : if (!bms_overlap(all_varnos, sjinfo->syn_righthand) ||
1496 83 : bms_is_subset(all_varnos, sjinfo->syn_righthand))
1497 : {
1498 : /*
1499 : * Clause refers to only one rel, so ignore it --- unless it
1500 : * contains volatile functions, in which case we'd better punt.
1501 : */
1502 0 : if (contain_volatile_functions((Node *) op))
1503 0 : return;
1504 0 : continue;
1505 : }
1506 :
1507 : /* check rel membership of arguments */
1508 166 : if (!bms_is_empty(right_varnos) &&
1509 137 : bms_is_subset(right_varnos, sjinfo->syn_righthand) &&
1510 54 : !bms_overlap(left_varnos, sjinfo->syn_righthand))
1511 : {
1512 : /* typical case, right_expr is RHS variable */
1513 : }
1514 58 : else if (!bms_is_empty(left_varnos) &&
1515 58 : bms_is_subset(left_varnos, sjinfo->syn_righthand) &&
1516 29 : !bms_overlap(right_varnos, sjinfo->syn_righthand))
1517 : {
1518 : /* flipped case, left_expr is RHS variable */
1519 29 : opno = get_commutator(opno);
1520 29 : if (!OidIsValid(opno))
1521 0 : return;
1522 29 : right_expr = left_expr;
1523 : }
1524 : else
1525 : {
1526 : /* mixed membership of args, punt */
1527 0 : return;
1528 : }
1529 :
1530 : /* all operators must be btree equality or hash equality */
1531 83 : if (all_btree)
1532 : {
1533 : /* oprcanmerge is considered a hint... */
1534 160 : if (!op_mergejoinable(opno, opinputtype) ||
1535 77 : get_mergejoin_opfamilies(opno) == NIL)
1536 6 : all_btree = false;
1537 : }
1538 83 : if (all_hash)
1539 : {
1540 : /* ... but oprcanhash had better be correct */
1541 77 : if (!op_hashjoinable(opno, opinputtype))
1542 11 : all_hash = false;
1543 : }
1544 83 : if (!(all_btree || all_hash))
1545 6 : return;
1546 :
1547 : /* so far so good, keep building lists */
1548 77 : semi_operators = lappend_oid(semi_operators, opno);
1549 77 : semi_rhs_exprs = lappend(semi_rhs_exprs, copyObject(right_expr));
1550 : }
1551 :
1552 : /* Punt if we didn't find at least one column to unique-ify */
1553 66 : if (semi_rhs_exprs == NIL)
1554 1 : return;
1555 :
1556 : /*
1557 : * The expressions we'd need to unique-ify mustn't be volatile.
1558 : */
1559 65 : if (contain_volatile_functions((Node *) semi_rhs_exprs))
1560 0 : return;
1561 :
1562 : /*
1563 : * If we get here, we can unique-ify the semijoin's RHS using at least one
1564 : * of sorting and hashing. Save the information about how to do that.
1565 : */
1566 65 : sjinfo->semi_can_btree = all_btree;
1567 65 : sjinfo->semi_can_hash = all_hash;
1568 65 : sjinfo->semi_operators = semi_operators;
1569 65 : sjinfo->semi_rhs_exprs = semi_rhs_exprs;
1570 : }
1571 :
1572 :
1573 : /*****************************************************************************
1574 : *
1575 : * QUALIFICATIONS
1576 : *
1577 : *****************************************************************************/
1578 :
1579 : /*
1580 : * distribute_qual_to_rels
1581 : * Add clause information to either the baserestrictinfo or joininfo list
1582 : * (depending on whether the clause is a join) of each base relation
1583 : * mentioned in the clause. A RestrictInfo node is created and added to
1584 : * the appropriate list for each rel. Alternatively, if the clause uses a
1585 : * mergejoinable operator and is not delayed by outer-join rules, enter
1586 : * the left- and right-side expressions into the query's list of
1587 : * EquivalenceClasses. Alternatively, if the clause needs to be treated
1588 : * as belonging to a higher join level, just add it to postponed_qual_list.
1589 : *
1590 : * 'clause': the qual clause to be distributed
1591 : * 'is_deduced': TRUE if the qual came from implied-equality deduction
1592 : * 'below_outer_join': TRUE if the qual is from a JOIN/ON that is below the
1593 : * nullable side of a higher-level outer join
1594 : * 'jointype': type of join the qual is from (JOIN_INNER for a WHERE clause)
1595 : * 'security_level': security_level to assign to the qual
1596 : * 'qualscope': set of baserels the qual's syntactic scope covers
1597 : * 'ojscope': NULL if not an outer-join qual, else the minimum set of baserels
1598 : * needed to form this join
1599 : * 'outerjoin_nonnullable': NULL if not an outer-join qual, else the set of
1600 : * baserels appearing on the outer (nonnullable) side of the join
1601 : * (for FULL JOIN this includes both sides of the join, and must in fact
1602 : * equal qualscope)
1603 : * 'deduced_nullable_relids': if is_deduced is TRUE, the nullable relids to
1604 : * impute to the clause; otherwise NULL
1605 : * 'postponed_qual_list': list of PostponedQual structs, which we can add
1606 : * this qual to if it turns out to belong to a higher join level.
1607 : * Can be NULL if caller knows postponement is impossible.
1608 : *
1609 : * 'qualscope' identifies what level of JOIN the qual came from syntactically.
1610 : * 'ojscope' is needed if we decide to force the qual up to the outer-join
1611 : * level, which will be ojscope not necessarily qualscope.
1612 : *
1613 : * In normal use (when is_deduced is FALSE), at the time this is called,
1614 : * root->join_info_list must contain entries for all and only those special
1615 : * joins that are syntactically below this qual. But when is_deduced is TRUE,
1616 : * we are adding new deduced clauses after completion of deconstruct_jointree,
1617 : * so it cannot be assumed that root->join_info_list has anything to do with
1618 : * qual placement.
1619 : */
1620 : static void
1621 18848 : distribute_qual_to_rels(PlannerInfo *root, Node *clause,
1622 : bool is_deduced,
1623 : bool below_outer_join,
1624 : JoinType jointype,
1625 : Index security_level,
1626 : Relids qualscope,
1627 : Relids ojscope,
1628 : Relids outerjoin_nonnullable,
1629 : Relids deduced_nullable_relids,
1630 : List **postponed_qual_list)
1631 : {
1632 : Relids relids;
1633 : bool is_pushed_down;
1634 : bool outerjoin_delayed;
1635 18848 : bool pseudoconstant = false;
1636 : bool maybe_equivalence;
1637 : bool maybe_outer_join;
1638 : Relids nullable_relids;
1639 : RestrictInfo *restrictinfo;
1640 :
1641 : /*
1642 : * Retrieve all relids mentioned within the clause.
1643 : */
1644 18848 : relids = pull_varnos(clause);
1645 :
1646 : /*
1647 : * In ordinary SQL, a WHERE or JOIN/ON clause can't reference any rels
1648 : * that aren't within its syntactic scope; however, if we pulled up a
1649 : * LATERAL subquery then we might find such references in quals that have
1650 : * been pulled up. We need to treat such quals as belonging to the join
1651 : * level that includes every rel they reference. Although we could make
1652 : * pull_up_subqueries() place such quals correctly to begin with, it's
1653 : * easier to handle it here. When we find a clause that contains Vars
1654 : * outside its syntactic scope, we add it to the postponed-quals list, and
1655 : * process it once we've recursed back up to the appropriate join level.
1656 : */
1657 18848 : if (!bms_is_subset(relids, qualscope))
1658 : {
1659 15 : PostponedQual *pq = (PostponedQual *) palloc(sizeof(PostponedQual));
1660 :
1661 15 : Assert(root->hasLateralRTEs); /* shouldn't happen otherwise */
1662 15 : Assert(jointype == JOIN_INNER); /* mustn't postpone past outer join */
1663 15 : Assert(!is_deduced); /* shouldn't be deduced, either */
1664 15 : pq->qual = clause;
1665 15 : pq->relids = relids;
1666 15 : *postponed_qual_list = lappend(*postponed_qual_list, pq);
1667 10903 : return;
1668 : }
1669 :
1670 : /*
1671 : * If it's an outer-join clause, also check that relids is a subset of
1672 : * ojscope. (This should not fail if the syntactic scope check passed.)
1673 : */
1674 18833 : if (ojscope && !bms_is_subset(relids, ojscope))
1675 0 : elog(ERROR, "JOIN qualification cannot refer to other relations");
1676 :
1677 : /*
1678 : * If the clause is variable-free, our normal heuristic for pushing it
1679 : * down to just the mentioned rels doesn't work, because there are none.
1680 : *
1681 : * If the clause is an outer-join clause, we must force it to the OJ's
1682 : * semantic level to preserve semantics.
1683 : *
1684 : * Otherwise, when the clause contains volatile functions, we force it to
1685 : * be evaluated at its original syntactic level. This preserves the
1686 : * expected semantics.
1687 : *
1688 : * When the clause contains no volatile functions either, it is actually a
1689 : * pseudoconstant clause that will not change value during any one
1690 : * execution of the plan, and hence can be used as a one-time qual in a
1691 : * gating Result plan node. We put such a clause into the regular
1692 : * RestrictInfo lists for the moment, but eventually createplan.c will
1693 : * pull it out and make a gating Result node immediately above whatever
1694 : * plan node the pseudoconstant clause is assigned to. It's usually best
1695 : * to put a gating node as high in the plan tree as possible. If we are
1696 : * not below an outer join, we can actually push the pseudoconstant qual
1697 : * all the way to the top of the tree. If we are below an outer join, we
1698 : * leave the qual at its original syntactic level (we could push it up to
1699 : * just below the outer join, but that seems more complex than it's
1700 : * worth).
1701 : */
1702 18833 : if (bms_is_empty(relids))
1703 : {
1704 488 : if (ojscope)
1705 : {
1706 : /* clause is attached to outer join, eval it there */
1707 15 : relids = bms_copy(ojscope);
1708 : /* mustn't use as gating qual, so don't mark pseudoconstant */
1709 : }
1710 : else
1711 : {
1712 : /* eval at original syntactic level */
1713 473 : relids = bms_copy(qualscope);
1714 473 : if (!contain_volatile_functions(clause))
1715 : {
1716 : /* mark as gating qual */
1717 461 : pseudoconstant = true;
1718 : /* tell createplan.c to check for gating quals */
1719 461 : root->hasPseudoConstantQuals = true;
1720 : /* if not below outer join, push it to top of tree */
1721 461 : if (!below_outer_join)
1722 : {
1723 456 : relids =
1724 456 : get_relids_in_jointree((Node *) root->parse->jointree,
1725 : false);
1726 456 : qualscope = bms_copy(relids);
1727 : }
1728 : }
1729 : }
1730 : }
1731 :
1732 : /*----------
1733 : * Check to see if clause application must be delayed by outer-join
1734 : * considerations.
1735 : *
1736 : * A word about is_pushed_down: we mark the qual as "pushed down" if
1737 : * it is (potentially) applicable at a level different from its original
1738 : * syntactic level. This flag is used to distinguish OUTER JOIN ON quals
1739 : * from other quals pushed down to the same joinrel. The rules are:
1740 : * WHERE quals and INNER JOIN quals: is_pushed_down = true.
1741 : * Non-degenerate OUTER JOIN quals: is_pushed_down = false.
1742 : * Degenerate OUTER JOIN quals: is_pushed_down = true.
1743 : * A "degenerate" OUTER JOIN qual is one that doesn't mention the
1744 : * non-nullable side, and hence can be pushed down into the nullable side
1745 : * without changing the join result. It is correct to treat it as a
1746 : * regular filter condition at the level where it is evaluated.
1747 : *
1748 : * Note: it is not immediately obvious that a simple boolean is enough
1749 : * for this: if for some reason we were to attach a degenerate qual to
1750 : * its original join level, it would need to be treated as an outer join
1751 : * qual there. However, this cannot happen, because all the rels the
1752 : * clause mentions must be in the outer join's min_righthand, therefore
1753 : * the join it needs must be formed before the outer join; and we always
1754 : * attach quals to the lowest level where they can be evaluated. But
1755 : * if we were ever to re-introduce a mechanism for delaying evaluation
1756 : * of "expensive" quals, this area would need work.
1757 : *----------
1758 : */
1759 18833 : if (is_deduced)
1760 : {
1761 : /*
1762 : * If the qual came from implied-equality deduction, it should not be
1763 : * outerjoin-delayed, else deducer blew it. But we can't check this
1764 : * because the join_info_list may now contain OJs above where the qual
1765 : * belongs. For the same reason, we must rely on caller to supply the
1766 : * correct nullable_relids set.
1767 : */
1768 857 : Assert(!ojscope);
1769 857 : is_pushed_down = true;
1770 857 : outerjoin_delayed = false;
1771 857 : nullable_relids = deduced_nullable_relids;
1772 : /* Don't feed it back for more deductions */
1773 857 : maybe_equivalence = false;
1774 857 : maybe_outer_join = false;
1775 : }
1776 17976 : else if (bms_overlap(relids, outerjoin_nonnullable))
1777 : {
1778 : /*
1779 : * The qual is attached to an outer join and mentions (some of the)
1780 : * rels on the nonnullable side, so it's not degenerate.
1781 : *
1782 : * We can't use such a clause to deduce equivalence (the left and
1783 : * right sides might be unequal above the join because one of them has
1784 : * gone to NULL) ... but we might be able to use it for more limited
1785 : * deductions, if it is mergejoinable. So consider adding it to the
1786 : * lists of set-aside outer-join clauses.
1787 : */
1788 1582 : is_pushed_down = false;
1789 1582 : maybe_equivalence = false;
1790 1582 : maybe_outer_join = true;
1791 :
1792 : /* Check to see if must be delayed by lower outer join */
1793 1582 : outerjoin_delayed = check_outerjoin_delay(root,
1794 : &relids,
1795 : &nullable_relids,
1796 : false);
1797 :
1798 : /*
1799 : * Now force the qual to be evaluated exactly at the level of joining
1800 : * corresponding to the outer join. We cannot let it get pushed down
1801 : * into the nonnullable side, since then we'd produce no output rows,
1802 : * rather than the intended single null-extended row, for any
1803 : * nonnullable-side rows failing the qual.
1804 : *
1805 : * (Do this step after calling check_outerjoin_delay, because that
1806 : * trashes relids.)
1807 : */
1808 1582 : Assert(ojscope);
1809 1582 : relids = ojscope;
1810 1582 : Assert(!pseudoconstant);
1811 : }
1812 : else
1813 : {
1814 : /*
1815 : * Normal qual clause or degenerate outer-join clause. Either way, we
1816 : * can mark it as pushed-down.
1817 : */
1818 16394 : is_pushed_down = true;
1819 :
1820 : /* Check to see if must be delayed by lower outer join */
1821 16394 : outerjoin_delayed = check_outerjoin_delay(root,
1822 : &relids,
1823 : &nullable_relids,
1824 : true);
1825 :
1826 16394 : if (outerjoin_delayed)
1827 : {
1828 : /* Should still be a subset of current scope ... */
1829 49 : Assert(root->hasLateralRTEs || bms_is_subset(relids, qualscope));
1830 49 : Assert(ojscope == NULL || bms_is_subset(relids, ojscope));
1831 :
1832 : /*
1833 : * Because application of the qual will be delayed by outer join,
1834 : * we mustn't assume its vars are equal everywhere.
1835 : */
1836 49 : maybe_equivalence = false;
1837 :
1838 : /*
1839 : * It's possible that this is an IS NULL clause that's redundant
1840 : * with a lower antijoin; if so we can just discard it. We need
1841 : * not test in any of the other cases, because this will only be
1842 : * possible for pushed-down, delayed clauses.
1843 : */
1844 49 : if (check_redundant_nullability_qual(root, clause))
1845 34 : return;
1846 : }
1847 : else
1848 : {
1849 : /*
1850 : * Qual is not delayed by any lower outer-join restriction, so we
1851 : * can consider feeding it to the equivalence machinery. However,
1852 : * if it's itself within an outer-join clause, treat it as though
1853 : * it appeared below that outer join (note that we can only get
1854 : * here when the clause references only nullable-side rels).
1855 : */
1856 16345 : maybe_equivalence = true;
1857 16345 : if (outerjoin_nonnullable != NULL)
1858 355 : below_outer_join = true;
1859 : }
1860 :
1861 : /*
1862 : * Since it doesn't mention the LHS, it's certainly not useful as a
1863 : * set-aside OJ clause, even if it's in an OJ.
1864 : */
1865 16360 : maybe_outer_join = false;
1866 : }
1867 :
1868 : /*
1869 : * Build the RestrictInfo node itself.
1870 : */
1871 18799 : restrictinfo = make_restrictinfo((Expr *) clause,
1872 : is_pushed_down,
1873 : outerjoin_delayed,
1874 : pseudoconstant,
1875 : security_level,
1876 : relids,
1877 : outerjoin_nonnullable,
1878 : nullable_relids);
1879 :
1880 : /*
1881 : * If it's a join clause (either naturally, or because delayed by
1882 : * outer-join rules), add vars used in the clause to targetlists of their
1883 : * relations, so that they will be emitted by the plan nodes that scan
1884 : * those relations (else they won't be available at the join node!).
1885 : *
1886 : * Note: if the clause gets absorbed into an EquivalenceClass then this
1887 : * may be unnecessary, but for now we have to do it to cover the case
1888 : * where the EC becomes ec_broken and we end up reinserting the original
1889 : * clauses into the plan.
1890 : */
1891 18799 : if (bms_membership(relids) == BMS_MULTIPLE)
1892 : {
1893 4078 : List *vars = pull_var_clause(clause,
1894 : PVC_RECURSE_AGGREGATES |
1895 : PVC_RECURSE_WINDOWFUNCS |
1896 : PVC_INCLUDE_PLACEHOLDERS);
1897 :
1898 4078 : add_vars_to_targetlist(root, vars, relids, false);
1899 4078 : list_free(vars);
1900 : }
1901 :
1902 : /*
1903 : * We check "mergejoinability" of every clause, not only join clauses,
1904 : * because we want to know about equivalences between vars of the same
1905 : * relation, or between vars and consts.
1906 : */
1907 18799 : check_mergejoinable(restrictinfo);
1908 :
1909 : /*
1910 : * If it is a true equivalence clause, send it to the EquivalenceClass
1911 : * machinery. We do *not* attach it directly to any restriction or join
1912 : * lists. The EC code will propagate it to the appropriate places later.
1913 : *
1914 : * If the clause has a mergejoinable operator and is not
1915 : * outerjoin-delayed, yet isn't an equivalence because it is an outer-join
1916 : * clause, the EC code may yet be able to do something with it. We add it
1917 : * to appropriate lists for further consideration later. Specifically:
1918 : *
1919 : * If it is a left or right outer-join qualification that relates the two
1920 : * sides of the outer join (no funny business like leftvar1 = leftvar2 +
1921 : * rightvar), we add it to root->left_join_clauses or
1922 : * root->right_join_clauses according to which side the nonnullable
1923 : * variable appears on.
1924 : *
1925 : * If it is a full outer-join qualification, we add it to
1926 : * root->full_join_clauses. (Ideally we'd discard cases that aren't
1927 : * leftvar = rightvar, as we do for left/right joins, but this routine
1928 : * doesn't have the info needed to do that; and the current usage of the
1929 : * full_join_clauses list doesn't require that, so it's not currently
1930 : * worth complicating this routine's API to make it possible.)
1931 : *
1932 : * If none of the above hold, pass it off to
1933 : * distribute_restrictinfo_to_rels().
1934 : *
1935 : * In all cases, it's important to initialize the left_ec and right_ec
1936 : * fields of a mergejoinable clause, so that all possibly mergejoinable
1937 : * expressions have representations in EquivalenceClasses. If
1938 : * process_equivalence is successful, it will take care of that;
1939 : * otherwise, we have to call initialize_mergeclause_eclasses to do it.
1940 : */
1941 18799 : if (restrictinfo->mergeopfamilies)
1942 : {
1943 11733 : if (maybe_equivalence)
1944 : {
1945 18636 : if (check_equivalence_delay(root, restrictinfo) &&
1946 9316 : process_equivalence(root, restrictinfo, below_outer_join))
1947 9305 : return;
1948 : /* EC rejected it, so set left_ec/right_ec the hard way ... */
1949 15 : initialize_mergeclause_eclasses(root, restrictinfo);
1950 : /* ... and fall through to distribute_restrictinfo_to_rels */
1951 : }
1952 2413 : else if (maybe_outer_join && restrictinfo->can_join)
1953 : {
1954 : /* we need to set up left_ec/right_ec the hard way */
1955 1537 : initialize_mergeclause_eclasses(root, restrictinfo);
1956 : /* now see if it should go to any outer-join lists */
1957 1537 : if (bms_is_subset(restrictinfo->left_relids,
1958 819 : outerjoin_nonnullable) &&
1959 819 : !bms_overlap(restrictinfo->right_relids,
1960 : outerjoin_nonnullable))
1961 : {
1962 : /* we have outervar = innervar */
1963 784 : root->left_join_clauses = lappend(root->left_join_clauses,
1964 : restrictinfo);
1965 784 : return;
1966 : }
1967 753 : if (bms_is_subset(restrictinfo->right_relids,
1968 752 : outerjoin_nonnullable) &&
1969 752 : !bms_overlap(restrictinfo->left_relids,
1970 : outerjoin_nonnullable))
1971 : {
1972 : /* we have innervar = outervar */
1973 717 : root->right_join_clauses = lappend(root->right_join_clauses,
1974 : restrictinfo);
1975 717 : return;
1976 : }
1977 39 : if (jointype == JOIN_FULL)
1978 : {
1979 : /* FULL JOIN (above tests cannot match in this case) */
1980 33 : root->full_join_clauses = lappend(root->full_join_clauses,
1981 : restrictinfo);
1982 33 : return;
1983 : }
1984 : /* nope, so fall through to distribute_restrictinfo_to_rels */
1985 : }
1986 : else
1987 : {
1988 : /* we still need to set up left_ec/right_ec */
1989 876 : initialize_mergeclause_eclasses(root, restrictinfo);
1990 : }
1991 : }
1992 :
1993 : /* No EC special case applies, so push it into the clause lists */
1994 7960 : distribute_restrictinfo_to_rels(root, restrictinfo);
1995 : }
1996 :
1997 : /*
1998 : * check_outerjoin_delay
1999 : * Detect whether a qual referencing the given relids must be delayed
2000 : * in application due to the presence of a lower outer join, and/or
2001 : * may force extra delay of higher-level outer joins.
2002 : *
2003 : * If the qual must be delayed, add relids to *relids_p to reflect the lowest
2004 : * safe level for evaluating the qual, and return TRUE. Any extra delay for
2005 : * higher-level joins is reflected by setting delay_upper_joins to TRUE in
2006 : * SpecialJoinInfo structs. We also compute nullable_relids, the set of
2007 : * referenced relids that are nullable by lower outer joins (note that this
2008 : * can be nonempty even for a non-delayed qual).
2009 : *
2010 : * For an is_pushed_down qual, we can evaluate the qual as soon as (1) we have
2011 : * all the rels it mentions, and (2) we are at or above any outer joins that
2012 : * can null any of these rels and are below the syntactic location of the
2013 : * given qual. We must enforce (2) because pushing down such a clause below
2014 : * the OJ might cause the OJ to emit null-extended rows that should not have
2015 : * been formed, or that should have been rejected by the clause. (This is
2016 : * only an issue for non-strict quals, since if we can prove a qual mentioning
2017 : * only nullable rels is strict, we'd have reduced the outer join to an inner
2018 : * join in reduce_outer_joins().)
2019 : *
2020 : * To enforce (2), scan the join_info_list and merge the required-relid sets of
2021 : * any such OJs into the clause's own reference list. At the time we are
2022 : * called, the join_info_list contains only outer joins below this qual. We
2023 : * have to repeat the scan until no new relids get added; this ensures that
2024 : * the qual is suitably delayed regardless of the order in which OJs get
2025 : * executed. As an example, if we have one OJ with LHS=A, RHS=B, and one with
2026 : * LHS=B, RHS=C, it is implied that these can be done in either order; if the
2027 : * B/C join is done first then the join to A can null C, so a qual actually
2028 : * mentioning only C cannot be applied below the join to A.
2029 : *
2030 : * For a non-pushed-down qual, this isn't going to determine where we place the
2031 : * qual, but we need to determine outerjoin_delayed and nullable_relids anyway
2032 : * for use later in the planning process.
2033 : *
2034 : * Lastly, a pushed-down qual that references the nullable side of any current
2035 : * join_info_list member and has to be evaluated above that OJ (because its
2036 : * required relids overlap the LHS too) causes that OJ's delay_upper_joins
2037 : * flag to be set TRUE. This will prevent any higher-level OJs from
2038 : * being interchanged with that OJ, which would result in not having any
2039 : * correct place to evaluate the qual. (The case we care about here is a
2040 : * sub-select WHERE clause within the RHS of some outer join. The WHERE
2041 : * clause must effectively be treated as a degenerate clause of that outer
2042 : * join's condition. Rather than trying to match such clauses with joins
2043 : * directly, we set delay_upper_joins here, and when the upper outer join
2044 : * is processed by make_outerjoininfo, it will refrain from allowing the
2045 : * two OJs to commute.)
2046 : */
2047 : static bool
2048 19428 : check_outerjoin_delay(PlannerInfo *root,
2049 : Relids *relids_p, /* in/out parameter */
2050 : Relids *nullable_relids_p, /* output parameter */
2051 : bool is_pushed_down)
2052 : {
2053 : Relids relids;
2054 : Relids nullable_relids;
2055 : bool outerjoin_delayed;
2056 : bool found_some;
2057 :
2058 : /* fast path if no special joins */
2059 19428 : if (root->join_info_list == NIL)
2060 : {
2061 16042 : *nullable_relids_p = NULL;
2062 16042 : return false;
2063 : }
2064 :
2065 : /* must copy relids because we need the original value at the end */
2066 3386 : relids = bms_copy(*relids_p);
2067 3386 : nullable_relids = NULL;
2068 3386 : outerjoin_delayed = false;
2069 : do
2070 : {
2071 : ListCell *l;
2072 :
2073 3468 : found_some = false;
2074 8092 : foreach(l, root->join_info_list)
2075 : {
2076 4624 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(l);
2077 :
2078 : /* do we reference any nullable rels of this OJ? */
2079 9021 : if (bms_overlap(relids, sjinfo->min_righthand) ||
2080 4400 : (sjinfo->jointype == JOIN_FULL &&
2081 3 : bms_overlap(relids, sjinfo->min_lefthand)))
2082 : {
2083 : /* yes; have we included all its rels in relids? */
2084 366 : if (!bms_is_subset(sjinfo->min_lefthand, relids) ||
2085 139 : !bms_is_subset(sjinfo->min_righthand, relids))
2086 : {
2087 : /* no, so add them in */
2088 88 : relids = bms_add_members(relids, sjinfo->min_lefthand);
2089 88 : relids = bms_add_members(relids, sjinfo->min_righthand);
2090 88 : outerjoin_delayed = true;
2091 : /* we'll need another iteration */
2092 88 : found_some = true;
2093 : }
2094 : /* track all the nullable rels of relevant OJs */
2095 227 : nullable_relids = bms_add_members(nullable_relids,
2096 227 : sjinfo->min_righthand);
2097 227 : if (sjinfo->jointype == JOIN_FULL)
2098 19 : nullable_relids = bms_add_members(nullable_relids,
2099 19 : sjinfo->min_lefthand);
2100 : /* set delay_upper_joins if needed */
2101 360 : if (is_pushed_down && sjinfo->jointype != JOIN_FULL &&
2102 133 : bms_overlap(relids, sjinfo->min_lefthand))
2103 133 : sjinfo->delay_upper_joins = true;
2104 : }
2105 : }
2106 3468 : } while (found_some);
2107 :
2108 : /* identify just the actually-referenced nullable rels */
2109 3386 : nullable_relids = bms_int_members(nullable_relids, *relids_p);
2110 :
2111 : /* replace *relids_p, and return nullable_relids */
2112 3386 : bms_free(*relids_p);
2113 3386 : *relids_p = relids;
2114 3386 : *nullable_relids_p = nullable_relids;
2115 3386 : return outerjoin_delayed;
2116 : }
2117 :
2118 : /*
2119 : * check_equivalence_delay
2120 : * Detect whether a potential equivalence clause is rendered unsafe
2121 : * by outer-join-delay considerations. Return TRUE if it's safe.
2122 : *
2123 : * The initial tests in distribute_qual_to_rels will consider a mergejoinable
2124 : * clause to be a potential equivalence clause if it is not outerjoin_delayed.
2125 : * But since the point of equivalence processing is that we will recombine the
2126 : * two sides of the clause with others, we have to check that each side
2127 : * satisfies the not-outerjoin_delayed condition on its own; otherwise it might
2128 : * not be safe to evaluate everywhere we could place a derived equivalence
2129 : * condition.
2130 : */
2131 : static bool
2132 9320 : check_equivalence_delay(PlannerInfo *root,
2133 : RestrictInfo *restrictinfo)
2134 : {
2135 : Relids relids;
2136 : Relids nullable_relids;
2137 :
2138 : /* fast path if no special joins */
2139 9320 : if (root->join_info_list == NIL)
2140 8593 : return true;
2141 :
2142 : /* must copy restrictinfo's relids to avoid changing it */
2143 727 : relids = bms_copy(restrictinfo->left_relids);
2144 : /* check left side does not need delay */
2145 727 : if (check_outerjoin_delay(root, &relids, &nullable_relids, true))
2146 2 : return false;
2147 :
2148 : /* and similarly for the right side */
2149 725 : relids = bms_copy(restrictinfo->right_relids);
2150 725 : if (check_outerjoin_delay(root, &relids, &nullable_relids, true))
2151 2 : return false;
2152 :
2153 723 : return true;
2154 : }
2155 :
2156 : /*
2157 : * check_redundant_nullability_qual
2158 : * Check to see if the qual is an IS NULL qual that is redundant with
2159 : * a lower JOIN_ANTI join.
2160 : *
2161 : * We want to suppress redundant IS NULL quals, not so much to save cycles
2162 : * as to avoid generating bogus selectivity estimates for them. So if
2163 : * redundancy is detected here, distribute_qual_to_rels() just throws away
2164 : * the qual.
2165 : */
2166 : static bool
2167 49 : check_redundant_nullability_qual(PlannerInfo *root, Node *clause)
2168 : {
2169 : Var *forced_null_var;
2170 : Index forced_null_rel;
2171 : ListCell *lc;
2172 :
2173 : /* Check for IS NULL, and identify the Var forced to NULL */
2174 49 : forced_null_var = find_forced_null_var(clause);
2175 49 : if (forced_null_var == NULL)
2176 11 : return false;
2177 38 : forced_null_rel = forced_null_var->varno;
2178 :
2179 : /*
2180 : * If the Var comes from the nullable side of a lower antijoin, the IS
2181 : * NULL condition is necessarily true.
2182 : */
2183 43 : foreach(lc, root->join_info_list)
2184 : {
2185 39 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
2186 :
2187 74 : if (sjinfo->jointype == JOIN_ANTI &&
2188 35 : bms_is_member(forced_null_rel, sjinfo->syn_righthand))
2189 34 : return true;
2190 : }
2191 :
2192 4 : return false;
2193 : }
2194 :
2195 : /*
2196 : * distribute_restrictinfo_to_rels
2197 : * Push a completed RestrictInfo into the proper restriction or join
2198 : * clause list(s).
2199 : *
2200 : * This is the last step of distribute_qual_to_rels() for ordinary qual
2201 : * clauses. Clauses that are interesting for equivalence-class processing
2202 : * are diverted to the EC machinery, but may ultimately get fed back here.
2203 : */
2204 : void
2205 16124 : distribute_restrictinfo_to_rels(PlannerInfo *root,
2206 : RestrictInfo *restrictinfo)
2207 : {
2208 16124 : Relids relids = restrictinfo->required_relids;
2209 : RelOptInfo *rel;
2210 :
2211 16124 : switch (bms_membership(relids))
2212 : {
2213 : case BMS_SINGLETON:
2214 :
2215 : /*
2216 : * There is only one relation participating in the clause, so it
2217 : * is a restriction clause for that relation.
2218 : */
2219 14277 : rel = find_base_rel(root, bms_singleton_member(relids));
2220 :
2221 : /* Add clause to rel's restriction list */
2222 14277 : rel->baserestrictinfo = lappend(rel->baserestrictinfo,
2223 : restrictinfo);
2224 : /* Update security level info */
2225 14277 : rel->baserestrict_min_security = Min(rel->baserestrict_min_security,
2226 : restrictinfo->security_level);
2227 14277 : break;
2228 : case BMS_MULTIPLE:
2229 :
2230 : /*
2231 : * The clause is a join clause, since there is more than one rel
2232 : * in its relid set.
2233 : */
2234 :
2235 : /*
2236 : * Check for hashjoinable operators. (We don't bother setting the
2237 : * hashjoin info except in true join clauses.)
2238 : */
2239 1847 : check_hashjoinable(restrictinfo);
2240 :
2241 : /*
2242 : * Add clause to the join lists of all the relevant relations.
2243 : */
2244 1847 : add_join_clause_to_rels(root, restrictinfo, relids);
2245 1847 : break;
2246 : default:
2247 :
2248 : /*
2249 : * clause references no rels, and therefore we have no place to
2250 : * attach it. Shouldn't get here if callers are working properly.
2251 : */
2252 0 : elog(ERROR, "cannot cope with variable-free clause");
2253 : break;
2254 : }
2255 16124 : }
2256 :
2257 : /*
2258 : * process_implied_equality
2259 : * Create a restrictinfo item that says "item1 op item2", and push it
2260 : * into the appropriate lists. (In practice opno is always a btree
2261 : * equality operator.)
2262 : *
2263 : * "qualscope" is the nominal syntactic level to impute to the restrictinfo.
2264 : * This must contain at least all the rels used in the expressions, but it
2265 : * is used only to set the qual application level when both exprs are
2266 : * variable-free. Otherwise the qual is applied at the lowest join level
2267 : * that provides all its variables.
2268 : *
2269 : * "nullable_relids" is the set of relids used in the expressions that are
2270 : * potentially nullable below the expressions. (This has to be supplied by
2271 : * caller because this function is used after deconstruct_jointree, so we
2272 : * don't have knowledge of where the clause items came from.)
2273 : *
2274 : * "security_level" is the security level to assign to the new restrictinfo.
2275 : *
2276 : * "both_const" indicates whether both items are known pseudo-constant;
2277 : * in this case it is worth applying eval_const_expressions() in case we
2278 : * can produce constant TRUE or constant FALSE. (Otherwise it's not,
2279 : * because the expressions went through eval_const_expressions already.)
2280 : *
2281 : * Note: this function will copy item1 and item2, but it is caller's
2282 : * responsibility to make sure that the Relids parameters are fresh copies
2283 : * not shared with other uses.
2284 : *
2285 : * This is currently used only when an EquivalenceClass is found to
2286 : * contain pseudoconstants. See path/pathkeys.c for more details.
2287 : */
2288 : void
2289 857 : process_implied_equality(PlannerInfo *root,
2290 : Oid opno,
2291 : Oid collation,
2292 : Expr *item1,
2293 : Expr *item2,
2294 : Relids qualscope,
2295 : Relids nullable_relids,
2296 : Index security_level,
2297 : bool below_outer_join,
2298 : bool both_const)
2299 : {
2300 : Expr *clause;
2301 :
2302 : /*
2303 : * Build the new clause. Copy to ensure it shares no substructure with
2304 : * original (this is necessary in case there are subselects in there...)
2305 : */
2306 857 : clause = make_opclause(opno,
2307 : BOOLOID, /* opresulttype */
2308 : false, /* opretset */
2309 857 : copyObject(item1),
2310 857 : copyObject(item2),
2311 : InvalidOid,
2312 : collation);
2313 :
2314 : /* If both constant, try to reduce to a boolean constant. */
2315 857 : if (both_const)
2316 : {
2317 9 : clause = (Expr *) eval_const_expressions(root, (Node *) clause);
2318 :
2319 : /* If we produced const TRUE, just drop the clause */
2320 9 : if (clause && IsA(clause, Const))
2321 : {
2322 9 : Const *cclause = (Const *) clause;
2323 :
2324 9 : Assert(cclause->consttype == BOOLOID);
2325 9 : if (!cclause->constisnull && DatumGetBool(cclause->constvalue))
2326 857 : return;
2327 : }
2328 : }
2329 :
2330 : /*
2331 : * Push the new clause into all the appropriate restrictinfo lists.
2332 : */
2333 857 : distribute_qual_to_rels(root, (Node *) clause,
2334 : true, below_outer_join, JOIN_INNER,
2335 : security_level,
2336 : qualscope, NULL, NULL, nullable_relids,
2337 : NULL);
2338 : }
2339 :
2340 : /*
2341 : * build_implied_join_equality --- build a RestrictInfo for a derived equality
2342 : *
2343 : * This overlaps the functionality of process_implied_equality(), but we
2344 : * must return the RestrictInfo, not push it into the joininfo tree.
2345 : *
2346 : * Note: this function will copy item1 and item2, but it is caller's
2347 : * responsibility to make sure that the Relids parameters are fresh copies
2348 : * not shared with other uses.
2349 : *
2350 : * Note: we do not do initialize_mergeclause_eclasses() here. It is
2351 : * caller's responsibility that left_ec/right_ec be set as necessary.
2352 : */
2353 : RestrictInfo *
2354 3734 : build_implied_join_equality(Oid opno,
2355 : Oid collation,
2356 : Expr *item1,
2357 : Expr *item2,
2358 : Relids qualscope,
2359 : Relids nullable_relids,
2360 : Index security_level)
2361 : {
2362 : RestrictInfo *restrictinfo;
2363 : Expr *clause;
2364 :
2365 : /*
2366 : * Build the new clause. Copy to ensure it shares no substructure with
2367 : * original (this is necessary in case there are subselects in there...)
2368 : */
2369 3734 : clause = make_opclause(opno,
2370 : BOOLOID, /* opresulttype */
2371 : false, /* opretset */
2372 3734 : copyObject(item1),
2373 3734 : copyObject(item2),
2374 : InvalidOid,
2375 : collation);
2376 :
2377 : /*
2378 : * Build the RestrictInfo node itself.
2379 : */
2380 3734 : restrictinfo = make_restrictinfo(clause,
2381 : true, /* is_pushed_down */
2382 : false, /* outerjoin_delayed */
2383 : false, /* pseudoconstant */
2384 : security_level, /* security_level */
2385 : qualscope, /* required_relids */
2386 : NULL, /* outer_relids */
2387 : nullable_relids); /* nullable_relids */
2388 :
2389 : /* Set mergejoinability/hashjoinability flags */
2390 3734 : check_mergejoinable(restrictinfo);
2391 3734 : check_hashjoinable(restrictinfo);
2392 :
2393 3734 : return restrictinfo;
2394 : }
2395 :
2396 :
2397 : /*
2398 : * match_foreign_keys_to_quals
2399 : * Match foreign-key constraints to equivalence classes and join quals
2400 : *
2401 : * The idea here is to see which query join conditions match equality
2402 : * constraints of a foreign-key relationship. For such join conditions,
2403 : * we can use the FK semantics to make selectivity estimates that are more
2404 : * reliable than estimating from statistics, especially for multiple-column
2405 : * FKs, where the normal assumption of independent conditions tends to fail.
2406 : *
2407 : * In this function we annotate the ForeignKeyOptInfos in root->fkey_list
2408 : * with info about which eclasses and join qual clauses they match, and
2409 : * discard any ForeignKeyOptInfos that are irrelevant for the query.
2410 : */
2411 : void
2412 13818 : match_foreign_keys_to_quals(PlannerInfo *root)
2413 : {
2414 13818 : List *newlist = NIL;
2415 : ListCell *lc;
2416 :
2417 13960 : foreach(lc, root->fkey_list)
2418 : {
2419 142 : ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
2420 : RelOptInfo *con_rel;
2421 : RelOptInfo *ref_rel;
2422 : int colno;
2423 :
2424 : /*
2425 : * Either relid might identify a rel that is in the query's rtable but
2426 : * isn't referenced by the jointree so won't have a RelOptInfo. Hence
2427 : * don't use find_base_rel() here. We can ignore such FKs.
2428 : */
2429 284 : if (fkinfo->con_relid >= root->simple_rel_array_size ||
2430 142 : fkinfo->ref_relid >= root->simple_rel_array_size)
2431 0 : continue; /* just paranoia */
2432 142 : con_rel = root->simple_rel_array[fkinfo->con_relid];
2433 142 : if (con_rel == NULL)
2434 0 : continue;
2435 142 : ref_rel = root->simple_rel_array[fkinfo->ref_relid];
2436 142 : if (ref_rel == NULL)
2437 4 : continue;
2438 :
2439 : /*
2440 : * Ignore FK unless both rels are baserels. This gets rid of FKs that
2441 : * link to inheritance child rels (otherrels) and those that link to
2442 : * rels removed by join removal (dead rels).
2443 : */
2444 276 : if (con_rel->reloptkind != RELOPT_BASEREL ||
2445 138 : ref_rel->reloptkind != RELOPT_BASEREL)
2446 0 : continue;
2447 :
2448 : /*
2449 : * Scan the columns and try to match them to eclasses and quals.
2450 : *
2451 : * Note: for simple inner joins, any match should be in an eclass.
2452 : * "Loose" quals that syntactically match an FK equality must have
2453 : * been rejected for EC status because they are outer-join quals or
2454 : * similar. We can still consider them to match the FK if they are
2455 : * not outerjoin_delayed.
2456 : */
2457 294 : for (colno = 0; colno < fkinfo->nkeys; colno++)
2458 : {
2459 : AttrNumber con_attno,
2460 : ref_attno;
2461 : Oid fpeqop;
2462 : ListCell *lc2;
2463 :
2464 156 : fkinfo->eclass[colno] = match_eclasses_to_foreign_key_col(root,
2465 : fkinfo,
2466 : colno);
2467 : /* Don't bother looking for loose quals if we got an EC match */
2468 156 : if (fkinfo->eclass[colno] != NULL)
2469 : {
2470 31 : fkinfo->nmatched_ec++;
2471 31 : continue;
2472 : }
2473 :
2474 : /*
2475 : * Scan joininfo list for relevant clauses. Either rel's joininfo
2476 : * list would do equally well; we use con_rel's.
2477 : */
2478 125 : con_attno = fkinfo->conkey[colno];
2479 125 : ref_attno = fkinfo->confkey[colno];
2480 125 : fpeqop = InvalidOid; /* we'll look this up only if needed */
2481 :
2482 327 : foreach(lc2, con_rel->joininfo)
2483 : {
2484 202 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc2);
2485 202 : OpExpr *clause = (OpExpr *) rinfo->clause;
2486 : Var *leftvar;
2487 : Var *rightvar;
2488 :
2489 : /* Ignore outerjoin-delayed clauses */
2490 202 : if (rinfo->outerjoin_delayed)
2491 0 : continue;
2492 :
2493 : /* Only binary OpExprs are useful for consideration */
2494 404 : if (!IsA(clause, OpExpr) ||
2495 202 : list_length(clause->args) != 2)
2496 0 : continue;
2497 202 : leftvar = (Var *) get_leftop((Expr *) clause);
2498 202 : rightvar = (Var *) get_rightop((Expr *) clause);
2499 :
2500 : /* Operands must be Vars, possibly with RelabelType */
2501 445 : while (leftvar && IsA(leftvar, RelabelType))
2502 41 : leftvar = (Var *) ((RelabelType *) leftvar)->arg;
2503 202 : if (!(leftvar && IsA(leftvar, Var)))
2504 0 : continue;
2505 442 : while (rightvar && IsA(rightvar, RelabelType))
2506 38 : rightvar = (Var *) ((RelabelType *) rightvar)->arg;
2507 202 : if (!(rightvar && IsA(rightvar, Var)))
2508 5 : continue;
2509 :
2510 : /* Now try to match the vars to the current foreign key cols */
2511 386 : if (fkinfo->ref_relid == leftvar->varno &&
2512 287 : ref_attno == leftvar->varattno &&
2513 196 : fkinfo->con_relid == rightvar->varno &&
2514 98 : con_attno == rightvar->varattno)
2515 : {
2516 : /* Vars match, but is it the right operator? */
2517 170 : if (clause->opno == fkinfo->conpfeqop[colno])
2518 : {
2519 85 : fkinfo->rinfos[colno] = lappend(fkinfo->rinfos[colno],
2520 : rinfo);
2521 85 : fkinfo->nmatched_ri++;
2522 : }
2523 : }
2524 114 : else if (fkinfo->ref_relid == rightvar->varno &&
2525 4 : ref_attno == rightvar->varattno &&
2526 4 : fkinfo->con_relid == leftvar->varno &&
2527 2 : con_attno == leftvar->varattno)
2528 : {
2529 : /*
2530 : * Reverse match, must check commutator operator. Look it
2531 : * up if we didn't already. (In the worst case we might
2532 : * do multiple lookups here, but that would require an FK
2533 : * equality operator without commutator, which is
2534 : * unlikely.)
2535 : */
2536 2 : if (!OidIsValid(fpeqop))
2537 2 : fpeqop = get_commutator(fkinfo->conpfeqop[colno]);
2538 2 : if (clause->opno == fpeqop)
2539 : {
2540 2 : fkinfo->rinfos[colno] = lappend(fkinfo->rinfos[colno],
2541 : rinfo);
2542 2 : fkinfo->nmatched_ri++;
2543 : }
2544 : }
2545 : }
2546 : /* If we found any matching loose quals, count col as matched */
2547 125 : if (fkinfo->rinfos[colno])
2548 87 : fkinfo->nmatched_rcols++;
2549 : }
2550 :
2551 : /*
2552 : * Currently, we drop multicolumn FKs that aren't fully matched to the
2553 : * query. Later we might figure out how to derive some sort of
2554 : * estimate from them, in which case this test should be weakened to
2555 : * "if ((fkinfo->nmatched_ec + fkinfo->nmatched_rcols) > 0)".
2556 : */
2557 138 : if ((fkinfo->nmatched_ec + fkinfo->nmatched_rcols) == fkinfo->nkeys)
2558 100 : newlist = lappend(newlist, fkinfo);
2559 : }
2560 : /* Replace fkey_list, thereby discarding any useless entries */
2561 13818 : root->fkey_list = newlist;
2562 13818 : }
2563 :
2564 :
2565 : /*****************************************************************************
2566 : *
2567 : * CHECKS FOR MERGEJOINABLE AND HASHJOINABLE CLAUSES
2568 : *
2569 : *****************************************************************************/
2570 :
2571 : /*
2572 : * check_mergejoinable
2573 : * If the restrictinfo's clause is mergejoinable, set the mergejoin
2574 : * info fields in the restrictinfo.
2575 : *
2576 : * Currently, we support mergejoin for binary opclauses where
2577 : * the operator is a mergejoinable operator. The arguments can be
2578 : * anything --- as long as there are no volatile functions in them.
2579 : */
2580 : static void
2581 22533 : check_mergejoinable(RestrictInfo *restrictinfo)
2582 : {
2583 22533 : Expr *clause = restrictinfo->clause;
2584 : Oid opno;
2585 : Node *leftarg;
2586 :
2587 22533 : if (restrictinfo->pseudoconstant)
2588 461 : return;
2589 22072 : if (!is_opclause(clause))
2590 2926 : return;
2591 19146 : if (list_length(((OpExpr *) clause)->args) != 2)
2592 0 : return;
2593 :
2594 19146 : opno = ((OpExpr *) clause)->opno;
2595 19146 : leftarg = linitial(((OpExpr *) clause)->args);
2596 :
2597 34614 : if (op_mergejoinable(opno, exprType(leftarg)) &&
2598 15468 : !contain_volatile_functions((Node *) clause))
2599 15467 : restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);
2600 :
2601 : /*
2602 : * Note: op_mergejoinable is just a hint; if we fail to find the operator
2603 : * in any btree opfamilies, mergeopfamilies remains NIL and so the clause
2604 : * is not treated as mergejoinable.
2605 : */
2606 : }
2607 :
2608 : /*
2609 : * check_hashjoinable
2610 : * If the restrictinfo's clause is hashjoinable, set the hashjoin
2611 : * info fields in the restrictinfo.
2612 : *
2613 : * Currently, we support hashjoin for binary opclauses where
2614 : * the operator is a hashjoinable operator. The arguments can be
2615 : * anything --- as long as there are no volatile functions in them.
2616 : */
2617 : static void
2618 5581 : check_hashjoinable(RestrictInfo *restrictinfo)
2619 : {
2620 5581 : Expr *clause = restrictinfo->clause;
2621 : Oid opno;
2622 : Node *leftarg;
2623 :
2624 5581 : if (restrictinfo->pseudoconstant)
2625 27 : return;
2626 5554 : if (!is_opclause(clause))
2627 129 : return;
2628 5425 : if (list_length(((OpExpr *) clause)->args) != 2)
2629 0 : return;
2630 :
2631 5425 : opno = ((OpExpr *) clause)->opno;
2632 5425 : leftarg = linitial(((OpExpr *) clause)->args);
2633 :
2634 10701 : if (op_hashjoinable(opno, exprType(leftarg)) &&
2635 5276 : !contain_volatile_functions((Node *) clause))
2636 5276 : restrictinfo->hashjoinoperator = opno;
2637 : }
|
