Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * initsplan.c
4 : * Target list, group by, qualification, joininfo initialization routines
5 : *
6 : * Portions Copyright (c) 1996-2026, 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 "access/nbtree.h"
18 : #include "access/sysattr.h"
19 : #include "catalog/pg_constraint.h"
20 : #include "catalog/pg_type.h"
21 : #include "nodes/makefuncs.h"
22 : #include "nodes/nodeFuncs.h"
23 : #include "optimizer/clauses.h"
24 : #include "optimizer/cost.h"
25 : #include "optimizer/inherit.h"
26 : #include "optimizer/joininfo.h"
27 : #include "optimizer/optimizer.h"
28 : #include "optimizer/pathnode.h"
29 : #include "optimizer/paths.h"
30 : #include "optimizer/placeholder.h"
31 : #include "optimizer/planmain.h"
32 : #include "optimizer/planner.h"
33 : #include "optimizer/restrictinfo.h"
34 : #include "parser/analyze.h"
35 : #include "rewrite/rewriteManip.h"
36 : #include "utils/lsyscache.h"
37 : #include "utils/rel.h"
38 : #include "utils/typcache.h"
39 :
40 : /* These parameters are set by GUC */
41 : int from_collapse_limit;
42 : int join_collapse_limit;
43 :
44 :
45 : /*
46 : * deconstruct_jointree requires multiple passes over the join tree, because we
47 : * need to finish computing JoinDomains before we start distributing quals.
48 : * As long as we have to do that, other information such as the relevant
49 : * qualscopes might as well be computed in the first pass too.
50 : *
51 : * deconstruct_recurse recursively examines the join tree and builds a List
52 : * (in depth-first traversal order) of JoinTreeItem structs, which are then
53 : * processed iteratively by deconstruct_distribute. If there are outer
54 : * joins, non-degenerate outer join clauses are processed in a third pass
55 : * deconstruct_distribute_oj_quals.
56 : *
57 : * The JoinTreeItem structs themselves can be freed at the end of
58 : * deconstruct_jointree, but do not modify or free their substructure,
59 : * as the relid sets may also be pointed to by RestrictInfo and
60 : * SpecialJoinInfo nodes.
61 : */
62 : typedef struct JoinTreeItem
63 : {
64 : /* Fields filled during deconstruct_recurse: */
65 : Node *jtnode; /* jointree node to examine */
66 : JoinDomain *jdomain; /* join domain for its ON/WHERE clauses */
67 : struct JoinTreeItem *jti_parent; /* JoinTreeItem for this node's
68 : * parent, or NULL if it's the top */
69 : Relids qualscope; /* base+OJ Relids syntactically included in
70 : * this jointree node */
71 : Relids inner_join_rels; /* base+OJ Relids syntactically included
72 : * in inner joins appearing at or below
73 : * this jointree node */
74 : Relids left_rels; /* if join node, Relids of the left side */
75 : Relids right_rels; /* if join node, Relids of the right side */
76 : Relids nonnullable_rels; /* if outer join, Relids of the
77 : * non-nullable side */
78 : /* Fields filled during deconstruct_distribute: */
79 : SpecialJoinInfo *sjinfo; /* if outer join, its SpecialJoinInfo */
80 : List *oj_joinclauses; /* outer join quals not yet distributed */
81 : List *lateral_clauses; /* quals postponed from children due to
82 : * lateral references */
83 : } JoinTreeItem;
84 :
85 :
86 : static bool is_partial_agg_memory_risky(PlannerInfo *root);
87 : static void create_agg_clause_infos(PlannerInfo *root);
88 : static void create_grouping_expr_infos(PlannerInfo *root);
89 : static EquivalenceClass *get_eclass_for_sortgroupclause(PlannerInfo *root,
90 : SortGroupClause *sgc,
91 : Expr *expr);
92 : static void extract_lateral_references(PlannerInfo *root, RelOptInfo *brel,
93 : Index rtindex);
94 : static List *deconstruct_recurse(PlannerInfo *root, Node *jtnode,
95 : JoinDomain *parent_domain,
96 : JoinTreeItem *parent_jtitem,
97 : List **item_list);
98 : static void deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem);
99 : static void process_security_barrier_quals(PlannerInfo *root,
100 : int rti, JoinTreeItem *jtitem);
101 : static void mark_rels_nulled_by_join(PlannerInfo *root, Index ojrelid,
102 : Relids lower_rels);
103 : static SpecialJoinInfo *make_outerjoininfo(PlannerInfo *root,
104 : Relids left_rels, Relids right_rels,
105 : Relids inner_join_rels,
106 : JoinType jointype, Index ojrelid,
107 : List *clause);
108 : static void compute_semijoin_info(PlannerInfo *root, SpecialJoinInfo *sjinfo,
109 : List *clause);
110 : static void deconstruct_distribute_oj_quals(PlannerInfo *root,
111 : List *jtitems,
112 : JoinTreeItem *jtitem);
113 : static void distribute_quals_to_rels(PlannerInfo *root, List *clauses,
114 : JoinTreeItem *jtitem,
115 : SpecialJoinInfo *sjinfo,
116 : Index security_level,
117 : Relids qualscope,
118 : Relids ojscope,
119 : Relids outerjoin_nonnullable,
120 : Relids incompatible_relids,
121 : bool allow_equivalence,
122 : bool has_clone,
123 : bool is_clone,
124 : List **postponed_oj_qual_list);
125 : static void distribute_qual_to_rels(PlannerInfo *root, Node *clause,
126 : JoinTreeItem *jtitem,
127 : SpecialJoinInfo *sjinfo,
128 : Index security_level,
129 : Relids qualscope,
130 : Relids ojscope,
131 : Relids outerjoin_nonnullable,
132 : Relids incompatible_relids,
133 : bool allow_equivalence,
134 : bool has_clone,
135 : bool is_clone,
136 : List **postponed_oj_qual_list);
137 : static bool check_redundant_nullability_qual(PlannerInfo *root, Node *clause);
138 : static Relids get_join_domain_min_rels(PlannerInfo *root, Relids domain_relids);
139 : static void check_mergejoinable(RestrictInfo *restrictinfo);
140 : static void check_hashjoinable(RestrictInfo *restrictinfo);
141 : static void check_memoizable(RestrictInfo *restrictinfo);
142 :
143 :
144 : /*****************************************************************************
145 : *
146 : * JOIN TREES
147 : *
148 : *****************************************************************************/
149 :
150 : /*
151 : * add_base_rels_to_query
152 : *
153 : * Scan the query's jointree and create baserel RelOptInfos for all
154 : * the base relations (e.g., table, subquery, and function RTEs)
155 : * appearing in the jointree.
156 : *
157 : * The initial invocation must pass root->parse->jointree as the value of
158 : * jtnode. Internally, the function recurses through the jointree.
159 : *
160 : * At the end of this process, there should be one baserel RelOptInfo for
161 : * every non-join RTE that is used in the query. Some of the baserels
162 : * may be appendrel parents, which will require additional "otherrel"
163 : * RelOptInfos for their member rels, but those are added later.
164 : */
165 : void
166 722119 : add_base_rels_to_query(PlannerInfo *root, Node *jtnode)
167 : {
168 722119 : if (jtnode == NULL)
169 0 : return;
170 722119 : if (IsA(jtnode, RangeTblRef))
171 : {
172 373757 : int varno = ((RangeTblRef *) jtnode)->rtindex;
173 :
174 373757 : (void) build_simple_rel(root, varno, NULL);
175 : }
176 348362 : else if (IsA(jtnode, FromExpr))
177 : {
178 265995 : FromExpr *f = (FromExpr *) jtnode;
179 : ListCell *l;
180 :
181 570056 : foreach(l, f->fromlist)
182 304072 : add_base_rels_to_query(root, lfirst(l));
183 : }
184 82367 : else if (IsA(jtnode, JoinExpr))
185 : {
186 82367 : JoinExpr *j = (JoinExpr *) jtnode;
187 :
188 82367 : add_base_rels_to_query(root, j->larg);
189 82367 : add_base_rels_to_query(root, j->rarg);
190 : }
191 : else
192 0 : elog(ERROR, "unrecognized node type: %d",
193 : (int) nodeTag(jtnode));
194 : }
195 :
196 : /*
197 : * add_other_rels_to_query
198 : * create "otherrel" RelOptInfos for the children of appendrel baserels
199 : *
200 : * At the end of this process, there should be RelOptInfos for all relations
201 : * that will be scanned by the query.
202 : */
203 : void
204 253302 : add_other_rels_to_query(PlannerInfo *root)
205 : {
206 : int rti;
207 :
208 794301 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
209 : {
210 541000 : RelOptInfo *rel = root->simple_rel_array[rti];
211 541000 : RangeTblEntry *rte = root->simple_rte_array[rti];
212 :
213 : /* there may be empty slots corresponding to non-baserel RTEs */
214 541000 : if (rel == NULL)
215 127695 : continue;
216 :
217 : /* Ignore any "otherrels" that were already added. */
218 413305 : if (rel->reloptkind != RELOPT_BASEREL)
219 48602 : continue;
220 :
221 : /* If it's marked as inheritable, look for children. */
222 364703 : if (rte->inh)
223 17678 : expand_inherited_rtentry(root, rel, rte, rti);
224 : }
225 253301 : }
226 :
227 :
228 : /*****************************************************************************
229 : *
230 : * TARGET LISTS
231 : *
232 : *****************************************************************************/
233 :
234 : /*
235 : * build_base_rel_tlists
236 : * Add targetlist entries for each var needed in the query's final tlist
237 : * (and HAVING clause, if any) to the appropriate base relations.
238 : *
239 : * We mark such vars as needed by "relation 0" to ensure that they will
240 : * propagate up through all join plan steps.
241 : */
242 : void
243 253330 : build_base_rel_tlists(PlannerInfo *root, List *final_tlist)
244 : {
245 253330 : List *tlist_vars = pull_var_clause((Node *) final_tlist,
246 : PVC_RECURSE_AGGREGATES |
247 : PVC_RECURSE_WINDOWFUNCS |
248 : PVC_INCLUDE_PLACEHOLDERS);
249 :
250 253330 : if (tlist_vars != NIL)
251 : {
252 236985 : add_vars_to_targetlist(root, tlist_vars, bms_make_singleton(0));
253 236985 : list_free(tlist_vars);
254 : }
255 :
256 : /*
257 : * If there's a HAVING clause, we'll need the Vars it uses, too. Note
258 : * that HAVING can contain Aggrefs but not WindowFuncs.
259 : */
260 253330 : if (root->parse->havingQual)
261 : {
262 731 : List *having_vars = pull_var_clause(root->parse->havingQual,
263 : PVC_RECURSE_AGGREGATES |
264 : PVC_INCLUDE_PLACEHOLDERS);
265 :
266 731 : if (having_vars != NIL)
267 : {
268 631 : add_vars_to_targetlist(root, having_vars,
269 : bms_make_singleton(0));
270 631 : list_free(having_vars);
271 : }
272 : }
273 253330 : }
274 :
275 : /*
276 : * add_vars_to_targetlist
277 : * For each variable appearing in the list, add it to the owning
278 : * relation's targetlist if not already present, and mark the variable
279 : * as being needed for the indicated join (or for final output if
280 : * where_needed includes "relation 0").
281 : *
282 : * The list may also contain PlaceHolderVars. These don't necessarily
283 : * have a single owning relation; we keep their attr_needed info in
284 : * root->placeholder_list instead. Find or create the associated
285 : * PlaceHolderInfo entry, and update its ph_needed.
286 : *
287 : * See also add_vars_to_attr_needed.
288 : */
289 : void
290 511875 : add_vars_to_targetlist(PlannerInfo *root, List *vars,
291 : Relids where_needed)
292 : {
293 : ListCell *temp;
294 :
295 : Assert(!bms_is_empty(where_needed));
296 :
297 1794217 : foreach(temp, vars)
298 : {
299 1282342 : Node *node = (Node *) lfirst(temp);
300 :
301 1282342 : if (IsA(node, Var))
302 : {
303 1279568 : Var *var = (Var *) node;
304 1279568 : RelOptInfo *rel = find_base_rel(root, var->varno);
305 1279568 : int attno = var->varattno;
306 :
307 1279568 : if (bms_is_subset(where_needed, rel->relids))
308 1282 : continue;
309 : Assert(attno >= rel->min_attr && attno <= rel->max_attr);
310 1278286 : attno -= rel->min_attr;
311 1278286 : if (rel->attr_needed[attno] == NULL)
312 : {
313 : /*
314 : * Variable not yet requested, so add to rel's targetlist.
315 : *
316 : * The value available at the rel's scan level has not been
317 : * nulled by any outer join, so drop its varnullingrels.
318 : * (We'll put those back as we climb up the join tree.)
319 : */
320 940256 : var = copyObject(var);
321 940256 : var->varnullingrels = NULL;
322 940256 : rel->reltarget->exprs = lappend(rel->reltarget->exprs, var);
323 : /* reltarget cost and width will be computed later */
324 : }
325 1278286 : rel->attr_needed[attno] = bms_add_members(rel->attr_needed[attno],
326 : where_needed);
327 : }
328 2774 : else if (IsA(node, PlaceHolderVar))
329 : {
330 2774 : PlaceHolderVar *phv = (PlaceHolderVar *) node;
331 2774 : PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
332 :
333 2774 : phinfo->ph_needed = bms_add_members(phinfo->ph_needed,
334 : where_needed);
335 : }
336 : else
337 0 : elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
338 : }
339 511875 : }
340 :
341 : /*
342 : * add_vars_to_attr_needed
343 : * This does a subset of what add_vars_to_targetlist does: it just
344 : * updates attr_needed for Vars and ph_needed for PlaceHolderVars.
345 : * We assume the Vars are already in their relations' targetlists.
346 : *
347 : * This is used to rebuild attr_needed/ph_needed sets after removal
348 : * of a useless outer join. The removed join clause might have been
349 : * the only upper-level use of some other relation's Var, in which
350 : * case we can reduce that Var's attr_needed and thereby possibly
351 : * open the door to further join removals. But we can't tell that
352 : * without tedious reconstruction of the attr_needed data.
353 : *
354 : * Note that if a Var's attr_needed is successfully reduced to empty,
355 : * it will still be in the relation's targetlist even though we do
356 : * not really need the scan plan node to emit it. The extra plan
357 : * inefficiency seems tiny enough to not be worth spending planner
358 : * cycles to get rid of it.
359 : */
360 : void
361 13042 : add_vars_to_attr_needed(PlannerInfo *root, List *vars,
362 : Relids where_needed)
363 : {
364 : ListCell *temp;
365 :
366 : Assert(!bms_is_empty(where_needed));
367 :
368 29957 : foreach(temp, vars)
369 : {
370 16915 : Node *node = (Node *) lfirst(temp);
371 :
372 16915 : if (IsA(node, Var))
373 : {
374 16853 : Var *var = (Var *) node;
375 16853 : RelOptInfo *rel = find_base_rel(root, var->varno);
376 16853 : int attno = var->varattno;
377 :
378 16853 : if (bms_is_subset(where_needed, rel->relids))
379 744 : continue;
380 : Assert(attno >= rel->min_attr && attno <= rel->max_attr);
381 16109 : attno -= rel->min_attr;
382 16109 : rel->attr_needed[attno] = bms_add_members(rel->attr_needed[attno],
383 : where_needed);
384 : }
385 62 : else if (IsA(node, PlaceHolderVar))
386 : {
387 62 : PlaceHolderVar *phv = (PlaceHolderVar *) node;
388 62 : PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
389 :
390 62 : phinfo->ph_needed = bms_add_members(phinfo->ph_needed,
391 : where_needed);
392 : }
393 : else
394 0 : elog(ERROR, "unrecognized node type: %d", (int) nodeTag(node));
395 : }
396 13042 : }
397 :
398 : /*****************************************************************************
399 : *
400 : * GROUP BY
401 : *
402 : *****************************************************************************/
403 :
404 : /*
405 : * remove_useless_groupby_columns
406 : * Remove any columns in the GROUP BY clause that are redundant due to
407 : * being functionally dependent on other GROUP BY columns.
408 : *
409 : * Since some other DBMSes do not allow references to ungrouped columns, it's
410 : * not unusual to find all columns listed in GROUP BY even though listing the
411 : * primary-key columns, or columns of a unique constraint would be sufficient.
412 : * Deleting such excess columns avoids redundant sorting or hashing work, so
413 : * it's worth doing.
414 : *
415 : * Relcache invalidations will ensure that cached plans become invalidated
416 : * when the underlying supporting indexes are dropped or if a column's NOT
417 : * NULL attribute is removed.
418 : */
419 : void
420 253302 : remove_useless_groupby_columns(PlannerInfo *root)
421 : {
422 253302 : Query *parse = root->parse;
423 : Bitmapset **groupbyattnos;
424 : Bitmapset **surplusvars;
425 253302 : bool tryremove = false;
426 : ListCell *lc;
427 : int relid;
428 :
429 : /* No chance to do anything if there are less than two GROUP BY items */
430 253302 : if (list_length(root->processed_groupClause) < 2)
431 251487 : return;
432 :
433 : /* Don't fiddle with the GROUP BY clause if the query has grouping sets */
434 1815 : if (parse->groupingSets)
435 623 : return;
436 :
437 : /*
438 : * Scan the GROUP BY clause to find GROUP BY items that are simple Vars.
439 : * Fill groupbyattnos[k] with a bitmapset of the column attnos of RTE k
440 : * that are GROUP BY items.
441 : */
442 1192 : groupbyattnos = palloc0_array(Bitmapset *, list_length(parse->rtable) + 1);
443 4323 : foreach(lc, root->processed_groupClause)
444 : {
445 3131 : SortGroupClause *sgc = lfirst_node(SortGroupClause, lc);
446 3131 : TargetEntry *tle = get_sortgroupclause_tle(sgc, parse->targetList);
447 3131 : Var *var = (Var *) tle->expr;
448 :
449 : /*
450 : * Ignore non-Vars and Vars from other query levels.
451 : *
452 : * XXX in principle, stable expressions containing Vars could also be
453 : * removed, if all the Vars are functionally dependent on other GROUP
454 : * BY items. But it's not clear that such cases occur often enough to
455 : * be worth troubling over.
456 : */
457 3131 : if (!IsA(var, Var) ||
458 2468 : var->varlevelsup > 0)
459 663 : continue;
460 :
461 : /* OK, remember we have this Var */
462 2468 : relid = var->varno;
463 : Assert(relid <= list_length(parse->rtable));
464 :
465 : /*
466 : * If this isn't the first column for this relation then we now have
467 : * multiple columns. That means there might be some that can be
468 : * removed.
469 : */
470 2468 : tryremove |= !bms_is_empty(groupbyattnos[relid]);
471 2468 : groupbyattnos[relid] = bms_add_member(groupbyattnos[relid],
472 2468 : var->varattno - FirstLowInvalidHeapAttributeNumber);
473 : }
474 :
475 : /*
476 : * No Vars or didn't find multiple Vars for any relation in the GROUP BY?
477 : * If so, nothing can be removed, so don't waste more effort trying.
478 : */
479 1192 : if (!tryremove)
480 366 : return;
481 :
482 : /*
483 : * Consider each relation and see if it is possible to remove some of its
484 : * Vars from GROUP BY. For simplicity and speed, we do the actual removal
485 : * in a separate pass. Here, we just fill surplusvars[k] with a bitmapset
486 : * of the column attnos of RTE k that are removable GROUP BY items.
487 : */
488 826 : surplusvars = NULL; /* don't allocate array unless required */
489 826 : relid = 0;
490 3505 : foreach(lc, parse->rtable)
491 : {
492 2679 : RangeTblEntry *rte = lfirst_node(RangeTblEntry, lc);
493 : RelOptInfo *rel;
494 : Bitmapset *relattnos;
495 2679 : Bitmapset *best_keycolumns = NULL;
496 2679 : int32 best_nkeycolumns = PG_INT32_MAX;
497 :
498 2679 : relid++;
499 :
500 : /* Only plain relations could have primary-key constraints */
501 2679 : if (rte->rtekind != RTE_RELATION)
502 1362 : continue;
503 :
504 : /*
505 : * We must skip inheritance parent tables as some of the child rels
506 : * may cause duplicate rows. This cannot happen with partitioned
507 : * tables, however.
508 : */
509 1317 : if (rte->inh && rte->relkind != RELKIND_PARTITIONED_TABLE)
510 15 : continue;
511 :
512 : /* Nothing to do unless this rel has multiple Vars in GROUP BY */
513 1302 : relattnos = groupbyattnos[relid];
514 1302 : if (bms_membership(relattnos) != BMS_MULTIPLE)
515 504 : continue;
516 :
517 798 : rel = root->simple_rel_array[relid];
518 :
519 : /*
520 : * Now check each index for this relation to see if there are any with
521 : * columns which are a proper subset of the grouping columns for this
522 : * relation.
523 : */
524 2486 : foreach_node(IndexOptInfo, index, rel->indexlist)
525 : {
526 : Bitmapset *ind_attnos;
527 : bool nulls_check_ok;
528 :
529 : /*
530 : * Skip any non-unique and deferrable indexes. Predicate indexes
531 : * have not been checked yet, so we must skip those too as the
532 : * predOK check that's done later might fail.
533 : */
534 890 : if (!index->unique || !index->immediate || index->indpred != NIL)
535 348 : continue;
536 :
537 : /* For simplicity, we currently don't support expression indexes */
538 542 : if (index->indexprs != NIL)
539 0 : continue;
540 :
541 542 : ind_attnos = NULL;
542 542 : nulls_check_ok = true;
543 1367 : for (int i = 0; i < index->nkeycolumns; i++)
544 : {
545 : /*
546 : * We must insist that the index columns are all defined NOT
547 : * NULL otherwise duplicate NULLs could exist. However, we
548 : * can relax this check when the index is defined with NULLS
549 : * NOT DISTINCT as there can only be 1 NULL row, therefore
550 : * functional dependency on the unique columns is maintained,
551 : * despite the NULL.
552 : */
553 830 : if (!index->nullsnotdistinct &&
554 825 : !bms_is_member(index->indexkeys[i],
555 825 : rel->notnullattnums))
556 : {
557 5 : nulls_check_ok = false;
558 5 : break;
559 : }
560 :
561 : ind_attnos =
562 825 : bms_add_member(ind_attnos,
563 825 : index->indexkeys[i] -
564 : FirstLowInvalidHeapAttributeNumber);
565 : }
566 :
567 542 : if (!nulls_check_ok)
568 5 : continue;
569 :
570 : /*
571 : * Skip any indexes where the indexed columns aren't a proper
572 : * subset of the GROUP BY.
573 : */
574 537 : if (bms_subset_compare(ind_attnos, relattnos) != BMS_SUBSET1)
575 248 : continue;
576 :
577 : /*
578 : * Record the attribute numbers from the index with the fewest
579 : * columns. This allows the largest number of columns to be
580 : * removed from the GROUP BY clause. In the future, we may wish
581 : * to consider using the narrowest set of columns and looking at
582 : * pg_statistic.stawidth as it might be better to use an index
583 : * with, say two INT4s, rather than, say, one long varlena column.
584 : */
585 289 : if (index->nkeycolumns < best_nkeycolumns)
586 : {
587 274 : best_keycolumns = ind_attnos;
588 274 : best_nkeycolumns = index->nkeycolumns;
589 : }
590 : }
591 :
592 : /* Did we find a suitable index? */
593 798 : if (!bms_is_empty(best_keycolumns))
594 : {
595 : /*
596 : * To easily remember whether we've found anything to do, we don't
597 : * allocate the surplusvars[] array until we find something.
598 : */
599 274 : if (surplusvars == NULL)
600 269 : surplusvars = palloc0_array(Bitmapset *, list_length(parse->rtable) + 1);
601 :
602 : /* Remember the attnos of the removable columns */
603 274 : surplusvars[relid] = bms_difference(relattnos, best_keycolumns);
604 : }
605 : }
606 :
607 : /*
608 : * If we found any surplus Vars, build a new GROUP BY clause without them.
609 : * (Note: this may leave some TLEs with unreferenced ressortgroupref
610 : * markings, but that's harmless.)
611 : */
612 826 : if (surplusvars != NULL)
613 : {
614 269 : List *new_groupby = NIL;
615 :
616 1105 : foreach(lc, root->processed_groupClause)
617 : {
618 836 : SortGroupClause *sgc = lfirst_node(SortGroupClause, lc);
619 836 : TargetEntry *tle = get_sortgroupclause_tle(sgc, parse->targetList);
620 836 : Var *var = (Var *) tle->expr;
621 :
622 : /*
623 : * New list must include non-Vars, outer Vars, and anything not
624 : * marked as surplus.
625 : */
626 836 : if (!IsA(var, Var) ||
627 836 : var->varlevelsup > 0 ||
628 836 : !bms_is_member(var->varattno - FirstLowInvalidHeapAttributeNumber,
629 836 : surplusvars[var->varno]))
630 527 : new_groupby = lappend(new_groupby, sgc);
631 : }
632 :
633 269 : root->processed_groupClause = new_groupby;
634 : }
635 : }
636 :
637 : /*
638 : * setup_eager_aggregation
639 : * Check if eager aggregation is applicable, and if so collect suitable
640 : * aggregate expressions and grouping expressions in the query.
641 : */
642 : void
643 253302 : setup_eager_aggregation(PlannerInfo *root)
644 : {
645 : /*
646 : * Don't apply eager aggregation if disabled by user.
647 : */
648 253302 : if (!enable_eager_aggregate)
649 400 : return;
650 :
651 : /*
652 : * Don't apply eager aggregation if there are no available GROUP BY
653 : * clauses.
654 : */
655 252902 : if (!root->processed_groupClause)
656 249349 : return;
657 :
658 : /*
659 : * For now we don't try to support grouping sets.
660 : */
661 3553 : if (root->parse->groupingSets)
662 707 : return;
663 :
664 : /*
665 : * For now we don't try to support DISTINCT or ORDER BY aggregates.
666 : */
667 2846 : if (root->numOrderedAggs > 0)
668 146 : return;
669 :
670 : /*
671 : * If there are any aggregates that do not support partial mode, or any
672 : * partial aggregates that are non-serializable, do not apply eager
673 : * aggregation.
674 : */
675 2700 : if (root->hasNonPartialAggs || root->hasNonSerialAggs)
676 125 : return;
677 :
678 : /*
679 : * We don't try to apply eager aggregation if there are set-returning
680 : * functions in targetlist.
681 : */
682 2575 : if (root->parse->hasTargetSRFs)
683 70 : return;
684 :
685 : /*
686 : * Eager aggregation only makes sense if there are multiple base rels in
687 : * the query.
688 : */
689 2505 : if (bms_membership(root->all_baserels) != BMS_MULTIPLE)
690 1662 : return;
691 :
692 : /*
693 : * Don't apply eager aggregation if any aggregate poses a risk of
694 : * excessive memory usage during partial aggregation.
695 : */
696 843 : if (is_partial_agg_memory_risky(root))
697 1 : return;
698 :
699 : /*
700 : * Collect aggregate expressions and plain Vars that appear in the
701 : * targetlist and havingQual.
702 : */
703 842 : create_agg_clause_infos(root);
704 :
705 : /*
706 : * If there are no suitable aggregate expressions, we cannot apply eager
707 : * aggregation.
708 : */
709 842 : if (root->agg_clause_list == NIL)
710 291 : return;
711 :
712 : /*
713 : * Collect grouping expressions that appear in grouping clauses.
714 : */
715 551 : create_grouping_expr_infos(root);
716 : }
717 :
718 : /*
719 : * is_partial_agg_memory_risky
720 : * Check if any aggregate poses a risk of excessive memory usage during
721 : * partial aggregation.
722 : *
723 : * We check if any aggregate has a negative aggtransspace value, which
724 : * indicates that its transition state data can grow unboundedly in size.
725 : * Applying eager aggregation in such cases risks high memory usage since
726 : * partial aggregation results might be stored in join hash tables or
727 : * materialized nodes.
728 : */
729 : static bool
730 843 : is_partial_agg_memory_risky(PlannerInfo *root)
731 : {
732 : ListCell *lc;
733 :
734 1615 : foreach(lc, root->aggtransinfos)
735 : {
736 773 : AggTransInfo *transinfo = lfirst_node(AggTransInfo, lc);
737 :
738 773 : if (transinfo->aggtransspace < 0)
739 1 : return true;
740 : }
741 :
742 842 : return false;
743 : }
744 :
745 : /*
746 : * create_agg_clause_infos
747 : * Search the targetlist and havingQual for Aggrefs and plain Vars, and
748 : * create an AggClauseInfo for each Aggref node.
749 : */
750 : static void
751 842 : create_agg_clause_infos(PlannerInfo *root)
752 : {
753 : List *tlist_exprs;
754 842 : List *agg_clause_list = NIL;
755 842 : List *tlist_vars = NIL;
756 842 : Relids aggregate_relids = NULL;
757 842 : bool eager_agg_applicable = true;
758 : ListCell *lc;
759 :
760 : Assert(root->agg_clause_list == NIL);
761 : Assert(root->tlist_vars == NIL);
762 :
763 842 : tlist_exprs = pull_var_clause((Node *) root->processed_tlist,
764 : PVC_INCLUDE_AGGREGATES |
765 : PVC_RECURSE_WINDOWFUNCS |
766 : PVC_RECURSE_PLACEHOLDERS);
767 :
768 : /*
769 : * Aggregates within the HAVING clause need to be processed in the same
770 : * way as those in the targetlist. Note that HAVING can contain Aggrefs
771 : * but not WindowFuncs.
772 : */
773 842 : if (root->parse->havingQual != NULL)
774 : {
775 : List *having_exprs;
776 :
777 35 : having_exprs = pull_var_clause((Node *) root->parse->havingQual,
778 : PVC_INCLUDE_AGGREGATES |
779 : PVC_RECURSE_PLACEHOLDERS);
780 35 : if (having_exprs != NIL)
781 : {
782 35 : tlist_exprs = list_concat(tlist_exprs, having_exprs);
783 35 : list_free(having_exprs);
784 : }
785 : }
786 :
787 3726 : foreach(lc, tlist_exprs)
788 : {
789 2932 : Expr *expr = (Expr *) lfirst(lc);
790 : Aggref *aggref;
791 : Relids agg_eval_at;
792 : AggClauseInfo *ac_info;
793 :
794 : /* For now we don't try to support GROUPING() expressions */
795 2932 : if (IsA(expr, GroupingFunc))
796 : {
797 0 : eager_agg_applicable = false;
798 0 : break;
799 : }
800 :
801 : /* Collect plain Vars for future reference */
802 2932 : if (IsA(expr, Var))
803 : {
804 2155 : tlist_vars = list_append_unique(tlist_vars, expr);
805 2155 : continue;
806 : }
807 :
808 777 : aggref = castNode(Aggref, expr);
809 :
810 : Assert(aggref->aggorder == NIL);
811 : Assert(aggref->aggdistinct == NIL);
812 :
813 : /*
814 : * We cannot push down aggregates that contain volatile functions.
815 : * Doing so would change the number of times the function is
816 : * evaluated.
817 : */
818 777 : if (contain_volatile_functions((Node *) aggref))
819 : {
820 10 : eager_agg_applicable = false;
821 10 : break;
822 : }
823 :
824 : /*
825 : * If there are any securityQuals, do not try to apply eager
826 : * aggregation if any non-leakproof aggregate functions are present.
827 : * This is overly strict, but for now...
828 : */
829 767 : if (root->qual_security_level > 0 &&
830 0 : !get_func_leakproof(aggref->aggfnoid))
831 : {
832 0 : eager_agg_applicable = false;
833 0 : break;
834 : }
835 :
836 767 : agg_eval_at = pull_varnos(root, (Node *) aggref);
837 :
838 : /*
839 : * If all base relations in the query are referenced by aggregate
840 : * functions, then eager aggregation is not applicable.
841 : */
842 767 : aggregate_relids = bms_add_members(aggregate_relids, agg_eval_at);
843 767 : if (bms_is_subset(root->all_baserels, aggregate_relids))
844 : {
845 38 : eager_agg_applicable = false;
846 38 : break;
847 : }
848 :
849 : /* OK, create the AggClauseInfo node */
850 729 : ac_info = makeNode(AggClauseInfo);
851 729 : ac_info->aggref = aggref;
852 729 : ac_info->agg_eval_at = agg_eval_at;
853 :
854 : /* ... and add it to the list */
855 729 : agg_clause_list = list_append_unique(agg_clause_list, ac_info);
856 : }
857 :
858 842 : list_free(tlist_exprs);
859 :
860 842 : if (eager_agg_applicable)
861 : {
862 794 : root->agg_clause_list = agg_clause_list;
863 794 : root->tlist_vars = tlist_vars;
864 : }
865 : else
866 : {
867 48 : list_free_deep(agg_clause_list);
868 48 : list_free(tlist_vars);
869 : }
870 842 : }
871 :
872 : /*
873 : * create_grouping_expr_infos
874 : * Create a GroupingExprInfo for each expression usable as grouping key.
875 : *
876 : * If any grouping expression is not suitable, we will just return with
877 : * root->group_expr_list being NIL.
878 : */
879 : static void
880 551 : create_grouping_expr_infos(PlannerInfo *root)
881 : {
882 551 : List *exprs = NIL;
883 551 : List *sortgrouprefs = NIL;
884 551 : List *ecs = NIL;
885 : ListCell *lc,
886 : *lc1,
887 : *lc2,
888 : *lc3;
889 :
890 : Assert(root->group_expr_list == NIL);
891 :
892 1047 : foreach(lc, root->processed_groupClause)
893 : {
894 607 : SortGroupClause *sgc = lfirst_node(SortGroupClause, lc);
895 607 : TargetEntry *tle = get_sortgroupclause_tle(sgc, root->processed_tlist);
896 : TypeCacheEntry *tce;
897 : Oid equalimageproc;
898 :
899 : Assert(tle->ressortgroupref > 0);
900 :
901 : /*
902 : * For now we only support plain Vars as grouping expressions.
903 : */
904 607 : if (!IsA(tle->expr, Var))
905 111 : return;
906 :
907 : /*
908 : * Eager aggregation is only possible if equality implies image
909 : * equality for each grouping key. Otherwise, placing keys with
910 : * different byte images into the same group may result in the loss of
911 : * information that could be necessary to evaluate upper qual clauses.
912 : *
913 : * For instance, the NUMERIC data type is not supported, as values
914 : * that are considered equal by the equality operator (e.g., 0 and
915 : * 0.0) can have different scales.
916 : */
917 561 : tce = lookup_type_cache(exprType((Node *) tle->expr),
918 : TYPECACHE_BTREE_OPFAMILY);
919 561 : if (!OidIsValid(tce->btree_opf) ||
920 561 : !OidIsValid(tce->btree_opintype))
921 0 : return;
922 :
923 561 : equalimageproc = get_opfamily_proc(tce->btree_opf,
924 : tce->btree_opintype,
925 : tce->btree_opintype,
926 : BTEQUALIMAGE_PROC);
927 :
928 : /*
929 : * If there is no BTEQUALIMAGE_PROC, eager aggregation is assumed to
930 : * be unsafe. Otherwise, we call the procedure to check. We must be
931 : * careful to pass the expression's actual collation, rather than the
932 : * data type's default collation, to ensure that non-deterministic
933 : * collations are correctly handled.
934 : */
935 561 : if (!OidIsValid(equalimageproc) ||
936 1112 : !DatumGetBool(OidFunctionCall1Coll(equalimageproc,
937 556 : exprCollation((Node *) tle->expr),
938 : ObjectIdGetDatum(tce->btree_opintype))))
939 65 : return;
940 :
941 496 : exprs = lappend(exprs, tle->expr);
942 496 : sortgrouprefs = lappend_int(sortgrouprefs, tle->ressortgroupref);
943 496 : ecs = lappend(ecs, get_eclass_for_sortgroupclause(root, sgc, tle->expr));
944 : }
945 :
946 : /*
947 : * Construct a GroupingExprInfo for each expression.
948 : */
949 916 : forthree(lc1, exprs, lc2, sortgrouprefs, lc3, ecs)
950 : {
951 476 : Expr *expr = (Expr *) lfirst(lc1);
952 476 : int sortgroupref = lfirst_int(lc2);
953 476 : EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc3);
954 : GroupingExprInfo *ge_info;
955 :
956 476 : ge_info = makeNode(GroupingExprInfo);
957 476 : ge_info->expr = (Expr *) copyObject(expr);
958 476 : ge_info->sortgroupref = sortgroupref;
959 476 : ge_info->ec = ec;
960 :
961 476 : root->group_expr_list = lappend(root->group_expr_list, ge_info);
962 : }
963 : }
964 :
965 : /*
966 : * get_eclass_for_sortgroupclause
967 : * Given a group clause and an expression, find an existing equivalence
968 : * class that the expression is a member of; return NULL if none.
969 : */
970 : static EquivalenceClass *
971 496 : get_eclass_for_sortgroupclause(PlannerInfo *root, SortGroupClause *sgc,
972 : Expr *expr)
973 : {
974 : Oid opfamily,
975 : opcintype,
976 : collation;
977 : CompareType cmptype;
978 : Oid equality_op;
979 : List *opfamilies;
980 :
981 : /* Punt if the group clause is not sortable */
982 496 : if (!OidIsValid(sgc->sortop))
983 0 : return NULL;
984 :
985 : /* Find the operator in pg_amop --- failure shouldn't happen */
986 496 : if (!get_ordering_op_properties(sgc->sortop,
987 : &opfamily, &opcintype, &cmptype))
988 0 : elog(ERROR, "operator %u is not a valid ordering operator",
989 : sgc->sortop);
990 :
991 : /* Because SortGroupClause doesn't carry collation, consult the expr */
992 496 : collation = exprCollation((Node *) expr);
993 :
994 : /*
995 : * EquivalenceClasses need to contain opfamily lists based on the family
996 : * membership of mergejoinable equality operators, which could belong to
997 : * more than one opfamily. So we have to look up the opfamily's equality
998 : * operator and get its membership.
999 : */
1000 496 : equality_op = get_opfamily_member_for_cmptype(opfamily,
1001 : opcintype,
1002 : opcintype,
1003 : COMPARE_EQ);
1004 496 : if (!OidIsValid(equality_op)) /* shouldn't happen */
1005 0 : elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
1006 : COMPARE_EQ, opcintype, opcintype, opfamily);
1007 496 : opfamilies = get_mergejoin_opfamilies(equality_op);
1008 496 : if (!opfamilies) /* certainly should find some */
1009 0 : elog(ERROR, "could not find opfamilies for equality operator %u",
1010 : equality_op);
1011 :
1012 : /* Now find a matching EquivalenceClass */
1013 496 : return get_eclass_for_sort_expr(root, expr, opfamilies, opcintype,
1014 : collation, sgc->tleSortGroupRef,
1015 : NULL, false);
1016 : }
1017 :
1018 : /*****************************************************************************
1019 : *
1020 : * LATERAL REFERENCES
1021 : *
1022 : *****************************************************************************/
1023 :
1024 : /*
1025 : * find_lateral_references
1026 : * For each LATERAL subquery, extract all its references to Vars and
1027 : * PlaceHolderVars of the current query level, and make sure those values
1028 : * will be available for evaluation of the subquery.
1029 : *
1030 : * While later planning steps ensure that the Var/PHV source rels are on the
1031 : * outside of nestloops relative to the LATERAL subquery, we also need to
1032 : * ensure that the Vars/PHVs propagate up to the nestloop join level; this
1033 : * means setting suitable where_needed values for them.
1034 : *
1035 : * Note that this only deals with lateral references in unflattened LATERAL
1036 : * subqueries. When we flatten a LATERAL subquery, its lateral references
1037 : * become plain Vars in the parent query, but they may have to be wrapped in
1038 : * PlaceHolderVars if they need to be forced NULL by outer joins that don't
1039 : * also null the LATERAL subquery. That's all handled elsewhere.
1040 : *
1041 : * This has to run before deconstruct_jointree, since it might result in
1042 : * creation of PlaceHolderInfos.
1043 : */
1044 : void
1045 253302 : find_lateral_references(PlannerInfo *root)
1046 : {
1047 : Index rti;
1048 :
1049 : /* We need do nothing if the query contains no LATERAL RTEs */
1050 253302 : if (!root->hasLateralRTEs)
1051 246207 : return;
1052 :
1053 : /*
1054 : * Examine all baserels (the rel array has been set up by now).
1055 : */
1056 33445 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
1057 : {
1058 26350 : RelOptInfo *brel = root->simple_rel_array[rti];
1059 :
1060 : /* there may be empty slots corresponding to non-baserel RTEs */
1061 26350 : if (brel == NULL)
1062 8633 : continue;
1063 :
1064 : Assert(brel->relid == rti); /* sanity check on array */
1065 :
1066 : /*
1067 : * This bit is less obvious than it might look. We ignore appendrel
1068 : * otherrels and consider only their parent baserels. In a case where
1069 : * a LATERAL-containing UNION ALL subquery was pulled up, it is the
1070 : * otherrel that is actually going to be in the plan. However, we
1071 : * want to mark all its lateral references as needed by the parent,
1072 : * because it is the parent's relid that will be used for join
1073 : * planning purposes. And the parent's RTE will contain all the
1074 : * lateral references we need to know, since the pulled-up member is
1075 : * nothing but a copy of parts of the original RTE's subquery. We
1076 : * could visit the parent's children instead and transform their
1077 : * references back to the parent's relid, but it would be much more
1078 : * complicated for no real gain. (Important here is that the child
1079 : * members have not yet received any processing beyond being pulled
1080 : * up.) Similarly, in appendrels created by inheritance expansion,
1081 : * it's sufficient to look at the parent relation.
1082 : */
1083 :
1084 : /* ignore RTEs that are "other rels" */
1085 17717 : if (brel->reloptkind != RELOPT_BASEREL)
1086 0 : continue;
1087 :
1088 17717 : extract_lateral_references(root, brel, rti);
1089 : }
1090 : }
1091 :
1092 : static void
1093 17717 : extract_lateral_references(PlannerInfo *root, RelOptInfo *brel, Index rtindex)
1094 : {
1095 17717 : RangeTblEntry *rte = root->simple_rte_array[rtindex];
1096 : List *vars;
1097 : List *newvars;
1098 : Relids where_needed;
1099 : ListCell *lc;
1100 :
1101 : /* No cross-references are possible if it's not LATERAL */
1102 17717 : if (!rte->lateral)
1103 11460 : return;
1104 :
1105 : /* Fetch the appropriate variables */
1106 6257 : if (rte->rtekind == RTE_RELATION)
1107 30 : vars = pull_vars_of_level((Node *) rte->tablesample, 0);
1108 6227 : else if (rte->rtekind == RTE_SUBQUERY)
1109 1263 : vars = pull_vars_of_level((Node *) rte->subquery, 1);
1110 4964 : else if (rte->rtekind == RTE_FUNCTION)
1111 4709 : vars = pull_vars_of_level((Node *) rte->functions, 0);
1112 255 : else if (rte->rtekind == RTE_TABLEFUNC)
1113 195 : vars = pull_vars_of_level((Node *) rte->tablefunc, 0);
1114 60 : else if (rte->rtekind == RTE_VALUES)
1115 60 : vars = pull_vars_of_level((Node *) rte->values_lists, 0);
1116 : else
1117 : {
1118 : Assert(false);
1119 0 : return; /* keep compiler quiet */
1120 : }
1121 :
1122 6257 : if (vars == NIL)
1123 248 : return; /* nothing to do */
1124 :
1125 : /* Copy each Var (or PlaceHolderVar) and adjust it to match our level */
1126 6009 : newvars = NIL;
1127 14602 : foreach(lc, vars)
1128 : {
1129 8593 : Node *node = (Node *) lfirst(lc);
1130 :
1131 8593 : node = copyObject(node);
1132 8593 : if (IsA(node, Var))
1133 : {
1134 8488 : Var *var = (Var *) node;
1135 :
1136 : /* Adjustment is easy since it's just one node */
1137 8488 : var->varlevelsup = 0;
1138 : }
1139 105 : else if (IsA(node, PlaceHolderVar))
1140 : {
1141 105 : PlaceHolderVar *phv = (PlaceHolderVar *) node;
1142 105 : int levelsup = phv->phlevelsup;
1143 :
1144 : /* Have to work harder to adjust the contained expression too */
1145 105 : if (levelsup != 0)
1146 75 : IncrementVarSublevelsUp(node, -levelsup, 0);
1147 :
1148 : /*
1149 : * If we pulled the PHV out of a subquery RTE, its expression
1150 : * needs to be preprocessed. subquery_planner() already did this
1151 : * for level-zero PHVs in function and values RTEs, though.
1152 : */
1153 105 : if (levelsup > 0)
1154 75 : phv->phexpr = preprocess_phv_expression(root, phv->phexpr);
1155 : }
1156 : else
1157 : Assert(false);
1158 8593 : newvars = lappend(newvars, node);
1159 : }
1160 :
1161 6009 : list_free(vars);
1162 :
1163 : /*
1164 : * We mark the Vars as being "needed" at the LATERAL RTE. This is a bit
1165 : * of a cheat: a more formal approach would be to mark each one as needed
1166 : * at the join of the LATERAL RTE with its source RTE. But it will work,
1167 : * and it's much less tedious than computing a separate where_needed for
1168 : * each Var.
1169 : */
1170 6009 : where_needed = bms_make_singleton(rtindex);
1171 :
1172 : /*
1173 : * Push Vars into their source relations' targetlists, and PHVs into
1174 : * root->placeholder_list.
1175 : */
1176 6009 : add_vars_to_targetlist(root, newvars, where_needed);
1177 :
1178 : /*
1179 : * Remember the lateral references for rebuild_lateral_attr_needed and
1180 : * create_lateral_join_info.
1181 : */
1182 6009 : brel->lateral_vars = newvars;
1183 : }
1184 :
1185 : /*
1186 : * rebuild_lateral_attr_needed
1187 : * Put back attr_needed bits for Vars/PHVs needed for lateral references.
1188 : *
1189 : * This is used to rebuild attr_needed/ph_needed sets after removal of a
1190 : * useless outer join. It should match what find_lateral_references did,
1191 : * except that we call add_vars_to_attr_needed not add_vars_to_targetlist.
1192 : */
1193 : void
1194 9043 : rebuild_lateral_attr_needed(PlannerInfo *root)
1195 : {
1196 : Index rti;
1197 :
1198 : /* We need do nothing if the query contains no LATERAL RTEs */
1199 9043 : if (!root->hasLateralRTEs)
1200 8130 : return;
1201 :
1202 : /* Examine the same baserels that find_lateral_references did */
1203 10272 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
1204 : {
1205 9359 : RelOptInfo *brel = root->simple_rel_array[rti];
1206 : Relids where_needed;
1207 :
1208 9359 : if (brel == NULL)
1209 5766 : continue;
1210 3593 : if (brel->reloptkind != RELOPT_BASEREL)
1211 0 : continue;
1212 :
1213 : /*
1214 : * We don't need to repeat all of extract_lateral_references, since it
1215 : * kindly saved the extracted Vars/PHVs in lateral_vars.
1216 : */
1217 3593 : if (brel->lateral_vars == NIL)
1218 2910 : continue;
1219 :
1220 683 : where_needed = bms_make_singleton(rti);
1221 :
1222 683 : add_vars_to_attr_needed(root, brel->lateral_vars, where_needed);
1223 : }
1224 : }
1225 :
1226 : /*
1227 : * create_lateral_join_info
1228 : * Fill in the per-base-relation direct_lateral_relids, lateral_relids
1229 : * and lateral_referencers sets.
1230 : */
1231 : void
1232 253302 : create_lateral_join_info(PlannerInfo *root)
1233 : {
1234 253302 : bool found_laterals = false;
1235 : Index rti;
1236 : ListCell *lc;
1237 :
1238 : /* We need do nothing if the query contains no LATERAL RTEs */
1239 253302 : if (!root->hasLateralRTEs)
1240 246207 : return;
1241 :
1242 : /* We'll need to have the ph_eval_at values for PlaceHolderVars */
1243 : Assert(root->placeholdersFrozen);
1244 :
1245 : /*
1246 : * Examine all baserels (the rel array has been set up by now).
1247 : */
1248 33445 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
1249 : {
1250 26350 : RelOptInfo *brel = root->simple_rel_array[rti];
1251 : Relids lateral_relids;
1252 :
1253 : /* there may be empty slots corresponding to non-baserel RTEs */
1254 26350 : if (brel == NULL)
1255 9546 : continue;
1256 :
1257 : Assert(brel->relid == rti); /* sanity check on array */
1258 :
1259 : /* ignore RTEs that are "other rels" */
1260 16804 : if (brel->reloptkind != RELOPT_BASEREL)
1261 0 : continue;
1262 :
1263 16804 : lateral_relids = NULL;
1264 :
1265 : /* consider each laterally-referenced Var or PHV */
1266 25244 : foreach(lc, brel->lateral_vars)
1267 : {
1268 8440 : Node *node = (Node *) lfirst(lc);
1269 :
1270 8440 : if (IsA(node, Var))
1271 : {
1272 8335 : Var *var = (Var *) node;
1273 :
1274 8335 : found_laterals = true;
1275 8335 : lateral_relids = bms_add_member(lateral_relids,
1276 : var->varno);
1277 : }
1278 105 : else if (IsA(node, PlaceHolderVar))
1279 : {
1280 105 : PlaceHolderVar *phv = (PlaceHolderVar *) node;
1281 105 : PlaceHolderInfo *phinfo = find_placeholder_info(root, phv);
1282 :
1283 105 : found_laterals = true;
1284 105 : lateral_relids = bms_add_members(lateral_relids,
1285 105 : phinfo->ph_eval_at);
1286 : }
1287 : else
1288 : Assert(false);
1289 : }
1290 :
1291 : /* We now have all the simple lateral refs from this rel */
1292 16804 : brel->direct_lateral_relids = lateral_relids;
1293 16804 : brel->lateral_relids = bms_copy(lateral_relids);
1294 : }
1295 :
1296 : /*
1297 : * Now check for lateral references within PlaceHolderVars, and mark their
1298 : * eval_at rels as having lateral references to the source rels.
1299 : *
1300 : * For a PHV that is due to be evaluated at a baserel, mark its source(s)
1301 : * as direct lateral dependencies of the baserel (adding onto the ones
1302 : * recorded above). If it's due to be evaluated at a join, mark its
1303 : * source(s) as indirect lateral dependencies of each baserel in the join,
1304 : * ie put them into lateral_relids but not direct_lateral_relids. This is
1305 : * appropriate because we can't put any such baserel on the outside of a
1306 : * join to one of the PHV's lateral dependencies, but on the other hand we
1307 : * also can't yet join it directly to the dependency.
1308 : */
1309 7548 : foreach(lc, root->placeholder_list)
1310 : {
1311 453 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
1312 453 : Relids eval_at = phinfo->ph_eval_at;
1313 : Relids lateral_refs;
1314 : int varno;
1315 :
1316 453 : if (phinfo->ph_lateral == NULL)
1317 236 : continue; /* PHV is uninteresting if no lateral refs */
1318 :
1319 217 : found_laterals = true;
1320 :
1321 : /*
1322 : * Include only baserels not outer joins in the evaluation sites'
1323 : * lateral relids. This avoids problems when outer join order gets
1324 : * rearranged, and it should still ensure that the lateral values are
1325 : * available when needed.
1326 : */
1327 217 : lateral_refs = bms_intersect(phinfo->ph_lateral, root->all_baserels);
1328 : Assert(!bms_is_empty(lateral_refs));
1329 :
1330 217 : if (bms_get_singleton_member(eval_at, &varno))
1331 : {
1332 : /* Evaluation site is a baserel */
1333 162 : RelOptInfo *brel = find_base_rel(root, varno);
1334 :
1335 162 : brel->direct_lateral_relids =
1336 162 : bms_add_members(brel->direct_lateral_relids,
1337 : lateral_refs);
1338 162 : brel->lateral_relids =
1339 162 : bms_add_members(brel->lateral_relids,
1340 : lateral_refs);
1341 : }
1342 : else
1343 : {
1344 : /* Evaluation site is a join */
1345 55 : varno = -1;
1346 165 : while ((varno = bms_next_member(eval_at, varno)) >= 0)
1347 : {
1348 110 : RelOptInfo *brel = find_base_rel_ignore_join(root, varno);
1349 :
1350 110 : if (brel == NULL)
1351 0 : continue; /* ignore outer joins in eval_at */
1352 110 : brel->lateral_relids = bms_add_members(brel->lateral_relids,
1353 : lateral_refs);
1354 : }
1355 : }
1356 : }
1357 :
1358 : /*
1359 : * If we found no actual lateral references, we're done; but reset the
1360 : * hasLateralRTEs flag to avoid useless work later.
1361 : */
1362 7095 : if (!found_laterals)
1363 : {
1364 1093 : root->hasLateralRTEs = false;
1365 1093 : return;
1366 : }
1367 :
1368 : /*
1369 : * Calculate the transitive closure of the lateral_relids sets, so that
1370 : * they describe both direct and indirect lateral references. If relation
1371 : * X references Y laterally, and Y references Z laterally, then we will
1372 : * have to scan X on the inside of a nestloop with Z, so for all intents
1373 : * and purposes X is laterally dependent on Z too.
1374 : *
1375 : * This code is essentially Warshall's algorithm for transitive closure.
1376 : * The outer loop considers each baserel, and propagates its lateral
1377 : * dependencies to those baserels that have a lateral dependency on it.
1378 : */
1379 26419 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
1380 : {
1381 20417 : RelOptInfo *brel = root->simple_rel_array[rti];
1382 : Relids outer_lateral_relids;
1383 : Index rti2;
1384 :
1385 20417 : if (brel == NULL || brel->reloptkind != RELOPT_BASEREL)
1386 5951 : continue;
1387 :
1388 : /* need not consider baserel further if it has no lateral refs */
1389 14466 : outer_lateral_relids = brel->lateral_relids;
1390 14466 : if (outer_lateral_relids == NULL)
1391 8338 : continue;
1392 :
1393 : /* else scan all baserels */
1394 27353 : for (rti2 = 1; rti2 < root->simple_rel_array_size; rti2++)
1395 : {
1396 21225 : RelOptInfo *brel2 = root->simple_rel_array[rti2];
1397 :
1398 21225 : if (brel2 == NULL || brel2->reloptkind != RELOPT_BASEREL)
1399 6296 : continue;
1400 :
1401 : /* if brel2 has lateral ref to brel, propagate brel's refs */
1402 14929 : if (bms_is_member(rti, brel2->lateral_relids))
1403 56 : brel2->lateral_relids = bms_add_members(brel2->lateral_relids,
1404 : outer_lateral_relids);
1405 : }
1406 : }
1407 :
1408 : /*
1409 : * Now that we've identified all lateral references, mark each baserel
1410 : * with the set of relids of rels that reference it laterally (possibly
1411 : * indirectly) --- that is, the inverse mapping of lateral_relids.
1412 : */
1413 26419 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
1414 : {
1415 20417 : RelOptInfo *brel = root->simple_rel_array[rti];
1416 : Relids lateral_relids;
1417 : int rti2;
1418 :
1419 20417 : if (brel == NULL || brel->reloptkind != RELOPT_BASEREL)
1420 5951 : continue;
1421 :
1422 : /* Nothing to do at rels with no lateral refs */
1423 14466 : lateral_relids = brel->lateral_relids;
1424 14466 : if (bms_is_empty(lateral_relids))
1425 8338 : continue;
1426 :
1427 : /* No rel should have a lateral dependency on itself */
1428 : Assert(!bms_is_member(rti, lateral_relids));
1429 :
1430 : /* Mark this rel's referencees */
1431 6128 : rti2 = -1;
1432 12712 : while ((rti2 = bms_next_member(lateral_relids, rti2)) >= 0)
1433 : {
1434 6584 : RelOptInfo *brel2 = root->simple_rel_array[rti2];
1435 :
1436 6584 : if (brel2 == NULL)
1437 10 : continue; /* must be an OJ */
1438 :
1439 : Assert(brel2->reloptkind == RELOPT_BASEREL);
1440 6574 : brel2->lateral_referencers =
1441 6574 : bms_add_member(brel2->lateral_referencers, rti);
1442 : }
1443 : }
1444 : }
1445 :
1446 :
1447 : /*****************************************************************************
1448 : *
1449 : * JOIN TREE PROCESSING
1450 : *
1451 : *****************************************************************************/
1452 :
1453 : /*
1454 : * deconstruct_jointree
1455 : * Recursively scan the query's join tree for WHERE and JOIN/ON qual
1456 : * clauses, and add these to the appropriate restrictinfo and joininfo
1457 : * lists belonging to base RelOptInfos. Also, add SpecialJoinInfo nodes
1458 : * to root->join_info_list for any outer joins appearing in the query tree.
1459 : * Return a "joinlist" data structure showing the join order decisions
1460 : * that need to be made by make_one_rel().
1461 : *
1462 : * The "joinlist" result is a list of items that are either RangeTblRef
1463 : * jointree nodes or sub-joinlists. All the items at the same level of
1464 : * joinlist must be joined in an order to be determined by make_one_rel()
1465 : * (note that legal orders may be constrained by SpecialJoinInfo nodes).
1466 : * A sub-joinlist represents a subproblem to be planned separately. Currently
1467 : * sub-joinlists arise only from FULL OUTER JOIN or when collapsing of
1468 : * subproblems is stopped by join_collapse_limit or from_collapse_limit.
1469 : */
1470 : List *
1471 253302 : deconstruct_jointree(PlannerInfo *root)
1472 : {
1473 : List *result;
1474 : JoinDomain *top_jdomain;
1475 253302 : List *item_list = NIL;
1476 : ListCell *lc;
1477 :
1478 : /*
1479 : * After this point, no more PlaceHolderInfos may be made, because
1480 : * make_outerjoininfo requires all active placeholders to be present in
1481 : * root->placeholder_list while we crawl up the join tree.
1482 : */
1483 253302 : root->placeholdersFrozen = true;
1484 :
1485 : /* Fetch the already-created top-level join domain for the query */
1486 253302 : top_jdomain = linitial_node(JoinDomain, root->join_domains);
1487 253302 : top_jdomain->jd_relids = NULL; /* filled during deconstruct_recurse */
1488 :
1489 : /* Start recursion at top of jointree */
1490 : Assert(root->parse->jointree != NULL &&
1491 : IsA(root->parse->jointree, FromExpr));
1492 :
1493 : /* These are filled as we scan the jointree */
1494 253302 : root->all_baserels = NULL;
1495 253302 : root->outer_join_rels = NULL;
1496 :
1497 : /* Perform the initial scan of the jointree */
1498 253302 : result = deconstruct_recurse(root, (Node *) root->parse->jointree,
1499 : top_jdomain, NULL,
1500 : &item_list);
1501 :
1502 : /* Now we can form the value of all_query_rels, too */
1503 253302 : root->all_query_rels = bms_union(root->all_baserels, root->outer_join_rels);
1504 :
1505 : /* ... which should match what we computed for the top join domain */
1506 : Assert(bms_equal(root->all_query_rels, top_jdomain->jd_relids));
1507 :
1508 : /* Now scan all the jointree nodes again, and distribute quals */
1509 975399 : foreach(lc, item_list)
1510 : {
1511 722097 : JoinTreeItem *jtitem = (JoinTreeItem *) lfirst(lc);
1512 :
1513 722097 : deconstruct_distribute(root, jtitem);
1514 : }
1515 :
1516 : /*
1517 : * If there were any special joins then we may have some postponed LEFT
1518 : * JOIN clauses to deal with.
1519 : */
1520 253302 : if (root->join_info_list)
1521 : {
1522 213806 : foreach(lc, item_list)
1523 : {
1524 180995 : JoinTreeItem *jtitem = (JoinTreeItem *) lfirst(lc);
1525 :
1526 180995 : if (jtitem->oj_joinclauses != NIL)
1527 31657 : deconstruct_distribute_oj_quals(root, item_list, jtitem);
1528 : }
1529 : }
1530 :
1531 : /* Don't need the JoinTreeItems any more */
1532 253302 : list_free_deep(item_list);
1533 :
1534 253302 : return result;
1535 : }
1536 :
1537 : /*
1538 : * deconstruct_recurse
1539 : * One recursion level of deconstruct_jointree's initial jointree scan.
1540 : *
1541 : * jtnode is the jointree node to examine, and parent_domain is the
1542 : * enclosing join domain. (We must add all base+OJ relids appearing
1543 : * here or below to parent_domain.) parent_jtitem is the JoinTreeItem
1544 : * for the parent jointree node, or NULL at the top of the recursion.
1545 : *
1546 : * item_list is an in/out parameter: we add a JoinTreeItem struct to
1547 : * that list for each jointree node, in depth-first traversal order.
1548 : * (Hence, after each call, the last list item corresponds to its jtnode.)
1549 : *
1550 : * Return value is the appropriate joinlist for this jointree node.
1551 : */
1552 : static List *
1553 722097 : deconstruct_recurse(PlannerInfo *root, Node *jtnode,
1554 : JoinDomain *parent_domain,
1555 : JoinTreeItem *parent_jtitem,
1556 : List **item_list)
1557 : {
1558 : List *joinlist;
1559 : JoinTreeItem *jtitem;
1560 :
1561 : Assert(jtnode != NULL);
1562 :
1563 : /* Make the new JoinTreeItem, but don't add it to item_list yet */
1564 722097 : jtitem = palloc0_object(JoinTreeItem);
1565 722097 : jtitem->jtnode = jtnode;
1566 722097 : jtitem->jti_parent = parent_jtitem;
1567 :
1568 722097 : if (IsA(jtnode, RangeTblRef))
1569 : {
1570 373746 : int varno = ((RangeTblRef *) jtnode)->rtindex;
1571 :
1572 : /* Fill all_baserels as we encounter baserel jointree nodes */
1573 373746 : root->all_baserels = bms_add_member(root->all_baserels, varno);
1574 : /* This node belongs to parent_domain */
1575 373746 : jtitem->jdomain = parent_domain;
1576 373746 : parent_domain->jd_relids = bms_add_member(parent_domain->jd_relids,
1577 : varno);
1578 : /* qualscope is just the one RTE */
1579 373746 : jtitem->qualscope = bms_make_singleton(varno);
1580 : /* A single baserel does not create an inner join */
1581 373746 : jtitem->inner_join_rels = NULL;
1582 373746 : joinlist = list_make1(jtnode);
1583 : }
1584 348351 : else if (IsA(jtnode, FromExpr))
1585 : {
1586 265984 : FromExpr *f = (FromExpr *) jtnode;
1587 : int remaining;
1588 : ListCell *l;
1589 :
1590 : /* This node belongs to parent_domain, as do its children */
1591 265984 : jtitem->jdomain = parent_domain;
1592 :
1593 : /*
1594 : * Recurse to handle child nodes, and compute output joinlist. We
1595 : * collapse subproblems into a single joinlist whenever the resulting
1596 : * joinlist wouldn't exceed from_collapse_limit members. Also, always
1597 : * collapse one-element subproblems, since that won't lengthen the
1598 : * joinlist anyway.
1599 : */
1600 265984 : jtitem->qualscope = NULL;
1601 265984 : jtitem->inner_join_rels = NULL;
1602 265984 : joinlist = NIL;
1603 265984 : remaining = list_length(f->fromlist);
1604 570045 : foreach(l, f->fromlist)
1605 : {
1606 : JoinTreeItem *sub_item;
1607 : List *sub_joinlist;
1608 : int sub_members;
1609 :
1610 304061 : sub_joinlist = deconstruct_recurse(root, lfirst(l),
1611 : parent_domain,
1612 : jtitem,
1613 : item_list);
1614 304061 : sub_item = (JoinTreeItem *) llast(*item_list);
1615 608122 : jtitem->qualscope = bms_add_members(jtitem->qualscope,
1616 304061 : sub_item->qualscope);
1617 304061 : jtitem->inner_join_rels = sub_item->inner_join_rels;
1618 304061 : sub_members = list_length(sub_joinlist);
1619 304061 : remaining--;
1620 304061 : if (sub_members <= 1 ||
1621 55592 : list_length(joinlist) + sub_members + remaining <= from_collapse_limit)
1622 304051 : joinlist = list_concat(joinlist, sub_joinlist);
1623 : else
1624 10 : joinlist = lappend(joinlist, sub_joinlist);
1625 : }
1626 :
1627 : /*
1628 : * A FROM with more than one list element is an inner join subsuming
1629 : * all below it, so we should report inner_join_rels = qualscope. If
1630 : * there was exactly one element, we should (and already did) report
1631 : * whatever its inner_join_rels were. If there were no elements (is
1632 : * that still possible?) the initialization before the loop fixed it.
1633 : */
1634 265984 : if (list_length(f->fromlist) > 1)
1635 33109 : jtitem->inner_join_rels = jtitem->qualscope;
1636 : }
1637 82367 : else if (IsA(jtnode, JoinExpr))
1638 : {
1639 82367 : JoinExpr *j = (JoinExpr *) jtnode;
1640 : JoinDomain *child_domain,
1641 : *fj_domain;
1642 : JoinTreeItem *left_item,
1643 : *right_item;
1644 : List *leftjoinlist,
1645 : *rightjoinlist;
1646 :
1647 82367 : switch (j->jointype)
1648 : {
1649 38819 : case JOIN_INNER:
1650 : /* This node belongs to parent_domain, as do its children */
1651 38819 : jtitem->jdomain = parent_domain;
1652 : /* Recurse */
1653 38819 : leftjoinlist = deconstruct_recurse(root, j->larg,
1654 : parent_domain,
1655 : jtitem,
1656 : item_list);
1657 38819 : left_item = (JoinTreeItem *) llast(*item_list);
1658 38819 : rightjoinlist = deconstruct_recurse(root, j->rarg,
1659 : parent_domain,
1660 : jtitem,
1661 : item_list);
1662 38819 : right_item = (JoinTreeItem *) llast(*item_list);
1663 : /* Compute qualscope etc */
1664 77638 : jtitem->qualscope = bms_union(left_item->qualscope,
1665 38819 : right_item->qualscope);
1666 38819 : jtitem->inner_join_rels = jtitem->qualscope;
1667 38819 : jtitem->left_rels = left_item->qualscope;
1668 38819 : jtitem->right_rels = right_item->qualscope;
1669 : /* Inner join adds no restrictions for quals */
1670 38819 : jtitem->nonnullable_rels = NULL;
1671 38819 : break;
1672 38738 : case JOIN_LEFT:
1673 : case JOIN_ANTI:
1674 : /* Make new join domain for my quals and the RHS */
1675 38738 : child_domain = makeNode(JoinDomain);
1676 38738 : child_domain->jd_relids = NULL; /* filled by recursion */
1677 38738 : root->join_domains = lappend(root->join_domains, child_domain);
1678 38738 : jtitem->jdomain = child_domain;
1679 : /* Recurse */
1680 38738 : leftjoinlist = deconstruct_recurse(root, j->larg,
1681 : parent_domain,
1682 : jtitem,
1683 : item_list);
1684 38738 : left_item = (JoinTreeItem *) llast(*item_list);
1685 38738 : rightjoinlist = deconstruct_recurse(root, j->rarg,
1686 : child_domain,
1687 : jtitem,
1688 : item_list);
1689 38738 : right_item = (JoinTreeItem *) llast(*item_list);
1690 : /* Compute join domain contents, qualscope etc */
1691 38738 : parent_domain->jd_relids =
1692 38738 : bms_add_members(parent_domain->jd_relids,
1693 38738 : child_domain->jd_relids);
1694 77476 : jtitem->qualscope = bms_union(left_item->qualscope,
1695 38738 : right_item->qualscope);
1696 : /* caution: ANTI join derived from SEMI will lack rtindex */
1697 38738 : if (j->rtindex != 0)
1698 : {
1699 33874 : parent_domain->jd_relids =
1700 33874 : bms_add_member(parent_domain->jd_relids,
1701 : j->rtindex);
1702 33874 : jtitem->qualscope = bms_add_member(jtitem->qualscope,
1703 : j->rtindex);
1704 33874 : root->outer_join_rels = bms_add_member(root->outer_join_rels,
1705 : j->rtindex);
1706 33874 : mark_rels_nulled_by_join(root, j->rtindex,
1707 : right_item->qualscope);
1708 : }
1709 77476 : jtitem->inner_join_rels = bms_union(left_item->inner_join_rels,
1710 38738 : right_item->inner_join_rels);
1711 38738 : jtitem->left_rels = left_item->qualscope;
1712 38738 : jtitem->right_rels = right_item->qualscope;
1713 38738 : jtitem->nonnullable_rels = left_item->qualscope;
1714 38738 : break;
1715 3999 : case JOIN_SEMI:
1716 : /* This node belongs to parent_domain, as do its children */
1717 3999 : jtitem->jdomain = parent_domain;
1718 : /* Recurse */
1719 3999 : leftjoinlist = deconstruct_recurse(root, j->larg,
1720 : parent_domain,
1721 : jtitem,
1722 : item_list);
1723 3999 : left_item = (JoinTreeItem *) llast(*item_list);
1724 3999 : rightjoinlist = deconstruct_recurse(root, j->rarg,
1725 : parent_domain,
1726 : jtitem,
1727 : item_list);
1728 3999 : right_item = (JoinTreeItem *) llast(*item_list);
1729 : /* Compute qualscope etc */
1730 7998 : jtitem->qualscope = bms_union(left_item->qualscope,
1731 3999 : right_item->qualscope);
1732 : /* SEMI join never has rtindex, so don't add to anything */
1733 : Assert(j->rtindex == 0);
1734 7998 : jtitem->inner_join_rels = bms_union(left_item->inner_join_rels,
1735 3999 : right_item->inner_join_rels);
1736 3999 : jtitem->left_rels = left_item->qualscope;
1737 3999 : jtitem->right_rels = right_item->qualscope;
1738 : /* Semi join adds no restrictions for quals */
1739 3999 : jtitem->nonnullable_rels = NULL;
1740 3999 : break;
1741 811 : case JOIN_FULL:
1742 : /* The FULL JOIN's quals need their very own domain */
1743 811 : fj_domain = makeNode(JoinDomain);
1744 811 : root->join_domains = lappend(root->join_domains, fj_domain);
1745 811 : jtitem->jdomain = fj_domain;
1746 : /* Recurse, giving each side its own join domain */
1747 811 : child_domain = makeNode(JoinDomain);
1748 811 : child_domain->jd_relids = NULL; /* filled by recursion */
1749 811 : root->join_domains = lappend(root->join_domains, child_domain);
1750 811 : leftjoinlist = deconstruct_recurse(root, j->larg,
1751 : child_domain,
1752 : jtitem,
1753 : item_list);
1754 811 : left_item = (JoinTreeItem *) llast(*item_list);
1755 811 : fj_domain->jd_relids = bms_copy(child_domain->jd_relids);
1756 811 : child_domain = makeNode(JoinDomain);
1757 811 : child_domain->jd_relids = NULL; /* filled by recursion */
1758 811 : root->join_domains = lappend(root->join_domains, child_domain);
1759 811 : rightjoinlist = deconstruct_recurse(root, j->rarg,
1760 : child_domain,
1761 : jtitem,
1762 : item_list);
1763 811 : right_item = (JoinTreeItem *) llast(*item_list);
1764 : /* Compute qualscope etc */
1765 1622 : fj_domain->jd_relids = bms_add_members(fj_domain->jd_relids,
1766 811 : child_domain->jd_relids);
1767 1622 : parent_domain->jd_relids = bms_add_members(parent_domain->jd_relids,
1768 811 : fj_domain->jd_relids);
1769 1622 : jtitem->qualscope = bms_union(left_item->qualscope,
1770 811 : right_item->qualscope);
1771 : Assert(j->rtindex != 0);
1772 811 : parent_domain->jd_relids = bms_add_member(parent_domain->jd_relids,
1773 : j->rtindex);
1774 811 : jtitem->qualscope = bms_add_member(jtitem->qualscope,
1775 : j->rtindex);
1776 811 : root->outer_join_rels = bms_add_member(root->outer_join_rels,
1777 : j->rtindex);
1778 811 : mark_rels_nulled_by_join(root, j->rtindex,
1779 : left_item->qualscope);
1780 811 : mark_rels_nulled_by_join(root, j->rtindex,
1781 : right_item->qualscope);
1782 1622 : jtitem->inner_join_rels = bms_union(left_item->inner_join_rels,
1783 811 : right_item->inner_join_rels);
1784 811 : jtitem->left_rels = left_item->qualscope;
1785 811 : jtitem->right_rels = right_item->qualscope;
1786 : /* each side is both outer and inner */
1787 811 : jtitem->nonnullable_rels = jtitem->qualscope;
1788 811 : break;
1789 0 : default:
1790 : /* JOIN_RIGHT was eliminated during reduce_outer_joins() */
1791 0 : elog(ERROR, "unrecognized join type: %d",
1792 : (int) j->jointype);
1793 : leftjoinlist = rightjoinlist = NIL; /* keep compiler quiet */
1794 : break;
1795 : }
1796 :
1797 : /*
1798 : * Compute the output joinlist. We fold subproblems together except
1799 : * at a FULL JOIN or where join_collapse_limit would be exceeded.
1800 : */
1801 82367 : if (j->jointype == JOIN_FULL)
1802 : {
1803 : /* force the join order exactly at this node */
1804 811 : joinlist = list_make1(list_make2(leftjoinlist, rightjoinlist));
1805 : }
1806 81556 : else if (list_length(leftjoinlist) + list_length(rightjoinlist) <=
1807 : join_collapse_limit)
1808 : {
1809 : /* OK to combine subproblems */
1810 81411 : joinlist = list_concat(leftjoinlist, rightjoinlist);
1811 : }
1812 : else
1813 : {
1814 : /* can't combine, but needn't force join order above here */
1815 : Node *leftpart,
1816 : *rightpart;
1817 :
1818 : /* avoid creating useless 1-element sublists */
1819 145 : if (list_length(leftjoinlist) == 1)
1820 25 : leftpart = (Node *) linitial(leftjoinlist);
1821 : else
1822 120 : leftpart = (Node *) leftjoinlist;
1823 145 : if (list_length(rightjoinlist) == 1)
1824 20 : rightpart = (Node *) linitial(rightjoinlist);
1825 : else
1826 125 : rightpart = (Node *) rightjoinlist;
1827 145 : joinlist = list_make2(leftpart, rightpart);
1828 : }
1829 : }
1830 : else
1831 : {
1832 0 : elog(ERROR, "unrecognized node type: %d",
1833 : (int) nodeTag(jtnode));
1834 : joinlist = NIL; /* keep compiler quiet */
1835 : }
1836 :
1837 : /* Finally, we can add the new JoinTreeItem to item_list */
1838 722097 : *item_list = lappend(*item_list, jtitem);
1839 :
1840 722097 : return joinlist;
1841 : }
1842 :
1843 : /*
1844 : * deconstruct_distribute
1845 : * Process one jointree node in phase 2 of deconstruct_jointree processing.
1846 : *
1847 : * Distribute quals of the node to appropriate restriction and join lists.
1848 : * In addition, entries will be added to root->join_info_list for outer joins.
1849 : */
1850 : static void
1851 722097 : deconstruct_distribute(PlannerInfo *root, JoinTreeItem *jtitem)
1852 : {
1853 722097 : Node *jtnode = jtitem->jtnode;
1854 :
1855 722097 : if (IsA(jtnode, RangeTblRef))
1856 : {
1857 373746 : int varno = ((RangeTblRef *) jtnode)->rtindex;
1858 :
1859 : /* Deal with any securityQuals attached to the RTE */
1860 373746 : if (root->qual_security_level > 0)
1861 2747 : process_security_barrier_quals(root,
1862 : varno,
1863 : jtitem);
1864 : }
1865 348351 : else if (IsA(jtnode, FromExpr))
1866 : {
1867 265984 : FromExpr *f = (FromExpr *) jtnode;
1868 :
1869 : /*
1870 : * Process any lateral-referencing quals that were postponed to this
1871 : * level by children.
1872 : */
1873 265984 : distribute_quals_to_rels(root, jtitem->lateral_clauses,
1874 : jtitem,
1875 : NULL,
1876 : root->qual_security_level,
1877 : jtitem->qualscope,
1878 : NULL, NULL, NULL,
1879 : true, false, false,
1880 : NULL);
1881 :
1882 : /*
1883 : * Now process the top-level quals.
1884 : */
1885 265984 : distribute_quals_to_rels(root, (List *) f->quals,
1886 : jtitem,
1887 : NULL,
1888 : root->qual_security_level,
1889 : jtitem->qualscope,
1890 : NULL, NULL, NULL,
1891 : true, false, false,
1892 : NULL);
1893 : }
1894 82367 : else if (IsA(jtnode, JoinExpr))
1895 : {
1896 82367 : JoinExpr *j = (JoinExpr *) jtnode;
1897 : Relids ojscope;
1898 : List *my_quals;
1899 : SpecialJoinInfo *sjinfo;
1900 : List **postponed_oj_qual_list;
1901 :
1902 : /*
1903 : * Include lateral-referencing quals postponed from children in
1904 : * my_quals, so that they'll be handled properly in
1905 : * make_outerjoininfo. (This is destructive to
1906 : * jtitem->lateral_clauses, but we won't use that again.)
1907 : */
1908 82367 : my_quals = list_concat(jtitem->lateral_clauses,
1909 82367 : (List *) j->quals);
1910 :
1911 : /*
1912 : * For an OJ, form the SpecialJoinInfo now, so that we can pass it to
1913 : * distribute_qual_to_rels. We must compute its ojscope too.
1914 : *
1915 : * Semijoins are a bit of a hybrid: we build a SpecialJoinInfo, but we
1916 : * want ojscope = NULL for distribute_qual_to_rels.
1917 : */
1918 82367 : if (j->jointype != JOIN_INNER)
1919 : {
1920 43548 : sjinfo = make_outerjoininfo(root,
1921 : jtitem->left_rels,
1922 : jtitem->right_rels,
1923 : jtitem->inner_join_rels,
1924 : j->jointype,
1925 43548 : j->rtindex,
1926 : my_quals);
1927 43548 : jtitem->sjinfo = sjinfo;
1928 43548 : if (j->jointype == JOIN_SEMI)
1929 3999 : ojscope = NULL;
1930 : else
1931 39549 : ojscope = bms_union(sjinfo->min_lefthand,
1932 39549 : sjinfo->min_righthand);
1933 : }
1934 : else
1935 : {
1936 38819 : sjinfo = NULL;
1937 38819 : ojscope = NULL;
1938 : }
1939 :
1940 : /*
1941 : * If it's a left join with a join clause that is strict for the LHS,
1942 : * then we need to postpone handling of any non-degenerate join
1943 : * clauses, in case the join is able to commute with another left join
1944 : * per identity 3. (Degenerate clauses need not be postponed, since
1945 : * they will drop down below this join anyway.)
1946 : */
1947 82367 : if (j->jointype == JOIN_LEFT && sjinfo->lhs_strict)
1948 : {
1949 31657 : postponed_oj_qual_list = &jtitem->oj_joinclauses;
1950 :
1951 : /*
1952 : * Add back any commutable lower OJ relids that were removed from
1953 : * min_lefthand or min_righthand, else the ojscope cross-check in
1954 : * distribute_qual_to_rels will complain. Since we are postponing
1955 : * processing of non-degenerate clauses, this addition doesn't
1956 : * affect anything except that cross-check. Real clause
1957 : * positioning decisions will be made later, when we revisit the
1958 : * postponed clauses.
1959 : */
1960 31657 : ojscope = bms_add_members(ojscope, sjinfo->commute_below_l);
1961 31657 : ojscope = bms_add_members(ojscope, sjinfo->commute_below_r);
1962 : }
1963 : else
1964 50710 : postponed_oj_qual_list = NULL;
1965 :
1966 : /* Process the JOIN's qual clauses */
1967 82367 : distribute_quals_to_rels(root, my_quals,
1968 : jtitem,
1969 : sjinfo,
1970 : root->qual_security_level,
1971 : jtitem->qualscope,
1972 : ojscope, jtitem->nonnullable_rels,
1973 : NULL, /* incompatible_relids */
1974 : true, /* allow_equivalence */
1975 : false, false, /* not clones */
1976 : postponed_oj_qual_list);
1977 :
1978 : /* And add the SpecialJoinInfo to join_info_list */
1979 82367 : if (sjinfo)
1980 43548 : root->join_info_list = lappend(root->join_info_list, sjinfo);
1981 : }
1982 : else
1983 : {
1984 0 : elog(ERROR, "unrecognized node type: %d",
1985 : (int) nodeTag(jtnode));
1986 : }
1987 722097 : }
1988 :
1989 : /*
1990 : * process_security_barrier_quals
1991 : * Transfer security-barrier quals into relation's baserestrictinfo list.
1992 : *
1993 : * The rewriter put any relevant security-barrier conditions into the RTE's
1994 : * securityQuals field, but it's now time to copy them into the rel's
1995 : * baserestrictinfo.
1996 : *
1997 : * In inheritance cases, we only consider quals attached to the parent rel
1998 : * here; they will be valid for all children too, so it's okay to consider
1999 : * them for purposes like equivalence class creation. Quals attached to
2000 : * individual child rels will be dealt with during path creation.
2001 : */
2002 : static void
2003 2747 : process_security_barrier_quals(PlannerInfo *root,
2004 : int rti, JoinTreeItem *jtitem)
2005 : {
2006 2747 : RangeTblEntry *rte = root->simple_rte_array[rti];
2007 2747 : Index security_level = 0;
2008 : ListCell *lc;
2009 :
2010 : /*
2011 : * Each element of the securityQuals list has been preprocessed into an
2012 : * implicitly-ANDed list of clauses. All the clauses in a given sublist
2013 : * should get the same security level, but successive sublists get higher
2014 : * levels.
2015 : */
2016 5512 : foreach(lc, rte->securityQuals)
2017 : {
2018 2765 : List *qualset = (List *) lfirst(lc);
2019 :
2020 : /*
2021 : * We cheat to the extent of passing ojscope = qualscope rather than
2022 : * its more logical value of NULL. The only effect this has is to
2023 : * force a Var-free qual to be evaluated at the rel rather than being
2024 : * pushed up to top of tree, which we don't want.
2025 : */
2026 2765 : distribute_quals_to_rels(root, qualset,
2027 : jtitem,
2028 : NULL,
2029 : security_level,
2030 : jtitem->qualscope,
2031 : jtitem->qualscope,
2032 : NULL,
2033 : NULL,
2034 : true,
2035 : false, false, /* not clones */
2036 : NULL);
2037 2765 : security_level++;
2038 : }
2039 :
2040 : /* Assert that qual_security_level is higher than anything we just used */
2041 : Assert(security_level <= root->qual_security_level);
2042 2747 : }
2043 :
2044 : /*
2045 : * mark_rels_nulled_by_join
2046 : * Fill RelOptInfo.nulling_relids of baserels nulled by this outer join
2047 : *
2048 : * Inputs:
2049 : * ojrelid: RT index of the join RTE (must not be 0)
2050 : * lower_rels: the base+OJ Relids syntactically below nullable side of join
2051 : */
2052 : static void
2053 35496 : mark_rels_nulled_by_join(PlannerInfo *root, Index ojrelid,
2054 : Relids lower_rels)
2055 : {
2056 35496 : int relid = -1;
2057 :
2058 73230 : while ((relid = bms_next_member(lower_rels, relid)) > 0)
2059 : {
2060 37734 : RelOptInfo *rel = root->simple_rel_array[relid];
2061 :
2062 : /* ignore the RTE_GROUP RTE */
2063 37734 : if (relid == root->group_rtindex)
2064 0 : continue;
2065 :
2066 37734 : if (rel == NULL) /* must be an outer join */
2067 : {
2068 : Assert(bms_is_member(relid, root->outer_join_rels));
2069 631 : continue;
2070 : }
2071 37103 : rel->nulling_relids = bms_add_member(rel->nulling_relids, ojrelid);
2072 : }
2073 35496 : }
2074 :
2075 : /*
2076 : * make_outerjoininfo
2077 : * Build a SpecialJoinInfo for the current outer join
2078 : *
2079 : * Inputs:
2080 : * left_rels: the base+OJ Relids syntactically on outer side of join
2081 : * right_rels: the base+OJ Relids syntactically on inner side of join
2082 : * inner_join_rels: base+OJ Relids participating in inner joins below this one
2083 : * jointype: what it says (must always be LEFT, FULL, SEMI, or ANTI)
2084 : * ojrelid: RT index of the join RTE (0 for SEMI, which isn't in the RT list)
2085 : * clause: the outer join's join condition (in implicit-AND format)
2086 : *
2087 : * The node should eventually be appended to root->join_info_list, but we
2088 : * do not do that here.
2089 : *
2090 : * Note: we assume that this function is invoked bottom-up, so that
2091 : * root->join_info_list already contains entries for all outer joins that are
2092 : * syntactically below this one.
2093 : */
2094 : static SpecialJoinInfo *
2095 43548 : make_outerjoininfo(PlannerInfo *root,
2096 : Relids left_rels, Relids right_rels,
2097 : Relids inner_join_rels,
2098 : JoinType jointype, Index ojrelid,
2099 : List *clause)
2100 : {
2101 43548 : SpecialJoinInfo *sjinfo = makeNode(SpecialJoinInfo);
2102 : Relids clause_relids;
2103 : Relids strict_relids;
2104 : Relids min_lefthand;
2105 : Relids min_righthand;
2106 : Relids commute_below_l;
2107 : Relids commute_below_r;
2108 : ListCell *l;
2109 :
2110 : /*
2111 : * We should not see RIGHT JOIN here because left/right were switched
2112 : * earlier
2113 : */
2114 : Assert(jointype != JOIN_INNER);
2115 : Assert(jointype != JOIN_RIGHT);
2116 :
2117 : /*
2118 : * Presently the executor cannot support FOR [KEY] UPDATE/SHARE marking of
2119 : * rels appearing on the nullable side of an outer join. (It's somewhat
2120 : * unclear what that would mean, anyway: what should we mark when a result
2121 : * row is generated from no element of the nullable relation?) So,
2122 : * complain if any nullable rel is FOR [KEY] UPDATE/SHARE.
2123 : *
2124 : * You might be wondering why this test isn't made far upstream in the
2125 : * parser. It's because the parser hasn't got enough info --- consider
2126 : * FOR UPDATE applied to a view. Only after rewriting and flattening do
2127 : * we know whether the view contains an outer join.
2128 : *
2129 : * We use the original RowMarkClause list here; the PlanRowMark list would
2130 : * list everything.
2131 : */
2132 43570 : foreach(l, root->parse->rowMarks)
2133 : {
2134 22 : RowMarkClause *rc = (RowMarkClause *) lfirst(l);
2135 :
2136 22 : if (bms_is_member(rc->rti, right_rels) ||
2137 4 : (jointype == JOIN_FULL && bms_is_member(rc->rti, left_rels)))
2138 0 : ereport(ERROR,
2139 : (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
2140 : /*------
2141 : translator: %s is a SQL row locking clause such as FOR UPDATE */
2142 : errmsg("%s cannot be applied to the nullable side of an outer join",
2143 : LCS_asString(rc->strength))));
2144 : }
2145 :
2146 43548 : sjinfo->syn_lefthand = left_rels;
2147 43548 : sjinfo->syn_righthand = right_rels;
2148 43548 : sjinfo->jointype = jointype;
2149 43548 : sjinfo->ojrelid = ojrelid;
2150 : /* these fields may get added to later: */
2151 43548 : sjinfo->commute_above_l = NULL;
2152 43548 : sjinfo->commute_above_r = NULL;
2153 43548 : sjinfo->commute_below_l = NULL;
2154 43548 : sjinfo->commute_below_r = NULL;
2155 :
2156 43548 : compute_semijoin_info(root, sjinfo, clause);
2157 :
2158 : /* If it's a full join, no need to be very smart */
2159 43548 : if (jointype == JOIN_FULL)
2160 : {
2161 811 : sjinfo->min_lefthand = bms_copy(left_rels);
2162 811 : sjinfo->min_righthand = bms_copy(right_rels);
2163 811 : sjinfo->lhs_strict = false; /* don't care about this */
2164 811 : return sjinfo;
2165 : }
2166 :
2167 : /*
2168 : * Retrieve all relids mentioned within the join clause.
2169 : */
2170 42737 : clause_relids = pull_varnos(root, (Node *) clause);
2171 :
2172 : /*
2173 : * For which relids is the clause strict, ie, it cannot succeed if the
2174 : * rel's columns are all NULL?
2175 : */
2176 42737 : strict_relids = find_nonnullable_rels((Node *) clause);
2177 :
2178 : /* Remember whether the clause is strict for any LHS relations */
2179 42737 : sjinfo->lhs_strict = bms_overlap(strict_relids, left_rels);
2180 :
2181 : /*
2182 : * Required LHS always includes the LHS rels mentioned in the clause. We
2183 : * may have to add more rels based on lower outer joins; see below.
2184 : */
2185 42737 : min_lefthand = bms_intersect(clause_relids, left_rels);
2186 :
2187 : /*
2188 : * Similarly for required RHS. But here, we must also include any lower
2189 : * inner joins, to ensure we don't try to commute with any of them.
2190 : */
2191 42737 : min_righthand = bms_int_members(bms_union(clause_relids, inner_join_rels),
2192 : right_rels);
2193 :
2194 : /*
2195 : * Now check previous outer joins for ordering restrictions.
2196 : *
2197 : * commute_below_l and commute_below_r accumulate the relids of lower
2198 : * outer joins that we think this one can commute with. These decisions
2199 : * are just tentative within this loop, since we might find an
2200 : * intermediate outer join that prevents commutation. Surviving relids
2201 : * will get merged into the SpecialJoinInfo structs afterwards.
2202 : */
2203 42737 : commute_below_l = commute_below_r = NULL;
2204 55630 : foreach(l, root->join_info_list)
2205 : {
2206 12893 : SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(l);
2207 : bool have_unsafe_phvs;
2208 :
2209 : /*
2210 : * A full join is an optimization barrier: we can't associate into or
2211 : * out of it. Hence, if it overlaps either LHS or RHS of the current
2212 : * rel, expand that side's min relset to cover the whole full join.
2213 : */
2214 12893 : if (otherinfo->jointype == JOIN_FULL)
2215 : {
2216 : Assert(otherinfo->ojrelid != 0);
2217 75 : if (bms_overlap(left_rels, otherinfo->syn_lefthand) ||
2218 25 : bms_overlap(left_rels, otherinfo->syn_righthand))
2219 : {
2220 25 : min_lefthand = bms_add_members(min_lefthand,
2221 25 : otherinfo->syn_lefthand);
2222 25 : min_lefthand = bms_add_members(min_lefthand,
2223 25 : otherinfo->syn_righthand);
2224 25 : min_lefthand = bms_add_member(min_lefthand,
2225 25 : otherinfo->ojrelid);
2226 : }
2227 75 : if (bms_overlap(right_rels, otherinfo->syn_lefthand) ||
2228 25 : bms_overlap(right_rels, otherinfo->syn_righthand))
2229 : {
2230 25 : min_righthand = bms_add_members(min_righthand,
2231 25 : otherinfo->syn_lefthand);
2232 25 : min_righthand = bms_add_members(min_righthand,
2233 25 : otherinfo->syn_righthand);
2234 25 : min_righthand = bms_add_member(min_righthand,
2235 25 : otherinfo->ojrelid);
2236 : }
2237 : /* Needn't do anything else with the full join */
2238 50 : continue;
2239 : }
2240 :
2241 : /*
2242 : * If our join condition contains any PlaceHolderVars that need to be
2243 : * evaluated above the lower OJ, then we can't commute with it.
2244 : */
2245 12843 : if (otherinfo->ojrelid != 0)
2246 : have_unsafe_phvs =
2247 12617 : contain_placeholder_references_to(root,
2248 : (Node *) clause,
2249 12617 : otherinfo->ojrelid);
2250 : else
2251 226 : have_unsafe_phvs = false;
2252 :
2253 : /*
2254 : * For a lower OJ in our LHS, if our join condition uses the lower
2255 : * join's RHS and is not strict for that rel, we must preserve the
2256 : * ordering of the two OJs, so add lower OJ's full syntactic relset to
2257 : * min_lefthand. (We must use its full syntactic relset, not just its
2258 : * min_lefthand + min_righthand. This is because there might be other
2259 : * OJs below this one that this one can commute with, but we cannot
2260 : * commute with them if we don't with this one.) Also, if we have
2261 : * unsafe PHVs or the current join is a semijoin or antijoin, we must
2262 : * preserve ordering regardless of strictness.
2263 : *
2264 : * Note: I believe we have to insist on being strict for at least one
2265 : * rel in the lower OJ's min_righthand, not its whole syn_righthand.
2266 : *
2267 : * When we don't need to preserve ordering, check to see if outer join
2268 : * identity 3 applies, and if so, remove the lower OJ's ojrelid from
2269 : * our min_lefthand so that commutation is allowed.
2270 : */
2271 12843 : if (bms_overlap(left_rels, otherinfo->syn_righthand))
2272 : {
2273 12143 : if (bms_overlap(clause_relids, otherinfo->syn_righthand) &&
2274 2729 : (have_unsafe_phvs ||
2275 2729 : jointype == JOIN_SEMI || jointype == JOIN_ANTI ||
2276 2729 : !bms_overlap(strict_relids, otherinfo->min_righthand)))
2277 : {
2278 : /* Preserve ordering */
2279 35 : min_lefthand = bms_add_members(min_lefthand,
2280 35 : otherinfo->syn_lefthand);
2281 35 : min_lefthand = bms_add_members(min_lefthand,
2282 35 : otherinfo->syn_righthand);
2283 35 : if (otherinfo->ojrelid != 0)
2284 35 : min_lefthand = bms_add_member(min_lefthand,
2285 35 : otherinfo->ojrelid);
2286 : }
2287 12108 : else if (jointype == JOIN_LEFT &&
2288 23313 : otherinfo->jointype == JOIN_LEFT &&
2289 11653 : bms_overlap(strict_relids, otherinfo->min_righthand) &&
2290 2699 : !bms_overlap(clause_relids, otherinfo->syn_lefthand))
2291 : {
2292 : /* Identity 3 applies, so remove the ordering restriction */
2293 2660 : min_lefthand = bms_del_member(min_lefthand, otherinfo->ojrelid);
2294 : /* Record the (still tentative) commutability relationship */
2295 : commute_below_l =
2296 2660 : bms_add_member(commute_below_l, otherinfo->ojrelid);
2297 : }
2298 : }
2299 :
2300 : /*
2301 : * For a lower OJ in our RHS, if our join condition does not use the
2302 : * lower join's RHS and the lower OJ's join condition is strict, we
2303 : * can interchange the ordering of the two OJs; otherwise we must add
2304 : * the lower OJ's full syntactic relset to min_righthand.
2305 : *
2306 : * Also, if our join condition does not use the lower join's LHS
2307 : * either, force the ordering to be preserved. Otherwise we can end
2308 : * up with SpecialJoinInfos with identical min_righthands, which can
2309 : * confuse join_is_legal (see discussion in backend/optimizer/README).
2310 : *
2311 : * Also, we must preserve ordering anyway if we have unsafe PHVs, or
2312 : * if either this join or the lower OJ is a semijoin or antijoin.
2313 : *
2314 : * When we don't need to preserve ordering, check to see if outer join
2315 : * identity 3 applies, and if so, remove the lower OJ's ojrelid from
2316 : * our min_righthand so that commutation is allowed.
2317 : */
2318 12843 : if (bms_overlap(right_rels, otherinfo->syn_righthand))
2319 : {
2320 635 : if (bms_overlap(clause_relids, otherinfo->syn_righthand) ||
2321 595 : !bms_overlap(clause_relids, otherinfo->min_lefthand) ||
2322 330 : have_unsafe_phvs ||
2323 262 : jointype == JOIN_SEMI ||
2324 237 : jointype == JOIN_ANTI ||
2325 237 : otherinfo->jointype == JOIN_SEMI ||
2326 203 : otherinfo->jointype == JOIN_ANTI ||
2327 203 : !otherinfo->lhs_strict)
2328 : {
2329 : /* Preserve ordering */
2330 452 : min_righthand = bms_add_members(min_righthand,
2331 452 : otherinfo->syn_lefthand);
2332 452 : min_righthand = bms_add_members(min_righthand,
2333 452 : otherinfo->syn_righthand);
2334 452 : if (otherinfo->ojrelid != 0)
2335 345 : min_righthand = bms_add_member(min_righthand,
2336 345 : otherinfo->ojrelid);
2337 : }
2338 183 : else if (jointype == JOIN_LEFT &&
2339 183 : otherinfo->jointype == JOIN_LEFT &&
2340 183 : otherinfo->lhs_strict)
2341 : {
2342 : /* Identity 3 applies, so remove the ordering restriction */
2343 183 : min_righthand = bms_del_member(min_righthand,
2344 183 : otherinfo->ojrelid);
2345 : /* Record the (still tentative) commutability relationship */
2346 : commute_below_r =
2347 183 : bms_add_member(commute_below_r, otherinfo->ojrelid);
2348 : }
2349 : }
2350 : }
2351 :
2352 : /*
2353 : * Examine PlaceHolderVars. If a PHV is supposed to be evaluated within
2354 : * this join's nullable side, then ensure that min_righthand contains the
2355 : * full eval_at set of the PHV. This ensures that the PHV actually can be
2356 : * evaluated within the RHS. Note that this works only because we should
2357 : * already have determined the final eval_at level for any PHV
2358 : * syntactically within this join.
2359 : */
2360 43873 : foreach(l, root->placeholder_list)
2361 : {
2362 1136 : PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(l);
2363 1136 : Relids ph_syn_level = phinfo->ph_var->phrels;
2364 :
2365 : /* Ignore placeholder if it didn't syntactically come from RHS */
2366 1136 : if (!bms_is_subset(ph_syn_level, right_rels))
2367 396 : continue;
2368 :
2369 : /* Else, prevent join from being formed before we eval the PHV */
2370 740 : min_righthand = bms_add_members(min_righthand, phinfo->ph_eval_at);
2371 : }
2372 :
2373 : /*
2374 : * If we found nothing to put in min_lefthand, punt and make it the full
2375 : * LHS, to avoid having an empty min_lefthand which will confuse later
2376 : * processing. (We don't try to be smart about such cases, just correct.)
2377 : * Likewise for min_righthand.
2378 : */
2379 42737 : if (bms_is_empty(min_lefthand))
2380 1172 : min_lefthand = bms_copy(left_rels);
2381 42737 : if (bms_is_empty(min_righthand))
2382 768 : min_righthand = bms_copy(right_rels);
2383 :
2384 : /* Now they'd better be nonempty */
2385 : Assert(!bms_is_empty(min_lefthand));
2386 : Assert(!bms_is_empty(min_righthand));
2387 : /* Shouldn't overlap either */
2388 : Assert(!bms_overlap(min_lefthand, min_righthand));
2389 :
2390 42737 : sjinfo->min_lefthand = min_lefthand;
2391 42737 : sjinfo->min_righthand = min_righthand;
2392 :
2393 : /*
2394 : * Now that we've identified the correct min_lefthand and min_righthand,
2395 : * any commute_below_l or commute_below_r relids that have not gotten
2396 : * added back into those sets (due to intervening outer joins) are indeed
2397 : * commutable with this one.
2398 : *
2399 : * First, delete any subsequently-added-back relids (this is easier than
2400 : * maintaining commute_below_l/r precisely through all the above).
2401 : */
2402 42737 : commute_below_l = bms_del_members(commute_below_l, min_lefthand);
2403 42737 : commute_below_r = bms_del_members(commute_below_r, min_righthand);
2404 :
2405 : /* Anything left? */
2406 42737 : if (commute_below_l || commute_below_r)
2407 : {
2408 : /* Yup, so we must update the derived data in the SpecialJoinInfos */
2409 2778 : sjinfo->commute_below_l = commute_below_l;
2410 2778 : sjinfo->commute_below_r = commute_below_r;
2411 6195 : foreach(l, root->join_info_list)
2412 : {
2413 3417 : SpecialJoinInfo *otherinfo = (SpecialJoinInfo *) lfirst(l);
2414 :
2415 3417 : if (bms_is_member(otherinfo->ojrelid, commute_below_l))
2416 2660 : otherinfo->commute_above_l =
2417 2660 : bms_add_member(otherinfo->commute_above_l, ojrelid);
2418 757 : else if (bms_is_member(otherinfo->ojrelid, commute_below_r))
2419 158 : otherinfo->commute_above_r =
2420 158 : bms_add_member(otherinfo->commute_above_r, ojrelid);
2421 : }
2422 : }
2423 :
2424 42737 : return sjinfo;
2425 : }
2426 :
2427 : /*
2428 : * compute_semijoin_info
2429 : * Fill semijoin-related fields of a new SpecialJoinInfo
2430 : *
2431 : * Note: this relies on only the jointype and syn_righthand fields of the
2432 : * SpecialJoinInfo; the rest may not be set yet.
2433 : */
2434 : static void
2435 43548 : compute_semijoin_info(PlannerInfo *root, SpecialJoinInfo *sjinfo, List *clause)
2436 : {
2437 : List *semi_operators;
2438 : List *semi_rhs_exprs;
2439 : bool all_btree;
2440 : bool all_hash;
2441 : ListCell *lc;
2442 :
2443 : /* Initialize semijoin-related fields in case we can't unique-ify */
2444 43548 : sjinfo->semi_can_btree = false;
2445 43548 : sjinfo->semi_can_hash = false;
2446 43548 : sjinfo->semi_operators = NIL;
2447 43548 : sjinfo->semi_rhs_exprs = NIL;
2448 :
2449 : /* Nothing more to do if it's not a semijoin */
2450 43548 : if (sjinfo->jointype != JOIN_SEMI)
2451 39549 : return;
2452 :
2453 : /*
2454 : * Look to see whether the semijoin's join quals consist of AND'ed
2455 : * equality operators, with (only) RHS variables on only one side of each
2456 : * one. If so, we can figure out how to enforce uniqueness for the RHS.
2457 : *
2458 : * Note that the input clause list is the list of quals that are
2459 : * *syntactically* associated with the semijoin, which in practice means
2460 : * the synthesized comparison list for an IN or the WHERE of an EXISTS.
2461 : * Particularly in the latter case, it might contain clauses that aren't
2462 : * *semantically* associated with the join, but refer to just one side or
2463 : * the other. We can ignore such clauses here, as they will just drop
2464 : * down to be processed within one side or the other. (It is okay to
2465 : * consider only the syntactically-associated clauses here because for a
2466 : * semijoin, no higher-level quals could refer to the RHS, and so there
2467 : * can be no other quals that are semantically associated with this join.
2468 : * We do things this way because it is useful to have the set of potential
2469 : * unique-ification expressions before we can extract the list of quals
2470 : * that are actually semantically associated with the particular join.)
2471 : *
2472 : * Note that the semi_operators list consists of the joinqual operators
2473 : * themselves (but commuted if needed to put the RHS value on the right).
2474 : * These could be cross-type operators, in which case the operator
2475 : * actually needed for uniqueness is a related single-type operator. We
2476 : * assume here that that operator will be available from the btree or hash
2477 : * opclass when the time comes ... if not, create_unique_plan() will fail.
2478 : */
2479 3999 : semi_operators = NIL;
2480 3999 : semi_rhs_exprs = NIL;
2481 3999 : all_btree = true;
2482 3999 : all_hash = enable_hashagg; /* don't consider hash if not enabled */
2483 8291 : foreach(lc, clause)
2484 : {
2485 4381 : OpExpr *op = (OpExpr *) lfirst(lc);
2486 : Oid opno;
2487 : Node *left_expr;
2488 : Node *right_expr;
2489 : Relids left_varnos;
2490 : Relids right_varnos;
2491 : Relids all_varnos;
2492 : Oid opinputtype;
2493 :
2494 : /* Is it a binary opclause? */
2495 8678 : if (!IsA(op, OpExpr) ||
2496 4297 : list_length(op->args) != 2)
2497 : {
2498 : /* No, but does it reference both sides? */
2499 84 : all_varnos = pull_varnos(root, (Node *) op);
2500 158 : if (!bms_overlap(all_varnos, sjinfo->syn_righthand) ||
2501 74 : bms_is_subset(all_varnos, sjinfo->syn_righthand))
2502 : {
2503 : /*
2504 : * Clause refers to only one rel, so ignore it --- unless it
2505 : * contains volatile functions, in which case we'd better
2506 : * punt.
2507 : */
2508 74 : if (contain_volatile_functions((Node *) op))
2509 89 : return;
2510 74 : continue;
2511 : }
2512 : /* Non-operator clause referencing both sides, must punt */
2513 10 : return;
2514 : }
2515 :
2516 : /* Extract data from binary opclause */
2517 4297 : opno = op->opno;
2518 4297 : left_expr = linitial(op->args);
2519 4297 : right_expr = lsecond(op->args);
2520 4297 : left_varnos = pull_varnos(root, left_expr);
2521 4297 : right_varnos = pull_varnos(root, right_expr);
2522 4297 : all_varnos = bms_union(left_varnos, right_varnos);
2523 4297 : opinputtype = exprType(left_expr);
2524 :
2525 : /* Does it reference both sides? */
2526 8580 : if (!bms_overlap(all_varnos, sjinfo->syn_righthand) ||
2527 4283 : bms_is_subset(all_varnos, sjinfo->syn_righthand))
2528 : {
2529 : /*
2530 : * Clause refers to only one rel, so ignore it --- unless it
2531 : * contains volatile functions, in which case we'd better punt.
2532 : */
2533 93 : if (contain_volatile_functions((Node *) op))
2534 0 : return;
2535 93 : continue;
2536 : }
2537 :
2538 : /* check rel membership of arguments */
2539 8408 : if (!bms_is_empty(right_varnos) &&
2540 4204 : bms_is_subset(right_varnos, sjinfo->syn_righthand) &&
2541 3872 : !bms_overlap(left_varnos, sjinfo->syn_righthand))
2542 : {
2543 : /* typical case, right_expr is RHS variable */
2544 : }
2545 664 : else if (!bms_is_empty(left_varnos) &&
2546 332 : bms_is_subset(left_varnos, sjinfo->syn_righthand) &&
2547 327 : !bms_overlap(right_varnos, sjinfo->syn_righthand))
2548 : {
2549 : /* flipped case, left_expr is RHS variable */
2550 327 : opno = get_commutator(opno);
2551 327 : if (!OidIsValid(opno))
2552 0 : return;
2553 327 : right_expr = left_expr;
2554 : }
2555 : else
2556 : {
2557 : /* mixed membership of args, punt */
2558 5 : return;
2559 : }
2560 :
2561 : /* all operators must be btree equality or hash equality */
2562 4199 : if (all_btree)
2563 : {
2564 : /* oprcanmerge is considered a hint... */
2565 8324 : if (!op_mergejoinable(opno, opinputtype) ||
2566 4125 : get_mergejoin_opfamilies(opno) == NIL)
2567 74 : all_btree = false;
2568 : }
2569 4199 : if (all_hash)
2570 : {
2571 : /* ... but oprcanhash had better be correct */
2572 4145 : if (!op_hashjoinable(opno, opinputtype))
2573 74 : all_hash = false;
2574 : }
2575 4199 : if (!(all_btree || all_hash))
2576 74 : return;
2577 :
2578 : /* so far so good, keep building lists */
2579 4125 : semi_operators = lappend_oid(semi_operators, opno);
2580 4125 : semi_rhs_exprs = lappend(semi_rhs_exprs, copyObject(right_expr));
2581 : }
2582 :
2583 : /* Punt if we didn't find at least one column to unique-ify */
2584 3910 : if (semi_rhs_exprs == NIL)
2585 10 : return;
2586 :
2587 : /*
2588 : * The expressions we'd need to unique-ify mustn't be volatile.
2589 : */
2590 3900 : if (contain_volatile_functions((Node *) semi_rhs_exprs))
2591 0 : return;
2592 :
2593 : /*
2594 : * If we get here, we can unique-ify the semijoin's RHS using at least one
2595 : * of sorting and hashing. Save the information about how to do that.
2596 : */
2597 3900 : sjinfo->semi_can_btree = all_btree;
2598 3900 : sjinfo->semi_can_hash = all_hash;
2599 3900 : sjinfo->semi_operators = semi_operators;
2600 3900 : sjinfo->semi_rhs_exprs = semi_rhs_exprs;
2601 : }
2602 :
2603 : /*
2604 : * deconstruct_distribute_oj_quals
2605 : * Adjust LEFT JOIN quals to be suitable for commuted-left-join cases,
2606 : * then push them into the joinqual lists and EquivalenceClass structures.
2607 : *
2608 : * This runs immediately after we've completed the deconstruct_distribute scan.
2609 : * jtitems contains all the JoinTreeItems (in depth-first order), and jtitem
2610 : * is one that has postponed oj_joinclauses to deal with.
2611 : */
2612 : static void
2613 31657 : deconstruct_distribute_oj_quals(PlannerInfo *root,
2614 : List *jtitems,
2615 : JoinTreeItem *jtitem)
2616 : {
2617 31657 : SpecialJoinInfo *sjinfo = jtitem->sjinfo;
2618 : Relids qualscope,
2619 : ojscope,
2620 : nonnullable_rels;
2621 :
2622 : /* Recompute syntactic and semantic scopes of this left join */
2623 31657 : qualscope = bms_union(sjinfo->syn_lefthand, sjinfo->syn_righthand);
2624 31657 : qualscope = bms_add_member(qualscope, sjinfo->ojrelid);
2625 31657 : ojscope = bms_union(sjinfo->min_lefthand, sjinfo->min_righthand);
2626 31657 : nonnullable_rels = sjinfo->syn_lefthand;
2627 :
2628 : /*
2629 : * If this join can commute with any other ones per outer-join identity 3,
2630 : * and it is the one providing the join clause with flexible semantics,
2631 : * then we have to generate variants of the join clause with different
2632 : * nullingrels labeling. Otherwise, just push out the postponed clause
2633 : * as-is.
2634 : */
2635 : Assert(sjinfo->lhs_strict); /* else we shouldn't be here */
2636 31657 : if (sjinfo->commute_above_r || sjinfo->commute_below_l)
2637 2788 : {
2638 : Relids joins_above;
2639 : Relids joins_below;
2640 : Relids incompatible_joins;
2641 : Relids joins_so_far;
2642 : List *quals;
2643 : int save_last_rinfo_serial;
2644 : ListCell *lc;
2645 :
2646 : /* Identify the outer joins this one commutes with */
2647 2788 : joins_above = sjinfo->commute_above_r;
2648 2788 : joins_below = sjinfo->commute_below_l;
2649 :
2650 : /*
2651 : * Generate qual variants with different sets of nullingrels bits.
2652 : *
2653 : * We only need bit-sets that correspond to the successively less
2654 : * deeply syntactically-nested subsets of this join and its
2655 : * commutators. That's true first because obviously only those forms
2656 : * of the Vars and PHVs could appear elsewhere in the query, and
2657 : * second because the outer join identities do not provide a way to
2658 : * re-order such joins in a way that would require different marking.
2659 : * (That is, while the current join may commute with several others,
2660 : * none of those others can commute with each other.) To visit the
2661 : * interesting joins in syntactic nesting order, we rely on the
2662 : * jtitems list to be ordered that way.
2663 : *
2664 : * We first strip out all the nullingrels bits corresponding to
2665 : * commuting joins below this one, and then successively put them back
2666 : * as we crawl up the join stack.
2667 : */
2668 2788 : quals = jtitem->oj_joinclauses;
2669 2788 : if (!bms_is_empty(joins_below))
2670 2630 : quals = (List *) remove_nulling_relids((Node *) quals,
2671 : joins_below,
2672 : NULL);
2673 :
2674 : /*
2675 : * We'll need to mark the lower versions of the quals as not safe to
2676 : * apply above not-yet-processed joins of the stack. This prevents
2677 : * possibly applying a cloned qual at the wrong join level.
2678 : */
2679 2788 : incompatible_joins = bms_union(joins_below, joins_above);
2680 2788 : incompatible_joins = bms_add_member(incompatible_joins,
2681 2788 : sjinfo->ojrelid);
2682 :
2683 : /*
2684 : * Each time we produce RestrictInfo(s) from these quals, reset the
2685 : * last_rinfo_serial counter, so that the RestrictInfos for the "same"
2686 : * qual condition get identical serial numbers. (This relies on the
2687 : * fact that we're not changing the qual list in any way that'd affect
2688 : * the number of RestrictInfos built from it.) This'll allow us to
2689 : * detect duplicative qual usage later.
2690 : */
2691 2788 : save_last_rinfo_serial = root->last_rinfo_serial;
2692 :
2693 2788 : joins_so_far = NULL;
2694 24624 : foreach(lc, jtitems)
2695 : {
2696 21836 : JoinTreeItem *otherjtitem = (JoinTreeItem *) lfirst(lc);
2697 21836 : SpecialJoinInfo *othersj = otherjtitem->sjinfo;
2698 21836 : bool below_sjinfo = false;
2699 21836 : bool above_sjinfo = false;
2700 : Relids this_qualscope;
2701 : Relids this_ojscope;
2702 : bool allow_equivalence,
2703 : has_clone,
2704 : is_clone;
2705 :
2706 21836 : if (othersj == NULL)
2707 15423 : continue; /* not an outer-join item, ignore */
2708 :
2709 6413 : if (bms_is_member(othersj->ojrelid, joins_below))
2710 : {
2711 : /* othersj commutes with sjinfo from below left */
2712 2660 : below_sjinfo = true;
2713 : }
2714 3753 : else if (othersj == sjinfo)
2715 : {
2716 : /* found our join in syntactic order */
2717 : Assert(bms_equal(joins_so_far, joins_below));
2718 : }
2719 965 : else if (bms_is_member(othersj->ojrelid, joins_above))
2720 : {
2721 : /* othersj commutes with sjinfo from above */
2722 158 : above_sjinfo = true;
2723 : }
2724 : else
2725 : {
2726 : /* othersj is not relevant, ignore */
2727 807 : continue;
2728 : }
2729 :
2730 : /* Reset serial counter for this version of the quals */
2731 5606 : root->last_rinfo_serial = save_last_rinfo_serial;
2732 :
2733 : /*
2734 : * When we are looking at joins above sjinfo, we are envisioning
2735 : * pushing sjinfo to above othersj, so add othersj's nulling bit
2736 : * before distributing the quals. We should add it to Vars coming
2737 : * from the current join's LHS: we want to transform the second
2738 : * form of OJ identity 3 to the first form, in which Vars of
2739 : * relation B will appear nulled by the syntactically-upper OJ
2740 : * within the Pbc clause, but those of relation C will not. (In
2741 : * the notation used by optimizer/README, we're converting a qual
2742 : * of the form Pbc to Pb*c.) Of course, we must also remove that
2743 : * bit from the incompatible_joins value, else we'll make a qual
2744 : * that can't be placed anywhere.
2745 : */
2746 5606 : if (above_sjinfo)
2747 : {
2748 : quals = (List *)
2749 158 : add_nulling_relids((Node *) quals,
2750 158 : sjinfo->syn_lefthand,
2751 158 : bms_make_singleton(othersj->ojrelid));
2752 158 : incompatible_joins = bms_del_member(incompatible_joins,
2753 158 : othersj->ojrelid);
2754 : }
2755 :
2756 : /* Compute qualscope and ojscope for this join level */
2757 5606 : this_qualscope = bms_union(qualscope, joins_so_far);
2758 5606 : this_ojscope = bms_union(ojscope, joins_so_far);
2759 5606 : if (above_sjinfo)
2760 : {
2761 : /* othersj is not yet in joins_so_far, but we need it */
2762 158 : this_qualscope = bms_add_member(this_qualscope,
2763 158 : othersj->ojrelid);
2764 158 : this_ojscope = bms_add_member(this_ojscope,
2765 158 : othersj->ojrelid);
2766 : /* sjinfo is in joins_so_far, and we don't want it */
2767 158 : this_ojscope = bms_del_member(this_ojscope,
2768 158 : sjinfo->ojrelid);
2769 : }
2770 :
2771 : /*
2772 : * We generate EquivalenceClasses only from the first form of the
2773 : * quals, with the fewest nullingrels bits set. An EC made from
2774 : * this version of the quals can be useful below the outer-join
2775 : * nest, whereas versions with some nullingrels bits set would not
2776 : * be. We cannot generate ECs from more than one version, or
2777 : * we'll make nonsensical conclusions that Vars with nullingrels
2778 : * bits set are equal to their versions without. Fortunately,
2779 : * such ECs wouldn't be very useful anyway, because they'd equate
2780 : * values not observable outside the join nest. (See
2781 : * optimizer/README.)
2782 : *
2783 : * The first form of the quals is also the only one marked as
2784 : * has_clone rather than is_clone.
2785 : */
2786 5606 : allow_equivalence = (joins_so_far == NULL);
2787 5606 : has_clone = allow_equivalence;
2788 5606 : is_clone = !has_clone;
2789 :
2790 5606 : distribute_quals_to_rels(root, quals,
2791 : otherjtitem,
2792 : sjinfo,
2793 : root->qual_security_level,
2794 : this_qualscope,
2795 : this_ojscope, nonnullable_rels,
2796 : bms_copy(incompatible_joins),
2797 : allow_equivalence,
2798 : has_clone,
2799 : is_clone,
2800 : NULL); /* no more postponement */
2801 :
2802 : /*
2803 : * Adjust qual nulling bits for next level up, if needed. We
2804 : * don't want to put sjinfo's own bit in at all, and if we're
2805 : * above sjinfo then we did it already. Here, we should mark all
2806 : * Vars coming from the lower join's RHS. (Again, we are
2807 : * converting a qual of the form Pbc to Pb*c, but now we are
2808 : * putting back bits that were there in the parser output and were
2809 : * temporarily stripped above.) Update incompatible_joins too.
2810 : */
2811 5606 : if (below_sjinfo)
2812 : {
2813 : quals = (List *)
2814 2660 : add_nulling_relids((Node *) quals,
2815 2660 : othersj->syn_righthand,
2816 2660 : bms_make_singleton(othersj->ojrelid));
2817 2660 : incompatible_joins = bms_del_member(incompatible_joins,
2818 2660 : othersj->ojrelid);
2819 : }
2820 :
2821 : /* ... and track joins processed so far */
2822 5606 : joins_so_far = bms_add_member(joins_so_far, othersj->ojrelid);
2823 : }
2824 : }
2825 : else
2826 : {
2827 : /* No commutation possible, just process the postponed clauses */
2828 28869 : distribute_quals_to_rels(root, jtitem->oj_joinclauses,
2829 : jtitem,
2830 : sjinfo,
2831 : root->qual_security_level,
2832 : qualscope,
2833 : ojscope, nonnullable_rels,
2834 : NULL, /* incompatible_relids */
2835 : true, /* allow_equivalence */
2836 : false, false, /* not clones */
2837 : NULL); /* no more postponement */
2838 : }
2839 31657 : }
2840 :
2841 :
2842 : /*****************************************************************************
2843 : *
2844 : * QUALIFICATIONS
2845 : *
2846 : *****************************************************************************/
2847 :
2848 : /*
2849 : * distribute_quals_to_rels
2850 : * Convenience routine to apply distribute_qual_to_rels to each element
2851 : * of an AND'ed list of clauses.
2852 : */
2853 : static void
2854 651575 : distribute_quals_to_rels(PlannerInfo *root, List *clauses,
2855 : JoinTreeItem *jtitem,
2856 : SpecialJoinInfo *sjinfo,
2857 : Index security_level,
2858 : Relids qualscope,
2859 : Relids ojscope,
2860 : Relids outerjoin_nonnullable,
2861 : Relids incompatible_relids,
2862 : bool allow_equivalence,
2863 : bool has_clone,
2864 : bool is_clone,
2865 : List **postponed_oj_qual_list)
2866 : {
2867 : ListCell *lc;
2868 :
2869 1116894 : foreach(lc, clauses)
2870 : {
2871 465319 : Node *clause = (Node *) lfirst(lc);
2872 :
2873 465319 : distribute_qual_to_rels(root, clause,
2874 : jtitem,
2875 : sjinfo,
2876 : security_level,
2877 : qualscope,
2878 : ojscope,
2879 : outerjoin_nonnullable,
2880 : incompatible_relids,
2881 : allow_equivalence,
2882 : has_clone,
2883 : is_clone,
2884 : postponed_oj_qual_list);
2885 : }
2886 651575 : }
2887 :
2888 : /*
2889 : * distribute_qual_to_rels
2890 : * Add clause information to either the baserestrictinfo or joininfo list
2891 : * (depending on whether the clause is a join) of each base relation
2892 : * mentioned in the clause. A RestrictInfo node is created and added to
2893 : * the appropriate list for each rel. Alternatively, if the clause uses a
2894 : * mergejoinable operator, enter its left- and right-side expressions into
2895 : * the query's EquivalenceClasses.
2896 : *
2897 : * In some cases, quals will be added to parent jtitems' lateral_clauses
2898 : * or to postponed_oj_qual_list instead of being processed right away.
2899 : * These will be dealt with in later calls of deconstruct_distribute.
2900 : *
2901 : * 'clause': the qual clause to be distributed
2902 : * 'jtitem': the JoinTreeItem for the containing jointree node
2903 : * 'sjinfo': join's SpecialJoinInfo (NULL for an inner join or WHERE clause)
2904 : * 'security_level': security_level to assign to the qual
2905 : * 'qualscope': set of base+OJ rels the qual's syntactic scope covers
2906 : * 'ojscope': NULL if not an outer-join qual, else the minimum set of base+OJ
2907 : * rels needed to form this join
2908 : * 'outerjoin_nonnullable': NULL if not an outer-join qual, else the set of
2909 : * base+OJ rels appearing on the outer (nonnullable) side of the join
2910 : * (for FULL JOIN this includes both sides of the join, and must in fact
2911 : * equal qualscope)
2912 : * 'incompatible_relids': the set of outer-join relid(s) that must not be
2913 : * computed below this qual. We only bother to compute this for
2914 : * "clone" quals, otherwise it can be left NULL.
2915 : * 'allow_equivalence': true if it's okay to convert clause into an
2916 : * EquivalenceClass
2917 : * 'has_clone': has_clone property to assign to the qual
2918 : * 'is_clone': is_clone property to assign to the qual
2919 : * 'postponed_oj_qual_list': if not NULL, non-degenerate outer join clauses
2920 : * should be added to this list instead of being processed (list entries
2921 : * are just the bare clauses)
2922 : *
2923 : * 'qualscope' identifies what level of JOIN the qual came from syntactically.
2924 : * 'ojscope' is needed if we decide to force the qual up to the outer-join
2925 : * level, which will be ojscope not necessarily qualscope.
2926 : *
2927 : * At the time this is called, root->join_info_list must contain entries for
2928 : * at least those special joins that are syntactically below this qual.
2929 : * (We now need that only for detection of redundant IS NULL quals.)
2930 : */
2931 : static void
2932 465319 : distribute_qual_to_rels(PlannerInfo *root, Node *clause,
2933 : JoinTreeItem *jtitem,
2934 : SpecialJoinInfo *sjinfo,
2935 : Index security_level,
2936 : Relids qualscope,
2937 : Relids ojscope,
2938 : Relids outerjoin_nonnullable,
2939 : Relids incompatible_relids,
2940 : bool allow_equivalence,
2941 : bool has_clone,
2942 : bool is_clone,
2943 : List **postponed_oj_qual_list)
2944 : {
2945 : Relids relids;
2946 : bool is_pushed_down;
2947 465319 : bool pseudoconstant = false;
2948 : bool maybe_equivalence;
2949 : bool maybe_outer_join;
2950 : RestrictInfo *restrictinfo;
2951 :
2952 : /*
2953 : * Retrieve all relids mentioned within the clause.
2954 : */
2955 465319 : relids = pull_varnos(root, clause);
2956 :
2957 : /*
2958 : * In ordinary SQL, a WHERE or JOIN/ON clause can't reference any rels
2959 : * that aren't within its syntactic scope; however, if we pulled up a
2960 : * LATERAL subquery then we might find such references in quals that have
2961 : * been pulled up. We need to treat such quals as belonging to the join
2962 : * level that includes every rel they reference. Although we could make
2963 : * pull_up_subqueries() place such quals correctly to begin with, it's
2964 : * easier to handle it here. When we find a clause that contains Vars
2965 : * outside its syntactic scope, locate the nearest parent join level that
2966 : * includes all the required rels and add the clause to that level's
2967 : * lateral_clauses list. We'll process it when we reach that join level.
2968 : */
2969 465319 : if (!bms_is_subset(relids, qualscope))
2970 : {
2971 : JoinTreeItem *pitem;
2972 :
2973 : Assert(root->hasLateralRTEs); /* shouldn't happen otherwise */
2974 : Assert(sjinfo == NULL); /* mustn't postpone past outer join */
2975 104 : for (pitem = jtitem->jti_parent; pitem; pitem = pitem->jti_parent)
2976 : {
2977 104 : if (bms_is_subset(relids, pitem->qualscope))
2978 : {
2979 99 : pitem->lateral_clauses = lappend(pitem->lateral_clauses,
2980 : clause);
2981 324593 : return;
2982 : }
2983 :
2984 : /*
2985 : * We should not be postponing any quals past an outer join. If
2986 : * this Assert fires, pull_up_subqueries() messed up.
2987 : */
2988 : Assert(pitem->sjinfo == NULL);
2989 : }
2990 0 : elog(ERROR, "failed to postpone qual containing lateral reference");
2991 : }
2992 :
2993 : /*
2994 : * If it's an outer-join clause, also check that relids is a subset of
2995 : * ojscope. (This should not fail if the syntactic scope check passed.)
2996 : */
2997 465220 : if (ojscope && !bms_is_subset(relids, ojscope))
2998 0 : elog(ERROR, "JOIN qualification cannot refer to other relations");
2999 :
3000 : /*
3001 : * If the clause is variable-free, our normal heuristic for pushing it
3002 : * down to just the mentioned rels doesn't work, because there are none.
3003 : *
3004 : * If the clause is an outer-join clause, we must force it to the OJ's
3005 : * semantic level to preserve semantics.
3006 : *
3007 : * Otherwise, when the clause contains volatile functions, we force it to
3008 : * be evaluated at its original syntactic level. This preserves the
3009 : * expected semantics.
3010 : *
3011 : * When the clause contains no volatile functions either, it is actually a
3012 : * pseudoconstant clause that will not change value during any one
3013 : * execution of the plan, and hence can be used as a one-time qual in a
3014 : * gating Result plan node. We put such a clause into the regular
3015 : * RestrictInfo lists for the moment, but eventually createplan.c will
3016 : * pull it out and make a gating Result node immediately above whatever
3017 : * plan node the pseudoconstant clause is assigned to. It's usually best
3018 : * to put a gating node as high in the plan tree as possible.
3019 : */
3020 465220 : if (bms_is_empty(relids))
3021 : {
3022 9494 : if (ojscope)
3023 : {
3024 : /* clause is attached to outer join, eval it there */
3025 316 : relids = bms_copy(ojscope);
3026 : /* mustn't use as gating qual, so don't mark pseudoconstant */
3027 : }
3028 9178 : else if (contain_volatile_functions(clause))
3029 : {
3030 : /* eval at original syntactic level */
3031 103 : relids = bms_copy(qualscope);
3032 : /* again, can't mark pseudoconstant */
3033 : }
3034 : else
3035 : {
3036 : /*
3037 : * If we are in the top-level join domain, we can push the qual to
3038 : * the top of the plan tree. Otherwise, be conservative and eval
3039 : * it at original syntactic level. (Ideally we'd push it to the
3040 : * top of the current join domain in all cases, but that causes
3041 : * problems if we later rearrange outer-join evaluation order.
3042 : * Pseudoconstant quals below the top level are a pretty odd case,
3043 : * so it's not clear that it's worth working hard on.)
3044 : */
3045 9075 : if (jtitem->jdomain == (JoinDomain *) linitial(root->join_domains))
3046 9025 : relids = bms_copy(jtitem->jdomain->jd_relids);
3047 : else
3048 50 : relids = bms_copy(qualscope);
3049 : /* mark as gating qual */
3050 9075 : pseudoconstant = true;
3051 : /* tell createplan.c to check for gating quals */
3052 9075 : root->hasPseudoConstantQuals = true;
3053 : }
3054 : }
3055 :
3056 : /*----------
3057 : * Check to see if clause application must be delayed by outer-join
3058 : * considerations.
3059 : *
3060 : * A word about is_pushed_down: we mark the qual as "pushed down" if
3061 : * it is (potentially) applicable at a level different from its original
3062 : * syntactic level. This flag is used to distinguish OUTER JOIN ON quals
3063 : * from other quals pushed down to the same joinrel. The rules are:
3064 : * WHERE quals and INNER JOIN quals: is_pushed_down = true.
3065 : * Non-degenerate OUTER JOIN quals: is_pushed_down = false.
3066 : * Degenerate OUTER JOIN quals: is_pushed_down = true.
3067 : * A "degenerate" OUTER JOIN qual is one that doesn't mention the
3068 : * non-nullable side, and hence can be pushed down into the nullable side
3069 : * without changing the join result. It is correct to treat it as a
3070 : * regular filter condition at the level where it is evaluated.
3071 : *
3072 : * Note: it is not immediately obvious that a simple boolean is enough
3073 : * for this: if for some reason we were to attach a degenerate qual to
3074 : * its original join level, it would need to be treated as an outer join
3075 : * qual there. However, this cannot happen, because all the rels the
3076 : * clause mentions must be in the outer join's min_righthand, therefore
3077 : * the join it needs must be formed before the outer join; and we always
3078 : * attach quals to the lowest level where they can be evaluated. But
3079 : * if we were ever to re-introduce a mechanism for delaying evaluation
3080 : * of "expensive" quals, this area would need work.
3081 : *
3082 : * Note: generally, use of is_pushed_down has to go through the macro
3083 : * RINFO_IS_PUSHED_DOWN, because that flag alone is not always sufficient
3084 : * to tell whether a clause must be treated as pushed-down in context.
3085 : * This seems like another reason why it should perhaps be rethought.
3086 : *----------
3087 : */
3088 465220 : if (bms_overlap(relids, outerjoin_nonnullable))
3089 : {
3090 : /*
3091 : * The qual is attached to an outer join and mentions (some of the)
3092 : * rels on the nonnullable side, so it's not degenerate. If the
3093 : * caller wants to postpone handling such clauses, just add it to
3094 : * postponed_oj_qual_list and return. (The work we've done up to here
3095 : * will have to be redone later, but there's not much of it.)
3096 : */
3097 81339 : if (postponed_oj_qual_list != NULL)
3098 : {
3099 35131 : *postponed_oj_qual_list = lappend(*postponed_oj_qual_list, clause);
3100 35131 : return;
3101 : }
3102 :
3103 : /*
3104 : * We can't use such a clause to deduce equivalence (the left and
3105 : * right sides might be unequal above the join because one of them has
3106 : * gone to NULL) ... but we might be able to use it for more limited
3107 : * deductions, if it is mergejoinable. So consider adding it to the
3108 : * lists of set-aside outer-join clauses.
3109 : */
3110 46208 : is_pushed_down = false;
3111 46208 : maybe_equivalence = false;
3112 46208 : maybe_outer_join = true;
3113 :
3114 : /*
3115 : * Now force the qual to be evaluated exactly at the level of joining
3116 : * corresponding to the outer join. We cannot let it get pushed down
3117 : * into the nonnullable side, since then we'd produce no output rows,
3118 : * rather than the intended single null-extended row, for any
3119 : * nonnullable-side rows failing the qual.
3120 : */
3121 : Assert(ojscope);
3122 46208 : relids = ojscope;
3123 : Assert(!pseudoconstant);
3124 : }
3125 : else
3126 : {
3127 : /*
3128 : * Normal qual clause or degenerate outer-join clause. Either way, we
3129 : * can mark it as pushed-down.
3130 : */
3131 383881 : is_pushed_down = true;
3132 :
3133 : /*
3134 : * It's possible that this is an IS NULL clause that's redundant with
3135 : * a lower antijoin; if so we can just discard it. We need not test
3136 : * in any of the other cases, because this will only be possible for
3137 : * pushed-down clauses.
3138 : */
3139 383881 : if (check_redundant_nullability_qual(root, clause))
3140 986 : return;
3141 :
3142 : /* Feed qual to the equivalence machinery, if allowed by caller */
3143 382895 : maybe_equivalence = allow_equivalence;
3144 :
3145 : /*
3146 : * Since it doesn't mention the LHS, it's certainly not useful as a
3147 : * set-aside OJ clause, even if it's in an OJ.
3148 : */
3149 382895 : maybe_outer_join = false;
3150 : }
3151 :
3152 : /*
3153 : * Build the RestrictInfo node itself.
3154 : */
3155 429103 : restrictinfo = make_restrictinfo(root,
3156 : (Expr *) clause,
3157 : is_pushed_down,
3158 : has_clone,
3159 : is_clone,
3160 : pseudoconstant,
3161 : security_level,
3162 : relids,
3163 : incompatible_relids,
3164 : outerjoin_nonnullable);
3165 :
3166 : /*
3167 : * If it's a join clause, add vars used in the clause to targetlists of
3168 : * their relations, so that they will be emitted by the plan nodes that
3169 : * scan those relations (else they won't be available at the join node!).
3170 : *
3171 : * Normally we mark the vars as needed at the join identified by "relids".
3172 : * However, if this is a clone clause then ignore the outer-join relids in
3173 : * that set. Otherwise, vars appearing in a cloned clause would end up
3174 : * marked as having to propagate to the highest one of the commuting
3175 : * joins, which would often be an overestimate. For such clauses, correct
3176 : * var propagation is ensured by making ojscope include input rels from
3177 : * both sides of the join.
3178 : *
3179 : * See also rebuild_joinclause_attr_needed, which has to partially repeat
3180 : * this work after removal of an outer join.
3181 : *
3182 : * Note: if the clause gets absorbed into an EquivalenceClass then this
3183 : * may be unnecessary, but for now we have to do it to cover the case
3184 : * where the EC becomes ec_broken and we end up reinserting the original
3185 : * clauses into the plan.
3186 : */
3187 429103 : if (bms_membership(relids) == BMS_MULTIPLE)
3188 : {
3189 133963 : List *vars = pull_var_clause(clause,
3190 : PVC_RECURSE_AGGREGATES |
3191 : PVC_RECURSE_WINDOWFUNCS |
3192 : PVC_INCLUDE_PLACEHOLDERS);
3193 : Relids where_needed;
3194 :
3195 133963 : if (is_clone)
3196 3112 : where_needed = bms_intersect(relids, root->all_baserels);
3197 : else
3198 130851 : where_needed = relids;
3199 133963 : add_vars_to_targetlist(root, vars, where_needed);
3200 133963 : list_free(vars);
3201 : }
3202 :
3203 : /*
3204 : * We check "mergejoinability" of every clause, not only join clauses,
3205 : * because we want to know about equivalences between vars of the same
3206 : * relation, or between vars and consts.
3207 : */
3208 429103 : check_mergejoinable(restrictinfo);
3209 :
3210 : /*
3211 : * If it is a true equivalence clause, send it to the EquivalenceClass
3212 : * machinery. We do *not* attach it directly to any restriction or join
3213 : * lists. The EC code will propagate it to the appropriate places later.
3214 : *
3215 : * If the clause has a mergejoinable operator, yet isn't an equivalence
3216 : * because it is an outer-join clause, the EC code may still be able to do
3217 : * something with it. We add it to appropriate lists for further
3218 : * consideration later. Specifically:
3219 : *
3220 : * If it is a left or right outer-join qualification that relates the two
3221 : * sides of the outer join (no funny business like leftvar1 = leftvar2 +
3222 : * rightvar), we add it to root->left_join_clauses or
3223 : * root->right_join_clauses according to which side the nonnullable
3224 : * variable appears on.
3225 : *
3226 : * If it is a full outer-join qualification, we add it to
3227 : * root->full_join_clauses. (Ideally we'd discard cases that aren't
3228 : * leftvar = rightvar, as we do for left/right joins, but this routine
3229 : * doesn't have the info needed to do that; and the current usage of the
3230 : * full_join_clauses list doesn't require that, so it's not currently
3231 : * worth complicating this routine's API to make it possible.)
3232 : *
3233 : * If none of the above hold, pass it off to
3234 : * distribute_restrictinfo_to_rels().
3235 : *
3236 : * In all cases, it's important to initialize the left_ec and right_ec
3237 : * fields of a mergejoinable clause, so that all possibly mergejoinable
3238 : * expressions have representations in EquivalenceClasses. If
3239 : * process_equivalence is successful, it will take care of that;
3240 : * otherwise, we have to call initialize_mergeclause_eclasses to do it.
3241 : */
3242 429103 : if (restrictinfo->mergeopfamilies)
3243 : {
3244 289293 : if (maybe_equivalence)
3245 : {
3246 244442 : if (process_equivalence(root, &restrictinfo, jtitem->jdomain))
3247 244225 : return;
3248 : /* EC rejected it, so set left_ec/right_ec the hard way ... */
3249 217 : if (restrictinfo->mergeopfamilies) /* EC might have changed this */
3250 172 : initialize_mergeclause_eclasses(root, restrictinfo);
3251 : /* ... and fall through to distribute_restrictinfo_to_rels */
3252 : }
3253 44851 : else if (maybe_outer_join && restrictinfo->can_join)
3254 : {
3255 : /* we need to set up left_ec/right_ec the hard way */
3256 44315 : initialize_mergeclause_eclasses(root, restrictinfo);
3257 : /* now see if it should go to any outer-join lists */
3258 : Assert(sjinfo != NULL);
3259 44315 : if (bms_is_subset(restrictinfo->left_relids,
3260 21457 : outerjoin_nonnullable) &&
3261 21457 : !bms_overlap(restrictinfo->right_relids,
3262 : outerjoin_nonnullable))
3263 : {
3264 : /* we have outervar = innervar */
3265 20423 : OuterJoinClauseInfo *ojcinfo = makeNode(OuterJoinClauseInfo);
3266 :
3267 20423 : ojcinfo->rinfo = restrictinfo;
3268 20423 : ojcinfo->sjinfo = sjinfo;
3269 20423 : root->left_join_clauses = lappend(root->left_join_clauses,
3270 : ojcinfo);
3271 20423 : return;
3272 : }
3273 23892 : if (bms_is_subset(restrictinfo->right_relids,
3274 23759 : outerjoin_nonnullable) &&
3275 23759 : !bms_overlap(restrictinfo->left_relids,
3276 : outerjoin_nonnullable))
3277 : {
3278 : /* we have innervar = outervar */
3279 22725 : OuterJoinClauseInfo *ojcinfo = makeNode(OuterJoinClauseInfo);
3280 :
3281 22725 : ojcinfo->rinfo = restrictinfo;
3282 22725 : ojcinfo->sjinfo = sjinfo;
3283 22725 : root->right_join_clauses = lappend(root->right_join_clauses,
3284 : ojcinfo);
3285 22725 : return;
3286 : }
3287 1167 : if (sjinfo->jointype == JOIN_FULL)
3288 : {
3289 : /* FULL JOIN (above tests cannot match in this case) */
3290 1004 : OuterJoinClauseInfo *ojcinfo = makeNode(OuterJoinClauseInfo);
3291 :
3292 1004 : ojcinfo->rinfo = restrictinfo;
3293 1004 : ojcinfo->sjinfo = sjinfo;
3294 1004 : root->full_join_clauses = lappend(root->full_join_clauses,
3295 : ojcinfo);
3296 1004 : return;
3297 : }
3298 : /* nope, so fall through to distribute_restrictinfo_to_rels */
3299 : }
3300 : else
3301 : {
3302 : /* we still need to set up left_ec/right_ec */
3303 536 : initialize_mergeclause_eclasses(root, restrictinfo);
3304 : }
3305 : }
3306 :
3307 : /* No EC special case applies, so push it into the clause lists */
3308 140726 : distribute_restrictinfo_to_rels(root, restrictinfo);
3309 : }
3310 :
3311 : /*
3312 : * check_redundant_nullability_qual
3313 : * Check to see if the qual is an IS NULL qual that is redundant with
3314 : * a lower JOIN_ANTI join.
3315 : *
3316 : * We want to suppress redundant IS NULL quals, not so much to save cycles
3317 : * as to avoid generating bogus selectivity estimates for them. So if
3318 : * redundancy is detected here, distribute_qual_to_rels() just throws away
3319 : * the qual.
3320 : */
3321 : static bool
3322 383881 : check_redundant_nullability_qual(PlannerInfo *root, Node *clause)
3323 : {
3324 : Var *forced_null_var;
3325 : ListCell *lc;
3326 :
3327 : /* Check for IS NULL, and identify the Var forced to NULL */
3328 383881 : forced_null_var = find_forced_null_var(clause);
3329 383881 : if (forced_null_var == NULL)
3330 381589 : return false;
3331 :
3332 : /*
3333 : * If the Var comes from the nullable side of a lower antijoin, the IS
3334 : * NULL condition is necessarily true. If it's not nulled by anything,
3335 : * there is no point in searching the join_info_list. Otherwise, we need
3336 : * to find out whether the nulling rel is an antijoin.
3337 : */
3338 2292 : if (forced_null_var->varnullingrels == NULL)
3339 1237 : return false;
3340 :
3341 1165 : foreach(lc, root->join_info_list)
3342 : {
3343 1096 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
3344 :
3345 : /*
3346 : * This test will not succeed if sjinfo->ojrelid is zero, which is
3347 : * possible for an antijoin that was converted from a semijoin; but in
3348 : * such a case the Var couldn't have come from its nullable side.
3349 : */
3350 2082 : if (sjinfo->jointype == JOIN_ANTI && sjinfo->ojrelid != 0 &&
3351 986 : bms_is_member(sjinfo->ojrelid, forced_null_var->varnullingrels))
3352 986 : return true;
3353 : }
3354 :
3355 69 : return false;
3356 : }
3357 :
3358 : /*
3359 : * add_base_clause_to_rel
3360 : * Add 'restrictinfo' as a baserestrictinfo to the base relation denoted
3361 : * by 'relid'. We offer some simple prechecks to try to determine if the
3362 : * qual is always true, in which case we ignore it rather than add it.
3363 : * If we detect the qual is always false, we replace it with
3364 : * constant-FALSE.
3365 : */
3366 : static void
3367 307755 : add_base_clause_to_rel(PlannerInfo *root, Index relid,
3368 : RestrictInfo *restrictinfo)
3369 : {
3370 307755 : RelOptInfo *rel = find_base_rel(root, relid);
3371 307755 : RangeTblEntry *rte = root->simple_rte_array[relid];
3372 :
3373 : Assert(bms_membership(restrictinfo->required_relids) == BMS_SINGLETON);
3374 :
3375 : /*
3376 : * For inheritance parent tables, we must always record the RestrictInfo
3377 : * in baserestrictinfo as is. If we were to transform or skip adding it,
3378 : * then the original wouldn't be available in apply_child_basequals. Since
3379 : * there are two RangeTblEntries for inheritance parents, one with
3380 : * inh==true and the other with inh==false, we're still able to apply this
3381 : * optimization to the inh==false one. The inh==true one is what
3382 : * apply_child_basequals() sees, whereas the inh==false one is what's used
3383 : * for the scan node in the final plan.
3384 : *
3385 : * We make an exception to this for partitioned tables. For these, we
3386 : * always apply the constant-TRUE and constant-FALSE transformations. A
3387 : * qual which is either of these for a partitioned table must also be that
3388 : * for all of its child partitions.
3389 : */
3390 307755 : if (!rte->inh || rte->relkind == RELKIND_PARTITIONED_TABLE)
3391 : {
3392 : /* Don't add the clause if it is always true */
3393 306039 : if (restriction_is_always_true(root, restrictinfo))
3394 352 : return;
3395 :
3396 : /*
3397 : * Substitute the origin qual with constant-FALSE if it is provably
3398 : * always false.
3399 : *
3400 : * Note that we need to keep the same rinfo_serial, since it is in
3401 : * practice the same condition. We also need to reset the
3402 : * last_rinfo_serial counter, which is essential to ensure that the
3403 : * RestrictInfos for the "same" qual condition get identical serial
3404 : * numbers (see deconstruct_distribute_oj_quals).
3405 : */
3406 305687 : if (restriction_is_always_false(root, restrictinfo))
3407 : {
3408 0 : int save_rinfo_serial = restrictinfo->rinfo_serial;
3409 0 : int save_last_rinfo_serial = root->last_rinfo_serial;
3410 :
3411 0 : restrictinfo = make_restrictinfo(root,
3412 0 : (Expr *) makeBoolConst(false, false),
3413 0 : restrictinfo->is_pushed_down,
3414 0 : restrictinfo->has_clone,
3415 0 : restrictinfo->is_clone,
3416 0 : restrictinfo->pseudoconstant,
3417 : 0, /* security_level */
3418 : restrictinfo->required_relids,
3419 : restrictinfo->incompatible_relids,
3420 : restrictinfo->outer_relids);
3421 0 : restrictinfo->rinfo_serial = save_rinfo_serial;
3422 0 : root->last_rinfo_serial = save_last_rinfo_serial;
3423 : }
3424 : }
3425 :
3426 : /* Add clause to rel's restriction list */
3427 307403 : rel->baserestrictinfo = lappend(rel->baserestrictinfo, restrictinfo);
3428 :
3429 : /* Update security level info */
3430 307403 : rel->baserestrict_min_security = Min(rel->baserestrict_min_security,
3431 : restrictinfo->security_level);
3432 : }
3433 :
3434 : /*
3435 : * restriction_is_always_true
3436 : * Check to see if the RestrictInfo is always true.
3437 : *
3438 : * Currently we only check for NullTest quals and OR clauses that include
3439 : * NullTest quals. We may extend it in the future.
3440 : */
3441 : bool
3442 379125 : restriction_is_always_true(PlannerInfo *root,
3443 : RestrictInfo *restrictinfo)
3444 : {
3445 : /*
3446 : * For a clone clause, we don't have a reliable way to determine if the
3447 : * input expression of a NullTest is non-nullable: nullingrel bits in
3448 : * clone clauses may not reflect reality, so we dare not draw conclusions
3449 : * from clones about whether Vars are guaranteed not-null.
3450 : */
3451 379125 : if (restrictinfo->has_clone || restrictinfo->is_clone)
3452 6204 : return false;
3453 :
3454 : /* Check for NullTest qual */
3455 372921 : if (IsA(restrictinfo->clause, NullTest))
3456 : {
3457 7561 : NullTest *nulltest = (NullTest *) restrictinfo->clause;
3458 :
3459 : /* is this NullTest an IS_NOT_NULL qual? */
3460 7561 : if (nulltest->nulltesttype != IS_NOT_NULL)
3461 1731 : return false;
3462 :
3463 : /*
3464 : * Empty rows can appear NULL in some contexts and NOT NULL in others,
3465 : * so avoid this optimization for row expressions.
3466 : */
3467 5830 : if (nulltest->argisrow)
3468 118 : return false;
3469 :
3470 5712 : return expr_is_nonnullable(root, nulltest->arg, NOTNULL_SOURCE_RELOPT);
3471 : }
3472 :
3473 : /* If it's an OR, check its sub-clauses */
3474 365360 : if (restriction_is_or_clause(restrictinfo))
3475 : {
3476 : ListCell *lc;
3477 :
3478 : Assert(is_orclause(restrictinfo->orclause));
3479 :
3480 : /*
3481 : * if any of the given OR branches is provably always true then the
3482 : * entire condition is true.
3483 : */
3484 24875 : foreach(lc, ((BoolExpr *) restrictinfo->orclause)->args)
3485 : {
3486 17375 : Node *orarg = (Node *) lfirst(lc);
3487 :
3488 17375 : if (!IsA(orarg, RestrictInfo))
3489 1466 : continue;
3490 :
3491 15909 : if (restriction_is_always_true(root, (RestrictInfo *) orarg))
3492 0 : return true;
3493 : }
3494 : }
3495 :
3496 365360 : return false;
3497 : }
3498 :
3499 : /*
3500 : * restriction_is_always_false
3501 : * Check to see if the RestrictInfo is always false.
3502 : *
3503 : * Currently we only check for NullTest quals and OR clauses that include
3504 : * NullTest quals. We may extend it in the future.
3505 : */
3506 : bool
3507 369724 : restriction_is_always_false(PlannerInfo *root,
3508 : RestrictInfo *restrictinfo)
3509 : {
3510 : /*
3511 : * For a clone clause, we don't have a reliable way to determine if the
3512 : * input expression of a NullTest is non-nullable: nullingrel bits in
3513 : * clone clauses may not reflect reality, so we dare not draw conclusions
3514 : * from clones about whether Vars are guaranteed not-null.
3515 : */
3516 369724 : if (restrictinfo->has_clone || restrictinfo->is_clone)
3517 6204 : return false;
3518 :
3519 : /* Check for NullTest qual */
3520 363520 : if (IsA(restrictinfo->clause, NullTest))
3521 : {
3522 6525 : NullTest *nulltest = (NullTest *) restrictinfo->clause;
3523 :
3524 : /* is this NullTest an IS_NULL qual? */
3525 6525 : if (nulltest->nulltesttype != IS_NULL)
3526 5007 : return false;
3527 :
3528 : /*
3529 : * Empty rows can appear NULL in some contexts and NOT NULL in others,
3530 : * so avoid this optimization for row expressions.
3531 : */
3532 1518 : if (nulltest->argisrow)
3533 88 : return false;
3534 :
3535 1430 : return expr_is_nonnullable(root, nulltest->arg, NOTNULL_SOURCE_RELOPT);
3536 : }
3537 :
3538 : /* If it's an OR, check its sub-clauses */
3539 356995 : if (restriction_is_or_clause(restrictinfo))
3540 : {
3541 : ListCell *lc;
3542 :
3543 : Assert(is_orclause(restrictinfo->orclause));
3544 :
3545 : /*
3546 : * Currently, when processing OR expressions, we only return true when
3547 : * all of the OR branches are always false. This could perhaps be
3548 : * expanded to remove OR branches that are provably false. This may
3549 : * be a useful thing to do as it could result in the OR being left
3550 : * with a single arg. That's useful as it would allow the OR
3551 : * condition to be replaced with its single argument which may allow
3552 : * use of an index for faster filtering on the remaining condition.
3553 : */
3554 7500 : foreach(lc, ((BoolExpr *) restrictinfo->orclause)->args)
3555 : {
3556 7500 : Node *orarg = (Node *) lfirst(lc);
3557 :
3558 7500 : if (!IsA(orarg, RestrictInfo) ||
3559 6860 : !restriction_is_always_false(root, (RestrictInfo *) orarg))
3560 7500 : return false;
3561 : }
3562 0 : return true;
3563 : }
3564 :
3565 349495 : return false;
3566 : }
3567 :
3568 : /*
3569 : * distribute_restrictinfo_to_rels
3570 : * Push a completed RestrictInfo into the proper restriction or join
3571 : * clause list(s).
3572 : *
3573 : * This is the last step of distribute_qual_to_rels() for ordinary qual
3574 : * clauses. Clauses that are interesting for equivalence-class processing
3575 : * are diverted to the EC machinery, but may ultimately get fed back here.
3576 : */
3577 : void
3578 364932 : distribute_restrictinfo_to_rels(PlannerInfo *root,
3579 : RestrictInfo *restrictinfo)
3580 : {
3581 364932 : Relids relids = restrictinfo->required_relids;
3582 :
3583 364932 : if (!bms_is_empty(relids))
3584 : {
3585 : int relid;
3586 :
3587 364932 : if (bms_get_singleton_member(relids, &relid))
3588 : {
3589 : /*
3590 : * There is only one relation participating in the clause, so it
3591 : * is a restriction clause for that relation.
3592 : */
3593 307755 : add_base_clause_to_rel(root, relid, restrictinfo);
3594 : }
3595 : else
3596 : {
3597 : /*
3598 : * The clause is a join clause, since there is more than one rel
3599 : * in its relid set.
3600 : */
3601 :
3602 : /*
3603 : * Check for hashjoinable operators. (We don't bother setting the
3604 : * hashjoin info except in true join clauses.)
3605 : */
3606 57177 : check_hashjoinable(restrictinfo);
3607 :
3608 : /*
3609 : * Likewise, check if the clause is suitable to be used with a
3610 : * Memoize node to cache inner tuples during a parameterized
3611 : * nested loop.
3612 : */
3613 57177 : check_memoizable(restrictinfo);
3614 :
3615 : /*
3616 : * Add clause to the join lists of all the relevant relations.
3617 : */
3618 57177 : add_join_clause_to_rels(root, restrictinfo, relids);
3619 : }
3620 : }
3621 : else
3622 : {
3623 : /*
3624 : * clause references no rels, and therefore we have no place to attach
3625 : * it. Shouldn't get here if callers are working properly.
3626 : */
3627 0 : elog(ERROR, "cannot cope with variable-free clause");
3628 : }
3629 364932 : }
3630 :
3631 : /*
3632 : * process_implied_equality
3633 : * Create a restrictinfo item that says "item1 op item2", and push it
3634 : * into the appropriate lists. (In practice opno is always a btree
3635 : * equality operator.)
3636 : *
3637 : * "qualscope" is the nominal syntactic level to impute to the restrictinfo.
3638 : * This must contain at least all the rels used in the expressions, but it
3639 : * is used only to set the qual application level when both exprs are
3640 : * variable-free. (Hence, it should usually match the join domain in which
3641 : * the clause applies.) Otherwise the qual is applied at the lowest join
3642 : * level that provides all its variables.
3643 : *
3644 : * "security_level" is the security level to assign to the new restrictinfo.
3645 : *
3646 : * "both_const" indicates whether both items are known pseudo-constant;
3647 : * in this case it is worth applying eval_const_expressions() in case we
3648 : * can produce constant TRUE or constant FALSE. (Otherwise it's not,
3649 : * because the expressions went through eval_const_expressions already.)
3650 : *
3651 : * Returns the generated RestrictInfo, if any. The result will be NULL
3652 : * if both_const is true and we successfully reduced the clause to
3653 : * constant TRUE.
3654 : *
3655 : * Note: this function will copy item1 and item2, but it is caller's
3656 : * responsibility to make sure that the Relids parameters are fresh copies
3657 : * not shared with other uses.
3658 : *
3659 : * Note: we do not do initialize_mergeclause_eclasses() here. It is
3660 : * caller's responsibility that left_ec/right_ec be set as necessary.
3661 : */
3662 : RestrictInfo *
3663 25534 : process_implied_equality(PlannerInfo *root,
3664 : Oid opno,
3665 : Oid collation,
3666 : Expr *item1,
3667 : Expr *item2,
3668 : Relids qualscope,
3669 : Index security_level,
3670 : bool both_const)
3671 : {
3672 : RestrictInfo *restrictinfo;
3673 : Node *clause;
3674 : Relids relids;
3675 25534 : bool pseudoconstant = false;
3676 :
3677 : /*
3678 : * Build the new clause. Copy to ensure it shares no substructure with
3679 : * original (this is necessary in case there are subselects in there...)
3680 : */
3681 25534 : clause = (Node *) make_opclause(opno,
3682 : BOOLOID, /* opresulttype */
3683 : false, /* opretset */
3684 25534 : copyObject(item1),
3685 25534 : copyObject(item2),
3686 : InvalidOid,
3687 : collation);
3688 :
3689 : /* If both constant, try to reduce to a boolean constant. */
3690 25534 : if (both_const)
3691 : {
3692 110 : clause = eval_const_expressions(root, clause);
3693 :
3694 : /* If we produced const TRUE, just drop the clause */
3695 110 : if (clause && IsA(clause, Const))
3696 : {
3697 105 : Const *cclause = (Const *) clause;
3698 :
3699 : Assert(cclause->consttype == BOOLOID);
3700 105 : if (!cclause->constisnull && DatumGetBool(cclause->constvalue))
3701 0 : return NULL;
3702 : }
3703 : }
3704 :
3705 : /*
3706 : * The rest of this is a very cut-down version of distribute_qual_to_rels.
3707 : * We can skip most of the work therein, but there are a couple of special
3708 : * cases we still have to handle.
3709 : *
3710 : * Retrieve all relids mentioned within the possibly-simplified clause.
3711 : */
3712 25534 : relids = pull_varnos(root, clause);
3713 : Assert(bms_is_subset(relids, qualscope));
3714 :
3715 : /*
3716 : * If the clause is variable-free, our normal heuristic for pushing it
3717 : * down to just the mentioned rels doesn't work, because there are none.
3718 : * Apply it as a gating qual at the appropriate level (see comments for
3719 : * get_join_domain_min_rels).
3720 : */
3721 25534 : if (bms_is_empty(relids))
3722 : {
3723 : /* eval at join domain's safe level */
3724 110 : relids = get_join_domain_min_rels(root, qualscope);
3725 : /* mark as gating qual */
3726 110 : pseudoconstant = true;
3727 : /* tell createplan.c to check for gating quals */
3728 110 : root->hasPseudoConstantQuals = true;
3729 : }
3730 :
3731 : /*
3732 : * Build the RestrictInfo node itself.
3733 : */
3734 25534 : restrictinfo = make_restrictinfo(root,
3735 : (Expr *) clause,
3736 : true, /* is_pushed_down */
3737 : false, /* !has_clone */
3738 : false, /* !is_clone */
3739 : pseudoconstant,
3740 : security_level,
3741 : relids,
3742 : NULL, /* incompatible_relids */
3743 : NULL); /* outer_relids */
3744 :
3745 : /*
3746 : * If it's a join clause, add vars used in the clause to targetlists of
3747 : * their relations, so that they will be emitted by the plan nodes that
3748 : * scan those relations (else they won't be available at the join node!).
3749 : *
3750 : * Typically, we'd have already done this when the component expressions
3751 : * were first seen by distribute_qual_to_rels; but it is possible that
3752 : * some of the Vars could have missed having that done because they only
3753 : * appeared in single-relation clauses originally. So do it here for
3754 : * safety.
3755 : *
3756 : * See also rebuild_joinclause_attr_needed, which has to partially repeat
3757 : * this work after removal of an outer join. (Since we will put this
3758 : * clause into the joininfo lists, that function needn't do any extra work
3759 : * to find it.)
3760 : */
3761 25534 : if (bms_membership(relids) == BMS_MULTIPLE)
3762 : {
3763 50 : List *vars = pull_var_clause(clause,
3764 : PVC_RECURSE_AGGREGATES |
3765 : PVC_RECURSE_WINDOWFUNCS |
3766 : PVC_INCLUDE_PLACEHOLDERS);
3767 :
3768 50 : add_vars_to_targetlist(root, vars, relids);
3769 50 : list_free(vars);
3770 : }
3771 :
3772 : /*
3773 : * Check mergejoinability. This will usually succeed, since the op came
3774 : * from an EquivalenceClass; but we could have reduced the original clause
3775 : * to a constant.
3776 : */
3777 25534 : check_mergejoinable(restrictinfo);
3778 :
3779 : /*
3780 : * Note we don't do initialize_mergeclause_eclasses(); the caller can
3781 : * handle that much more cheaply than we can. It's okay to call
3782 : * distribute_restrictinfo_to_rels() before that happens.
3783 : */
3784 :
3785 : /*
3786 : * Push the new clause into all the appropriate restrictinfo lists.
3787 : */
3788 25534 : distribute_restrictinfo_to_rels(root, restrictinfo);
3789 :
3790 25534 : return restrictinfo;
3791 : }
3792 :
3793 : /*
3794 : * build_implied_join_equality --- build a RestrictInfo for a derived equality
3795 : *
3796 : * This overlaps the functionality of process_implied_equality(), but we
3797 : * must not push the RestrictInfo into the joininfo tree.
3798 : *
3799 : * Note: this function will copy item1 and item2, but it is caller's
3800 : * responsibility to make sure that the Relids parameters are fresh copies
3801 : * not shared with other uses.
3802 : *
3803 : * Note: we do not do initialize_mergeclause_eclasses() here. It is
3804 : * caller's responsibility that left_ec/right_ec be set as necessary.
3805 : */
3806 : RestrictInfo *
3807 73984 : build_implied_join_equality(PlannerInfo *root,
3808 : Oid opno,
3809 : Oid collation,
3810 : Expr *item1,
3811 : Expr *item2,
3812 : Relids qualscope,
3813 : Index security_level)
3814 : {
3815 : RestrictInfo *restrictinfo;
3816 : Expr *clause;
3817 :
3818 : /*
3819 : * Build the new clause. Copy to ensure it shares no substructure with
3820 : * original (this is necessary in case there are subselects in there...)
3821 : */
3822 73984 : clause = make_opclause(opno,
3823 : BOOLOID, /* opresulttype */
3824 : false, /* opretset */
3825 73984 : copyObject(item1),
3826 73984 : copyObject(item2),
3827 : InvalidOid,
3828 : collation);
3829 :
3830 : /*
3831 : * Build the RestrictInfo node itself.
3832 : */
3833 73984 : restrictinfo = make_restrictinfo(root,
3834 : clause,
3835 : true, /* is_pushed_down */
3836 : false, /* !has_clone */
3837 : false, /* !is_clone */
3838 : false, /* pseudoconstant */
3839 : security_level, /* security_level */
3840 : qualscope, /* required_relids */
3841 : NULL, /* incompatible_relids */
3842 : NULL); /* outer_relids */
3843 :
3844 : /* Set mergejoinability/hashjoinability flags */
3845 73984 : check_mergejoinable(restrictinfo);
3846 73984 : check_hashjoinable(restrictinfo);
3847 73984 : check_memoizable(restrictinfo);
3848 :
3849 73984 : return restrictinfo;
3850 : }
3851 :
3852 : /*
3853 : * get_join_domain_min_rels
3854 : * Identify the appropriate join level for derived quals belonging
3855 : * to the join domain with the given relids.
3856 : *
3857 : * When we derive a pseudoconstant (Var-free) clause from an EquivalenceClass,
3858 : * we'd ideally apply the clause at the top level of the EC's join domain.
3859 : * However, if there are any outer joins inside that domain that get commuted
3860 : * with joins outside it, that leads to not finding a correct place to apply
3861 : * the clause. Instead, remove any lower outer joins from the relid set,
3862 : * and apply the clause to just the remaining rels. This still results in a
3863 : * correct answer, since if the clause produces FALSE then the LHS of these
3864 : * joins will be empty leading to an empty join result.
3865 : *
3866 : * However, there's no need to remove outer joins if this is the top-level
3867 : * join domain of the query, since then there's nothing else to commute with.
3868 : *
3869 : * Note: it's tempting to use this in distribute_qual_to_rels where it's
3870 : * dealing with pseudoconstant quals; but we can't because the necessary
3871 : * SpecialJoinInfos aren't all formed at that point.
3872 : *
3873 : * The result is always freshly palloc'd; we do not modify domain_relids.
3874 : */
3875 : static Relids
3876 110 : get_join_domain_min_rels(PlannerInfo *root, Relids domain_relids)
3877 : {
3878 110 : Relids result = bms_copy(domain_relids);
3879 : ListCell *lc;
3880 :
3881 : /* Top-level join domain? */
3882 110 : if (bms_equal(result, root->all_query_rels))
3883 55 : return result;
3884 :
3885 : /* Nope, look for lower outer joins that could potentially commute out */
3886 115 : foreach(lc, root->join_info_list)
3887 : {
3888 60 : SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
3889 :
3890 120 : if (sjinfo->jointype == JOIN_LEFT &&
3891 60 : bms_is_member(sjinfo->ojrelid, result))
3892 : {
3893 5 : result = bms_del_member(result, sjinfo->ojrelid);
3894 5 : result = bms_del_members(result, sjinfo->syn_righthand);
3895 : }
3896 : }
3897 55 : return result;
3898 : }
3899 :
3900 :
3901 : /*
3902 : * rebuild_joinclause_attr_needed
3903 : * Put back attr_needed bits for Vars/PHVs needed for join clauses.
3904 : *
3905 : * This is used to rebuild attr_needed/ph_needed sets after removal of a
3906 : * useless outer join. It should match what distribute_qual_to_rels did,
3907 : * except that we call add_vars_to_attr_needed not add_vars_to_targetlist.
3908 : */
3909 : void
3910 9043 : rebuild_joinclause_attr_needed(PlannerInfo *root)
3911 : {
3912 : /*
3913 : * We must examine all join clauses, but there's no value in processing
3914 : * any join clause more than once. So it's slightly annoying that we have
3915 : * to find them via the per-base-relation joininfo lists. Avoid duplicate
3916 : * processing by tracking the rinfo_serial numbers of join clauses we've
3917 : * already seen. (This doesn't work for is_clone clauses, so we must
3918 : * waste effort on them.)
3919 : */
3920 9043 : Bitmapset *seen_serials = NULL;
3921 : Index rti;
3922 :
3923 : /* Scan all baserels for join clauses */
3924 59635 : for (rti = 1; rti < root->simple_rel_array_size; rti++)
3925 : {
3926 50592 : RelOptInfo *brel = root->simple_rel_array[rti];
3927 : ListCell *lc;
3928 :
3929 50592 : if (brel == NULL)
3930 33612 : continue;
3931 16980 : if (brel->reloptkind != RELOPT_BASEREL)
3932 0 : continue;
3933 :
3934 25553 : foreach(lc, brel->joininfo)
3935 : {
3936 8573 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3937 8573 : Relids relids = rinfo->required_relids;
3938 :
3939 8573 : if (!rinfo->is_clone) /* else serial number is not unique */
3940 : {
3941 8503 : if (bms_is_member(rinfo->rinfo_serial, seen_serials))
3942 4555 : continue; /* saw it already */
3943 3948 : seen_serials = bms_add_member(seen_serials,
3944 : rinfo->rinfo_serial);
3945 : }
3946 :
3947 4018 : if (bms_membership(relids) == BMS_MULTIPLE)
3948 : {
3949 4018 : List *vars = pull_var_clause((Node *) rinfo->clause,
3950 : PVC_RECURSE_AGGREGATES |
3951 : PVC_RECURSE_WINDOWFUNCS |
3952 : PVC_INCLUDE_PLACEHOLDERS);
3953 : Relids where_needed;
3954 :
3955 4018 : if (rinfo->is_clone)
3956 70 : where_needed = bms_intersect(relids, root->all_baserels);
3957 : else
3958 3948 : where_needed = relids;
3959 4018 : add_vars_to_attr_needed(root, vars, where_needed);
3960 4018 : list_free(vars);
3961 : }
3962 : }
3963 : }
3964 9043 : }
3965 :
3966 :
3967 : /*
3968 : * match_foreign_keys_to_quals
3969 : * Match foreign-key constraints to equivalence classes and join quals
3970 : *
3971 : * The idea here is to see which query join conditions match equality
3972 : * constraints of a foreign-key relationship. For such join conditions,
3973 : * we can use the FK semantics to make selectivity estimates that are more
3974 : * reliable than estimating from statistics, especially for multiple-column
3975 : * FKs, where the normal assumption of independent conditions tends to fail.
3976 : *
3977 : * In this function we annotate the ForeignKeyOptInfos in root->fkey_list
3978 : * with info about which eclasses and join qual clauses they match, and
3979 : * discard any ForeignKeyOptInfos that are irrelevant for the query.
3980 : */
3981 : void
3982 253302 : match_foreign_keys_to_quals(PlannerInfo *root)
3983 : {
3984 253302 : List *newlist = NIL;
3985 : ListCell *lc;
3986 :
3987 255028 : foreach(lc, root->fkey_list)
3988 : {
3989 1726 : ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
3990 : RelOptInfo *con_rel;
3991 : RelOptInfo *ref_rel;
3992 : int colno;
3993 :
3994 : /*
3995 : * Either relid might identify a rel that is in the query's rtable but
3996 : * isn't referenced by the jointree, or has been removed by join
3997 : * removal, so that it won't have a RelOptInfo. Hence don't use
3998 : * find_base_rel() here. We can ignore such FKs.
3999 : */
4000 1726 : if (fkinfo->con_relid >= root->simple_rel_array_size ||
4001 1726 : fkinfo->ref_relid >= root->simple_rel_array_size)
4002 0 : continue; /* just paranoia */
4003 1726 : con_rel = root->simple_rel_array[fkinfo->con_relid];
4004 1726 : if (con_rel == NULL)
4005 10 : continue;
4006 1716 : ref_rel = root->simple_rel_array[fkinfo->ref_relid];
4007 1716 : if (ref_rel == NULL)
4008 20 : continue;
4009 :
4010 : /*
4011 : * Ignore FK unless both rels are baserels. This gets rid of FKs that
4012 : * link to inheritance child rels (otherrels).
4013 : */
4014 1696 : if (con_rel->reloptkind != RELOPT_BASEREL ||
4015 1696 : ref_rel->reloptkind != RELOPT_BASEREL)
4016 0 : continue;
4017 :
4018 : /*
4019 : * Scan the columns and try to match them to eclasses and quals.
4020 : *
4021 : * Note: for simple inner joins, any match should be in an eclass.
4022 : * "Loose" quals that syntactically match an FK equality must have
4023 : * been rejected for EC status because they are outer-join quals or
4024 : * similar. We can still consider them to match the FK.
4025 : */
4026 3842 : for (colno = 0; colno < fkinfo->nkeys; colno++)
4027 : {
4028 : EquivalenceClass *ec;
4029 : AttrNumber con_attno,
4030 : ref_attno;
4031 : Oid fpeqop;
4032 : ListCell *lc2;
4033 :
4034 2146 : ec = match_eclasses_to_foreign_key_col(root, fkinfo, colno);
4035 : /* Don't bother looking for loose quals if we got an EC match */
4036 2146 : if (ec != NULL)
4037 : {
4038 533 : fkinfo->nmatched_ec++;
4039 533 : if (ec->ec_has_const)
4040 45 : fkinfo->nconst_ec++;
4041 533 : continue;
4042 : }
4043 :
4044 : /*
4045 : * Scan joininfo list for relevant clauses. Either rel's joininfo
4046 : * list would do equally well; we use con_rel's.
4047 : */
4048 1613 : con_attno = fkinfo->conkey[colno];
4049 1613 : ref_attno = fkinfo->confkey[colno];
4050 1613 : fpeqop = InvalidOid; /* we'll look this up only if needed */
4051 :
4052 4203 : foreach(lc2, con_rel->joininfo)
4053 : {
4054 2590 : RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc2);
4055 2590 : OpExpr *clause = (OpExpr *) rinfo->clause;
4056 : Var *leftvar;
4057 : Var *rightvar;
4058 :
4059 : /* Only binary OpExprs are useful for consideration */
4060 5168 : if (!IsA(clause, OpExpr) ||
4061 2578 : list_length(clause->args) != 2)
4062 12 : continue;
4063 2578 : leftvar = (Var *) get_leftop((Expr *) clause);
4064 2578 : rightvar = (Var *) get_rightop((Expr *) clause);
4065 :
4066 : /* Operands must be Vars, possibly with RelabelType */
4067 2783 : while (leftvar && IsA(leftvar, RelabelType))
4068 205 : leftvar = (Var *) ((RelabelType *) leftvar)->arg;
4069 2578 : if (!(leftvar && IsA(leftvar, Var)))
4070 12 : continue;
4071 2756 : while (rightvar && IsA(rightvar, RelabelType))
4072 190 : rightvar = (Var *) ((RelabelType *) rightvar)->arg;
4073 2566 : if (!(rightvar && IsA(rightvar, Var)))
4074 25 : continue;
4075 :
4076 : /* Now try to match the vars to the current foreign key cols */
4077 2541 : if (fkinfo->ref_relid == leftvar->varno &&
4078 2436 : ref_attno == leftvar->varattno &&
4079 1391 : fkinfo->con_relid == rightvar->varno &&
4080 1391 : con_attno == rightvar->varattno)
4081 : {
4082 : /* Vars match, but is it the right operator? */
4083 1326 : if (clause->opno == fkinfo->conpfeqop[colno])
4084 : {
4085 1326 : fkinfo->rinfos[colno] = lappend(fkinfo->rinfos[colno],
4086 : rinfo);
4087 1326 : fkinfo->nmatched_ri++;
4088 : }
4089 : }
4090 1215 : else if (fkinfo->ref_relid == rightvar->varno &&
4091 75 : ref_attno == rightvar->varattno &&
4092 30 : fkinfo->con_relid == leftvar->varno &&
4093 30 : con_attno == leftvar->varattno)
4094 : {
4095 : /*
4096 : * Reverse match, must check commutator operator. Look it
4097 : * up if we didn't already. (In the worst case we might
4098 : * do multiple lookups here, but that would require an FK
4099 : * equality operator without commutator, which is
4100 : * unlikely.)
4101 : */
4102 30 : if (!OidIsValid(fpeqop))
4103 30 : fpeqop = get_commutator(fkinfo->conpfeqop[colno]);
4104 30 : if (clause->opno == fpeqop)
4105 : {
4106 30 : fkinfo->rinfos[colno] = lappend(fkinfo->rinfos[colno],
4107 : rinfo);
4108 30 : fkinfo->nmatched_ri++;
4109 : }
4110 : }
4111 : }
4112 : /* If we found any matching loose quals, count col as matched */
4113 1613 : if (fkinfo->rinfos[colno])
4114 1356 : fkinfo->nmatched_rcols++;
4115 : }
4116 :
4117 : /*
4118 : * Currently, we drop multicolumn FKs that aren't fully matched to the
4119 : * query. Later we might figure out how to derive some sort of
4120 : * estimate from them, in which case this test should be weakened to
4121 : * "if ((fkinfo->nmatched_ec + fkinfo->nmatched_rcols) > 0)".
4122 : */
4123 1696 : if ((fkinfo->nmatched_ec + fkinfo->nmatched_rcols) == fkinfo->nkeys)
4124 1459 : newlist = lappend(newlist, fkinfo);
4125 : }
4126 : /* Replace fkey_list, thereby discarding any useless entries */
4127 253302 : root->fkey_list = newlist;
4128 253302 : }
4129 :
4130 :
4131 : /*****************************************************************************
4132 : *
4133 : * CHECKS FOR MERGEJOINABLE AND HASHJOINABLE CLAUSES
4134 : *
4135 : *****************************************************************************/
4136 :
4137 : /*
4138 : * check_mergejoinable
4139 : * If the restrictinfo's clause is mergejoinable, set the mergejoin
4140 : * info fields in the restrictinfo.
4141 : *
4142 : * Currently, we support mergejoin for binary opclauses where
4143 : * the operator is a mergejoinable operator. The arguments can be
4144 : * anything --- as long as there are no volatile functions in them.
4145 : */
4146 : static void
4147 528621 : check_mergejoinable(RestrictInfo *restrictinfo)
4148 : {
4149 528621 : Expr *clause = restrictinfo->clause;
4150 : Oid opno;
4151 : Node *leftarg;
4152 :
4153 528621 : if (restrictinfo->pseudoconstant)
4154 9185 : return;
4155 519436 : if (!is_opclause(clause))
4156 67358 : return;
4157 452078 : if (list_length(((OpExpr *) clause)->args) != 2)
4158 20 : return;
4159 :
4160 452058 : opno = ((OpExpr *) clause)->opno;
4161 452058 : leftarg = linitial(((OpExpr *) clause)->args);
4162 :
4163 452058 : if (op_mergejoinable(opno, exprType(leftarg)) &&
4164 388727 : !contain_volatile_functions((Node *) restrictinfo))
4165 388701 : restrictinfo->mergeopfamilies = get_mergejoin_opfamilies(opno);
4166 :
4167 : /*
4168 : * Note: op_mergejoinable is just a hint; if we fail to find the operator
4169 : * in any btree opfamilies, mergeopfamilies remains NIL and so the clause
4170 : * is not treated as mergejoinable.
4171 : */
4172 : }
4173 :
4174 : /*
4175 : * check_hashjoinable
4176 : * If the restrictinfo's clause is hashjoinable, set the hashjoin
4177 : * info fields in the restrictinfo.
4178 : *
4179 : * Currently, we support hashjoin for binary opclauses where
4180 : * the operator is a hashjoinable operator. The arguments can be
4181 : * anything --- as long as there are no volatile functions in them.
4182 : */
4183 : static void
4184 131161 : check_hashjoinable(RestrictInfo *restrictinfo)
4185 : {
4186 131161 : Expr *clause = restrictinfo->clause;
4187 : Oid opno;
4188 : Node *leftarg;
4189 :
4190 131161 : if (restrictinfo->pseudoconstant)
4191 5504 : return;
4192 125657 : if (!is_opclause(clause))
4193 5738 : return;
4194 119919 : if (list_length(((OpExpr *) clause)->args) != 2)
4195 0 : return;
4196 :
4197 119919 : opno = ((OpExpr *) clause)->opno;
4198 119919 : leftarg = linitial(((OpExpr *) clause)->args);
4199 :
4200 119919 : if (op_hashjoinable(opno, exprType(leftarg)) &&
4201 117307 : !contain_volatile_functions((Node *) restrictinfo))
4202 117301 : restrictinfo->hashjoinoperator = opno;
4203 : }
4204 :
4205 : /*
4206 : * check_memoizable
4207 : * If the restrictinfo's clause is suitable to be used for a Memoize node,
4208 : * set the left_hasheqoperator and right_hasheqoperator to the hash equality
4209 : * operator that will be needed during caching.
4210 : */
4211 : static void
4212 131161 : check_memoizable(RestrictInfo *restrictinfo)
4213 : {
4214 : TypeCacheEntry *typentry;
4215 131161 : Expr *clause = restrictinfo->clause;
4216 : Oid lefttype;
4217 : Oid righttype;
4218 :
4219 131161 : if (restrictinfo->pseudoconstant)
4220 5504 : return;
4221 125657 : if (!is_opclause(clause))
4222 5738 : return;
4223 119919 : if (list_length(((OpExpr *) clause)->args) != 2)
4224 0 : return;
4225 :
4226 119919 : lefttype = exprType(linitial(((OpExpr *) clause)->args));
4227 :
4228 119919 : typentry = lookup_type_cache(lefttype, TYPECACHE_HASH_PROC |
4229 : TYPECACHE_EQ_OPR);
4230 :
4231 119919 : if (OidIsValid(typentry->hash_proc) && OidIsValid(typentry->eq_opr))
4232 119579 : restrictinfo->left_hasheqoperator = typentry->eq_opr;
4233 :
4234 119919 : righttype = exprType(lsecond(((OpExpr *) clause)->args));
4235 :
4236 : /*
4237 : * Lookup the right type, unless it's the same as the left type, in which
4238 : * case typentry is already pointing to the required TypeCacheEntry.
4239 : */
4240 119919 : if (lefttype != righttype)
4241 1717 : typentry = lookup_type_cache(righttype, TYPECACHE_HASH_PROC |
4242 : TYPECACHE_EQ_OPR);
4243 :
4244 119919 : if (OidIsValid(typentry->hash_proc) && OidIsValid(typentry->eq_opr))
4245 119409 : restrictinfo->right_hasheqoperator = typentry->eq_opr;
4246 : }
|
