Debian Codegraph @

src/backend/optimizer/plan/initsplan.c

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