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