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