PostgreSQL Source Code  git master
createplan.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * createplan.c
4  * Routines to create the desired plan for processing a query.
5  * Planning is complete, we just need to convert the selected
6  * Path into a Plan.
7  *
8  * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
9  * Portions Copyright (c) 1994, Regents of the University of California
10  *
11  *
12  * IDENTIFICATION
13  * src/backend/optimizer/plan/createplan.c
14  *
15  *-------------------------------------------------------------------------
16  */
17 #include "postgres.h"
18 
19 #include <limits.h>
20 #include <math.h>
21 
22 #include "access/stratnum.h"
23 #include "access/sysattr.h"
24 #include "catalog/pg_class.h"
25 #include "foreign/fdwapi.h"
26 #include "miscadmin.h"
27 #include "nodes/extensible.h"
28 #include "nodes/makefuncs.h"
29 #include "nodes/nodeFuncs.h"
30 #include "optimizer/clauses.h"
31 #include "optimizer/cost.h"
32 #include "optimizer/paths.h"
33 #include "optimizer/placeholder.h"
34 #include "optimizer/plancat.h"
35 #include "optimizer/planmain.h"
36 #include "optimizer/planner.h"
37 #include "optimizer/predtest.h"
38 #include "optimizer/restrictinfo.h"
39 #include "optimizer/subselect.h"
40 #include "optimizer/tlist.h"
41 #include "optimizer/var.h"
42 #include "parser/parse_clause.h"
43 #include "parser/parsetree.h"
44 #include "utils/lsyscache.h"
45 
46 
47 /*
48  * Flag bits that can appear in the flags argument of create_plan_recurse().
49  * These can be OR-ed together.
50  *
51  * CP_EXACT_TLIST specifies that the generated plan node must return exactly
52  * the tlist specified by the path's pathtarget (this overrides both
53  * CP_SMALL_TLIST and CP_LABEL_TLIST, if those are set). Otherwise, the
54  * plan node is allowed to return just the Vars and PlaceHolderVars needed
55  * to evaluate the pathtarget.
56  *
57  * CP_SMALL_TLIST specifies that a narrower tlist is preferred. This is
58  * passed down by parent nodes such as Sort and Hash, which will have to
59  * store the returned tuples.
60  *
61  * CP_LABEL_TLIST specifies that the plan node must return columns matching
62  * any sortgrouprefs specified in its pathtarget, with appropriate
63  * ressortgroupref labels. This is passed down by parent nodes such as Sort
64  * and Group, which need these values to be available in their inputs.
65  */
66 #define CP_EXACT_TLIST 0x0001 /* Plan must return specified tlist */
67 #define CP_SMALL_TLIST 0x0002 /* Prefer narrower tlists */
68 #define CP_LABEL_TLIST 0x0004 /* tlist must contain sortgrouprefs */
69 
70 
71 static Plan *create_plan_recurse(PlannerInfo *root, Path *best_path,
72  int flags);
73 static Plan *create_scan_plan(PlannerInfo *root, Path *best_path,
74  int flags);
75 static List *build_path_tlist(PlannerInfo *root, Path *path);
76 static bool use_physical_tlist(PlannerInfo *root, Path *path, int flags);
77 static List *get_gating_quals(PlannerInfo *root, List *quals);
78 static Plan *create_gating_plan(PlannerInfo *root, Path *path, Plan *plan,
79  List *gating_quals);
80 static Plan *create_join_plan(PlannerInfo *root, JoinPath *best_path);
81 static Plan *create_append_plan(PlannerInfo *root, AppendPath *best_path);
82 static Plan *create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path);
83 static Result *create_result_plan(PlannerInfo *root, ResultPath *best_path);
85 static Material *create_material_plan(PlannerInfo *root, MaterialPath *best_path,
86  int flags);
87 static Plan *create_unique_plan(PlannerInfo *root, UniquePath *best_path,
88  int flags);
89 static Gather *create_gather_plan(PlannerInfo *root, GatherPath *best_path);
90 static Plan *create_projection_plan(PlannerInfo *root, ProjectionPath *best_path);
91 static Plan *inject_projection_plan(Plan *subplan, List *tlist, bool parallel_safe);
92 static Sort *create_sort_plan(PlannerInfo *root, SortPath *best_path, int flags);
93 static Group *create_group_plan(PlannerInfo *root, GroupPath *best_path);
95  int flags);
96 static Agg *create_agg_plan(PlannerInfo *root, AggPath *best_path);
98 static Result *create_minmaxagg_plan(PlannerInfo *root, MinMaxAggPath *best_path);
99 static WindowAgg *create_windowagg_plan(PlannerInfo *root, WindowAggPath *best_path);
100 static SetOp *create_setop_plan(PlannerInfo *root, SetOpPath *best_path,
101  int flags);
104  List *tlist,
105  int numSortCols, AttrNumber *sortColIdx,
106  int *partNumCols,
107  AttrNumber **partColIdx,
108  Oid **partOperators,
109  int *ordNumCols,
110  AttrNumber **ordColIdx,
111  Oid **ordOperators);
112 static LockRows *create_lockrows_plan(PlannerInfo *root, LockRowsPath *best_path,
113  int flags);
115 static Limit *create_limit_plan(PlannerInfo *root, LimitPath *best_path,
116  int flags);
117 static SeqScan *create_seqscan_plan(PlannerInfo *root, Path *best_path,
118  List *tlist, List *scan_clauses);
119 static SampleScan *create_samplescan_plan(PlannerInfo *root, Path *best_path,
120  List *tlist, List *scan_clauses);
121 static Scan *create_indexscan_plan(PlannerInfo *root, IndexPath *best_path,
122  List *tlist, List *scan_clauses, bool indexonly);
124  BitmapHeapPath *best_path,
125  List *tlist, List *scan_clauses);
126 static Plan *create_bitmap_subplan(PlannerInfo *root, Path *bitmapqual,
127  List **qual, List **indexqual, List **indexECs);
128 static void bitmap_subplan_mark_shared(Plan *plan);
129 static TidScan *create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
130  List *tlist, List *scan_clauses);
132  SubqueryScanPath *best_path,
133  List *tlist, List *scan_clauses);
134 static FunctionScan *create_functionscan_plan(PlannerInfo *root, Path *best_path,
135  List *tlist, List *scan_clauses);
136 static ValuesScan *create_valuesscan_plan(PlannerInfo *root, Path *best_path,
137  List *tlist, List *scan_clauses);
138 static TableFuncScan *create_tablefuncscan_plan(PlannerInfo *root, Path *best_path,
139  List *tlist, List *scan_clauses);
140 static CteScan *create_ctescan_plan(PlannerInfo *root, Path *best_path,
141  List *tlist, List *scan_clauses);
143  Path *best_path, List *tlist, List *scan_clauses);
144 static WorkTableScan *create_worktablescan_plan(PlannerInfo *root, Path *best_path,
145  List *tlist, List *scan_clauses);
147  List *tlist, List *scan_clauses);
149  CustomPath *best_path,
150  List *tlist, List *scan_clauses);
151 static NestLoop *create_nestloop_plan(PlannerInfo *root, NestPath *best_path);
152 static MergeJoin *create_mergejoin_plan(PlannerInfo *root, MergePath *best_path);
153 static HashJoin *create_hashjoin_plan(PlannerInfo *root, HashPath *best_path);
154 static Node *replace_nestloop_params(PlannerInfo *root, Node *expr);
157  List *subplan_params);
158 static List *fix_indexqual_references(PlannerInfo *root, IndexPath *index_path);
159 static List *fix_indexorderby_references(PlannerInfo *root, IndexPath *index_path);
160 static Node *fix_indexqual_operand(Node *node, IndexOptInfo *index, int indexcol);
161 static List *get_switched_clauses(List *clauses, Relids outerrelids);
162 static List *order_qual_clauses(PlannerInfo *root, List *clauses);
163 static void copy_generic_path_info(Plan *dest, Path *src);
164 static void copy_plan_costsize(Plan *dest, Plan *src);
165 static void label_sort_with_costsize(PlannerInfo *root, Sort *plan,
166  double limit_tuples);
167 static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);
168 static SampleScan *make_samplescan(List *qptlist, List *qpqual, Index scanrelid,
169  TableSampleClause *tsc);
170 static IndexScan *make_indexscan(List *qptlist, List *qpqual, Index scanrelid,
171  Oid indexid, List *indexqual, List *indexqualorig,
172  List *indexorderby, List *indexorderbyorig,
173  List *indexorderbyops,
174  ScanDirection indexscandir);
175 static IndexOnlyScan *make_indexonlyscan(List *qptlist, List *qpqual,
176  Index scanrelid, Oid indexid,
177  List *indexqual, List *indexorderby,
178  List *indextlist,
179  ScanDirection indexscandir);
180 static BitmapIndexScan *make_bitmap_indexscan(Index scanrelid, Oid indexid,
181  List *indexqual,
182  List *indexqualorig);
183 static BitmapHeapScan *make_bitmap_heapscan(List *qptlist,
184  List *qpqual,
185  Plan *lefttree,
186  List *bitmapqualorig,
187  Index scanrelid);
188 static TidScan *make_tidscan(List *qptlist, List *qpqual, Index scanrelid,
189  List *tidquals);
190 static SubqueryScan *make_subqueryscan(List *qptlist,
191  List *qpqual,
192  Index scanrelid,
193  Plan *subplan);
194 static FunctionScan *make_functionscan(List *qptlist, List *qpqual,
195  Index scanrelid, List *functions, bool funcordinality);
196 static ValuesScan *make_valuesscan(List *qptlist, List *qpqual,
197  Index scanrelid, List *values_lists);
198 static TableFuncScan *make_tablefuncscan(List *qptlist, List *qpqual,
199  Index scanrelid, TableFunc *tablefunc);
200 static CteScan *make_ctescan(List *qptlist, List *qpqual,
201  Index scanrelid, int ctePlanId, int cteParam);
202 static NamedTuplestoreScan *make_namedtuplestorescan(List *qptlist, List *qpqual,
203  Index scanrelid, char *enrname);
204 static WorkTableScan *make_worktablescan(List *qptlist, List *qpqual,
205  Index scanrelid, int wtParam);
206 static Append *make_append(List *appendplans, int first_partial_plan,
207  List *tlist, List *partitioned_rels);
209  Plan *lefttree,
210  Plan *righttree,
211  int wtParam,
212  List *distinctList,
213  long numGroups);
214 static BitmapAnd *make_bitmap_and(List *bitmapplans);
215 static BitmapOr *make_bitmap_or(List *bitmapplans);
216 static NestLoop *make_nestloop(List *tlist,
217  List *joinclauses, List *otherclauses, List *nestParams,
218  Plan *lefttree, Plan *righttree,
219  JoinType jointype, bool inner_unique);
220 static HashJoin *make_hashjoin(List *tlist,
221  List *joinclauses, List *otherclauses,
222  List *hashclauses,
223  Plan *lefttree, Plan *righttree,
224  JoinType jointype, bool inner_unique);
225 static Hash *make_hash(Plan *lefttree,
226  Oid skewTable,
227  AttrNumber skewColumn,
228  bool skewInherit);
229 static MergeJoin *make_mergejoin(List *tlist,
230  List *joinclauses, List *otherclauses,
231  List *mergeclauses,
232  Oid *mergefamilies,
233  Oid *mergecollations,
234  int *mergestrategies,
235  bool *mergenullsfirst,
236  Plan *lefttree, Plan *righttree,
237  JoinType jointype, bool inner_unique,
238  bool skip_mark_restore);
239 static Sort *make_sort(Plan *lefttree, int numCols,
240  AttrNumber *sortColIdx, Oid *sortOperators,
241  Oid *collations, bool *nullsFirst);
242 static Plan *prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
243  Relids relids,
244  const AttrNumber *reqColIdx,
245  bool adjust_tlist_in_place,
246  int *p_numsortkeys,
247  AttrNumber **p_sortColIdx,
248  Oid **p_sortOperators,
249  Oid **p_collations,
250  bool **p_nullsFirst);
252  TargetEntry *tle,
253  Relids relids);
254 static Sort *make_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
255  Relids relids);
256 static Sort *make_sort_from_groupcols(List *groupcls,
257  AttrNumber *grpColIdx,
258  Plan *lefttree);
259 static Material *make_material(Plan *lefttree);
260 static WindowAgg *make_windowagg(List *tlist, Index winref,
261  int partNumCols, AttrNumber *partColIdx, Oid *partOperators,
262  int ordNumCols, AttrNumber *ordColIdx, Oid *ordOperators,
263  int frameOptions, Node *startOffset, Node *endOffset,
264  Plan *lefttree);
265 static Group *make_group(List *tlist, List *qual, int numGroupCols,
266  AttrNumber *grpColIdx, Oid *grpOperators,
267  Plan *lefttree);
268 static Unique *make_unique_from_sortclauses(Plan *lefttree, List *distinctList);
269 static Unique *make_unique_from_pathkeys(Plan *lefttree,
270  List *pathkeys, int numCols);
271 static Gather *make_gather(List *qptlist, List *qpqual,
272  int nworkers, int rescan_param, bool single_copy, Plan *subplan);
273 static SetOp *make_setop(SetOpCmd cmd, SetOpStrategy strategy, Plan *lefttree,
274  List *distinctList, AttrNumber flagColIdx, int firstFlag,
275  long numGroups);
276 static LockRows *make_lockrows(Plan *lefttree, List *rowMarks, int epqParam);
277 static Result *make_result(List *tlist, Node *resconstantqual, Plan *subplan);
278 static ProjectSet *make_project_set(List *tlist, Plan *subplan);
280  CmdType operation, bool canSetTag,
281  Index nominalRelation, List *partitioned_rels,
282  List *resultRelations, List *subplans,
283  List *withCheckOptionLists, List *returningLists,
284  List *rowMarks, OnConflictExpr *onconflict, int epqParam);
286  GatherMergePath *best_path);
287 
288 
289 /*
290  * create_plan
291  * Creates the access plan for a query by recursively processing the
292  * desired tree of pathnodes, starting at the node 'best_path'. For
293  * every pathnode found, we create a corresponding plan node containing
294  * appropriate id, target list, and qualification information.
295  *
296  * The tlists and quals in the plan tree are still in planner format,
297  * ie, Vars still correspond to the parser's numbering. This will be
298  * fixed later by setrefs.c.
299  *
300  * best_path is the best access path
301  *
302  * Returns a Plan tree.
303  */
304 Plan *
305 create_plan(PlannerInfo *root, Path *best_path)
306 {
307  Plan *plan;
308 
309  /* plan_params should not be in use in current query level */
310  Assert(root->plan_params == NIL);
311 
312  /* Initialize this module's private workspace in PlannerInfo */
313  root->curOuterRels = NULL;
314  root->curOuterParams = NIL;
315 
316  /* Recursively process the path tree, demanding the correct tlist result */
317  plan = create_plan_recurse(root, best_path, CP_EXACT_TLIST);
318 
319  /*
320  * Make sure the topmost plan node's targetlist exposes the original
321  * column names and other decorative info. Targetlists generated within
322  * the planner don't bother with that stuff, but we must have it on the
323  * top-level tlist seen at execution time. However, ModifyTable plan
324  * nodes don't have a tlist matching the querytree targetlist.
325  */
326  if (!IsA(plan, ModifyTable))
328 
329  /*
330  * Attach any initPlans created in this query level to the topmost plan
331  * node. (In principle the initplans could go in any plan node at or
332  * above where they're referenced, but there seems no reason to put them
333  * any lower than the topmost node for the query level. Also, see
334  * comments for SS_finalize_plan before you try to change this.)
335  */
336  SS_attach_initplans(root, plan);
337 
338  /* Check we successfully assigned all NestLoopParams to plan nodes */
339  if (root->curOuterParams != NIL)
340  elog(ERROR, "failed to assign all NestLoopParams to plan nodes");
341 
342  /*
343  * Reset plan_params to ensure param IDs used for nestloop params are not
344  * re-used later
345  */
346  root->plan_params = NIL;
347 
348  return plan;
349 }
350 
351 /*
352  * create_plan_recurse
353  * Recursive guts of create_plan().
354  */
355 static Plan *
356 create_plan_recurse(PlannerInfo *root, Path *best_path, int flags)
357 {
358  Plan *plan;
359 
360  switch (best_path->pathtype)
361  {
362  case T_SeqScan:
363  case T_SampleScan:
364  case T_IndexScan:
365  case T_IndexOnlyScan:
366  case T_BitmapHeapScan:
367  case T_TidScan:
368  case T_SubqueryScan:
369  case T_FunctionScan:
370  case T_TableFuncScan:
371  case T_ValuesScan:
372  case T_CteScan:
373  case T_WorkTableScan:
375  case T_ForeignScan:
376  case T_CustomScan:
377  plan = create_scan_plan(root, best_path, flags);
378  break;
379  case T_HashJoin:
380  case T_MergeJoin:
381  case T_NestLoop:
382  plan = create_join_plan(root,
383  (JoinPath *) best_path);
384  break;
385  case T_Append:
386  plan = create_append_plan(root,
387  (AppendPath *) best_path);
388  break;
389  case T_MergeAppend:
390  plan = create_merge_append_plan(root,
391  (MergeAppendPath *) best_path);
392  break;
393  case T_Result:
394  if (IsA(best_path, ProjectionPath))
395  {
396  plan = create_projection_plan(root,
397  (ProjectionPath *) best_path);
398  }
399  else if (IsA(best_path, MinMaxAggPath))
400  {
401  plan = (Plan *) create_minmaxagg_plan(root,
402  (MinMaxAggPath *) best_path);
403  }
404  else
405  {
406  Assert(IsA(best_path, ResultPath));
407  plan = (Plan *) create_result_plan(root,
408  (ResultPath *) best_path);
409  }
410  break;
411  case T_ProjectSet:
412  plan = (Plan *) create_project_set_plan(root,
413  (ProjectSetPath *) best_path);
414  break;
415  case T_Material:
416  plan = (Plan *) create_material_plan(root,
417  (MaterialPath *) best_path,
418  flags);
419  break;
420  case T_Unique:
421  if (IsA(best_path, UpperUniquePath))
422  {
423  plan = (Plan *) create_upper_unique_plan(root,
424  (UpperUniquePath *) best_path,
425  flags);
426  }
427  else
428  {
429  Assert(IsA(best_path, UniquePath));
430  plan = create_unique_plan(root,
431  (UniquePath *) best_path,
432  flags);
433  }
434  break;
435  case T_Gather:
436  plan = (Plan *) create_gather_plan(root,
437  (GatherPath *) best_path);
438  break;
439  case T_Sort:
440  plan = (Plan *) create_sort_plan(root,
441  (SortPath *) best_path,
442  flags);
443  break;
444  case T_Group:
445  plan = (Plan *) create_group_plan(root,
446  (GroupPath *) best_path);
447  break;
448  case T_Agg:
449  if (IsA(best_path, GroupingSetsPath))
450  plan = create_groupingsets_plan(root,
451  (GroupingSetsPath *) best_path);
452  else
453  {
454  Assert(IsA(best_path, AggPath));
455  plan = (Plan *) create_agg_plan(root,
456  (AggPath *) best_path);
457  }
458  break;
459  case T_WindowAgg:
460  plan = (Plan *) create_windowagg_plan(root,
461  (WindowAggPath *) best_path);
462  break;
463  case T_SetOp:
464  plan = (Plan *) create_setop_plan(root,
465  (SetOpPath *) best_path,
466  flags);
467  break;
468  case T_RecursiveUnion:
469  plan = (Plan *) create_recursiveunion_plan(root,
470  (RecursiveUnionPath *) best_path);
471  break;
472  case T_LockRows:
473  plan = (Plan *) create_lockrows_plan(root,
474  (LockRowsPath *) best_path,
475  flags);
476  break;
477  case T_ModifyTable:
478  plan = (Plan *) create_modifytable_plan(root,
479  (ModifyTablePath *) best_path);
480  break;
481  case T_Limit:
482  plan = (Plan *) create_limit_plan(root,
483  (LimitPath *) best_path,
484  flags);
485  break;
486  case T_GatherMerge:
487  plan = (Plan *) create_gather_merge_plan(root,
488  (GatherMergePath *) best_path);
489  break;
490  default:
491  elog(ERROR, "unrecognized node type: %d",
492  (int) best_path->pathtype);
493  plan = NULL; /* keep compiler quiet */
494  break;
495  }
496 
497  return plan;
498 }
499 
500 /*
501  * create_scan_plan
502  * Create a scan plan for the parent relation of 'best_path'.
503  */
504 static Plan *
505 create_scan_plan(PlannerInfo *root, Path *best_path, int flags)
506 {
507  RelOptInfo *rel = best_path->parent;
508  List *scan_clauses;
509  List *gating_clauses;
510  List *tlist;
511  Plan *plan;
512 
513  /*
514  * Extract the relevant restriction clauses from the parent relation. The
515  * executor must apply all these restrictions during the scan, except for
516  * pseudoconstants which we'll take care of below.
517  *
518  * If this is a plain indexscan or index-only scan, we need not consider
519  * restriction clauses that are implied by the index's predicate, so use
520  * indrestrictinfo not baserestrictinfo. Note that we can't do that for
521  * bitmap indexscans, since there's not necessarily a single index
522  * involved; but it doesn't matter since create_bitmap_scan_plan() will be
523  * able to get rid of such clauses anyway via predicate proof.
524  */
525  switch (best_path->pathtype)
526  {
527  case T_IndexScan:
528  case T_IndexOnlyScan:
529  scan_clauses = castNode(IndexPath, best_path)->indexinfo->indrestrictinfo;
530  break;
531  default:
532  scan_clauses = rel->baserestrictinfo;
533  break;
534  }
535 
536  /*
537  * If this is a parameterized scan, we also need to enforce all the join
538  * clauses available from the outer relation(s).
539  *
540  * For paranoia's sake, don't modify the stored baserestrictinfo list.
541  */
542  if (best_path->param_info)
543  scan_clauses = list_concat(list_copy(scan_clauses),
544  best_path->param_info->ppi_clauses);
545 
546  /*
547  * Detect whether we have any pseudoconstant quals to deal with. Then, if
548  * we'll need a gating Result node, it will be able to project, so there
549  * are no requirements on the child's tlist.
550  */
551  gating_clauses = get_gating_quals(root, scan_clauses);
552  if (gating_clauses)
553  flags = 0;
554 
555  /*
556  * For table scans, rather than using the relation targetlist (which is
557  * only those Vars actually needed by the query), we prefer to generate a
558  * tlist containing all Vars in order. This will allow the executor to
559  * optimize away projection of the table tuples, if possible.
560  */
561  if (use_physical_tlist(root, best_path, flags))
562  {
563  if (best_path->pathtype == T_IndexOnlyScan)
564  {
565  /* For index-only scan, the preferred tlist is the index's */
566  tlist = copyObject(((IndexPath *) best_path)->indexinfo->indextlist);
567 
568  /*
569  * Transfer any sortgroupref data to the replacement tlist, unless
570  * we don't care because the gating Result will handle it.
571  */
572  if (!gating_clauses)
573  apply_pathtarget_labeling_to_tlist(tlist, best_path->pathtarget);
574  }
575  else
576  {
577  tlist = build_physical_tlist(root, rel);
578  if (tlist == NIL)
579  {
580  /* Failed because of dropped cols, so use regular method */
581  tlist = build_path_tlist(root, best_path);
582  }
583  else
584  {
585  /* As above, transfer sortgroupref data to replacement tlist */
586  if (!gating_clauses)
588  }
589  }
590  }
591  else
592  {
593  tlist = build_path_tlist(root, best_path);
594  }
595 
596  switch (best_path->pathtype)
597  {
598  case T_SeqScan:
599  plan = (Plan *) create_seqscan_plan(root,
600  best_path,
601  tlist,
602  scan_clauses);
603  break;
604 
605  case T_SampleScan:
606  plan = (Plan *) create_samplescan_plan(root,
607  best_path,
608  tlist,
609  scan_clauses);
610  break;
611 
612  case T_IndexScan:
613  plan = (Plan *) create_indexscan_plan(root,
614  (IndexPath *) best_path,
615  tlist,
616  scan_clauses,
617  false);
618  break;
619 
620  case T_IndexOnlyScan:
621  plan = (Plan *) create_indexscan_plan(root,
622  (IndexPath *) best_path,
623  tlist,
624  scan_clauses,
625  true);
626  break;
627 
628  case T_BitmapHeapScan:
629  plan = (Plan *) create_bitmap_scan_plan(root,
630  (BitmapHeapPath *) best_path,
631  tlist,
632  scan_clauses);
633  break;
634 
635  case T_TidScan:
636  plan = (Plan *) create_tidscan_plan(root,
637  (TidPath *) best_path,
638  tlist,
639  scan_clauses);
640  break;
641 
642  case T_SubqueryScan:
643  plan = (Plan *) create_subqueryscan_plan(root,
644  (SubqueryScanPath *) best_path,
645  tlist,
646  scan_clauses);
647  break;
648 
649  case T_FunctionScan:
650  plan = (Plan *) create_functionscan_plan(root,
651  best_path,
652  tlist,
653  scan_clauses);
654  break;
655 
656  case T_TableFuncScan:
657  plan = (Plan *) create_tablefuncscan_plan(root,
658  best_path,
659  tlist,
660  scan_clauses);
661  break;
662 
663  case T_ValuesScan:
664  plan = (Plan *) create_valuesscan_plan(root,
665  best_path,
666  tlist,
667  scan_clauses);
668  break;
669 
670  case T_CteScan:
671  plan = (Plan *) create_ctescan_plan(root,
672  best_path,
673  tlist,
674  scan_clauses);
675  break;
676 
678  plan = (Plan *) create_namedtuplestorescan_plan(root,
679  best_path,
680  tlist,
681  scan_clauses);
682  break;
683 
684  case T_WorkTableScan:
685  plan = (Plan *) create_worktablescan_plan(root,
686  best_path,
687  tlist,
688  scan_clauses);
689  break;
690 
691  case T_ForeignScan:
692  plan = (Plan *) create_foreignscan_plan(root,
693  (ForeignPath *) best_path,
694  tlist,
695  scan_clauses);
696  break;
697 
698  case T_CustomScan:
699  plan = (Plan *) create_customscan_plan(root,
700  (CustomPath *) best_path,
701  tlist,
702  scan_clauses);
703  break;
704 
705  default:
706  elog(ERROR, "unrecognized node type: %d",
707  (int) best_path->pathtype);
708  plan = NULL; /* keep compiler quiet */
709  break;
710  }
711 
712  /*
713  * If there are any pseudoconstant clauses attached to this node, insert a
714  * gating Result node that evaluates the pseudoconstants as one-time
715  * quals.
716  */
717  if (gating_clauses)
718  plan = create_gating_plan(root, best_path, plan, gating_clauses);
719 
720  return plan;
721 }
722 
723 /*
724  * Build a target list (ie, a list of TargetEntry) for the Path's output.
725  *
726  * This is almost just make_tlist_from_pathtarget(), but we also have to
727  * deal with replacing nestloop params.
728  */
729 static List *
731 {
732  List *tlist = NIL;
733  Index *sortgrouprefs = path->pathtarget->sortgrouprefs;
734  int resno = 1;
735  ListCell *v;
736 
737  foreach(v, path->pathtarget->exprs)
738  {
739  Node *node = (Node *) lfirst(v);
740  TargetEntry *tle;
741 
742  /*
743  * If it's a parameterized path, there might be lateral references in
744  * the tlist, which need to be replaced with Params. There's no need
745  * to remake the TargetEntry nodes, so apply this to each list item
746  * separately.
747  */
748  if (path->param_info)
749  node = replace_nestloop_params(root, node);
750 
751  tle = makeTargetEntry((Expr *) node,
752  resno,
753  NULL,
754  false);
755  if (sortgrouprefs)
756  tle->ressortgroupref = sortgrouprefs[resno - 1];
757 
758  tlist = lappend(tlist, tle);
759  resno++;
760  }
761  return tlist;
762 }
763 
764 /*
765  * use_physical_tlist
766  * Decide whether to use a tlist matching relation structure,
767  * rather than only those Vars actually referenced.
768  */
769 static bool
770 use_physical_tlist(PlannerInfo *root, Path *path, int flags)
771 {
772  RelOptInfo *rel = path->parent;
773  int i;
774  ListCell *lc;
775 
776  /*
777  * Forget it if either exact tlist or small tlist is demanded.
778  */
779  if (flags & (CP_EXACT_TLIST | CP_SMALL_TLIST))
780  return false;
781 
782  /*
783  * We can do this for real relation scans, subquery scans, function scans,
784  * tablefunc scans, values scans, and CTE scans (but not for, eg, joins).
785  */
786  if (rel->rtekind != RTE_RELATION &&
787  rel->rtekind != RTE_SUBQUERY &&
788  rel->rtekind != RTE_FUNCTION &&
789  rel->rtekind != RTE_TABLEFUNC &&
790  rel->rtekind != RTE_VALUES &&
791  rel->rtekind != RTE_CTE)
792  return false;
793 
794  /*
795  * Can't do it with inheritance cases either (mainly because Append
796  * doesn't project; this test may be unnecessary now that
797  * create_append_plan instructs its children to return an exact tlist).
798  */
799  if (rel->reloptkind != RELOPT_BASEREL)
800  return false;
801 
802  /*
803  * Also, don't do it to a CustomPath; the premise that we're extracting
804  * columns from a simple physical tuple is unlikely to hold for those.
805  * (When it does make sense, the custom path creator can set up the path's
806  * pathtarget that way.)
807  */
808  if (IsA(path, CustomPath))
809  return false;
810 
811  /*
812  * If a bitmap scan's tlist is empty, keep it as-is. This may allow the
813  * executor to skip heap page fetches, and in any case, the benefit of
814  * using a physical tlist instead would be minimal.
815  */
816  if (IsA(path, BitmapHeapPath) &&
817  path->pathtarget->exprs == NIL)
818  return false;
819 
820  /*
821  * Can't do it if any system columns or whole-row Vars are requested.
822  * (This could possibly be fixed but would take some fragile assumptions
823  * in setrefs.c, I think.)
824  */
825  for (i = rel->min_attr; i <= 0; i++)
826  {
827  if (!bms_is_empty(rel->attr_needed[i - rel->min_attr]))
828  return false;
829  }
830 
831  /*
832  * Can't do it if the rel is required to emit any placeholder expressions,
833  * either.
834  */
835  foreach(lc, root->placeholder_list)
836  {
837  PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
838 
839  if (bms_nonempty_difference(phinfo->ph_needed, rel->relids) &&
840  bms_is_subset(phinfo->ph_eval_at, rel->relids))
841  return false;
842  }
843 
844  /*
845  * Also, can't do it if CP_LABEL_TLIST is specified and path is requested
846  * to emit any sort/group columns that are not simple Vars. (If they are
847  * simple Vars, they should appear in the physical tlist, and
848  * apply_pathtarget_labeling_to_tlist will take care of getting them
849  * labeled again.) We also have to check that no two sort/group columns
850  * are the same Var, else that element of the physical tlist would need
851  * conflicting ressortgroupref labels.
852  */
853  if ((flags & CP_LABEL_TLIST) && path->pathtarget->sortgrouprefs)
854  {
855  Bitmapset *sortgroupatts = NULL;
856 
857  i = 0;
858  foreach(lc, path->pathtarget->exprs)
859  {
860  Expr *expr = (Expr *) lfirst(lc);
861 
862  if (path->pathtarget->sortgrouprefs[i])
863  {
864  if (expr && IsA(expr, Var))
865  {
866  int attno = ((Var *) expr)->varattno;
867 
869  if (bms_is_member(attno, sortgroupatts))
870  return false;
871  sortgroupatts = bms_add_member(sortgroupatts, attno);
872  }
873  else
874  return false;
875  }
876  i++;
877  }
878  }
879 
880  return true;
881 }
882 
883 /*
884  * get_gating_quals
885  * See if there are pseudoconstant quals in a node's quals list
886  *
887  * If the node's quals list includes any pseudoconstant quals,
888  * return just those quals.
889  */
890 static List *
892 {
893  /* No need to look if we know there are no pseudoconstants */
894  if (!root->hasPseudoConstantQuals)
895  return NIL;
896 
897  /* Sort into desirable execution order while still in RestrictInfo form */
898  quals = order_qual_clauses(root, quals);
899 
900  /* Pull out any pseudoconstant quals from the RestrictInfo list */
901  return extract_actual_clauses(quals, true);
902 }
903 
904 /*
905  * create_gating_plan
906  * Deal with pseudoconstant qual clauses
907  *
908  * Add a gating Result node atop the already-built plan.
909  */
910 static Plan *
912  List *gating_quals)
913 {
914  Plan *gplan;
915 
916  Assert(gating_quals);
917 
918  /*
919  * Since we need a Result node anyway, always return the path's requested
920  * tlist; that's never a wrong choice, even if the parent node didn't ask
921  * for CP_EXACT_TLIST.
922  */
923  gplan = (Plan *) make_result(build_path_tlist(root, path),
924  (Node *) gating_quals,
925  plan);
926 
927  /*
928  * Notice that we don't change cost or size estimates when doing gating.
929  * The costs of qual eval were already included in the subplan's cost.
930  * Leaving the size alone amounts to assuming that the gating qual will
931  * succeed, which is the conservative estimate for planning upper queries.
932  * We certainly don't want to assume the output size is zero (unless the
933  * gating qual is actually constant FALSE, and that case is dealt with in
934  * clausesel.c). Interpolating between the two cases is silly, because it
935  * doesn't reflect what will really happen at runtime, and besides which
936  * in most cases we have only a very bad idea of the probability of the
937  * gating qual being true.
938  */
939  copy_plan_costsize(gplan, plan);
940 
941  /* Gating quals could be unsafe, so better use the Path's safety flag */
942  gplan->parallel_safe = path->parallel_safe;
943 
944  return gplan;
945 }
946 
947 /*
948  * create_join_plan
949  * Create a join plan for 'best_path' and (recursively) plans for its
950  * inner and outer paths.
951  */
952 static Plan *
954 {
955  Plan *plan;
956  List *gating_clauses;
957 
958  switch (best_path->path.pathtype)
959  {
960  case T_MergeJoin:
961  plan = (Plan *) create_mergejoin_plan(root,
962  (MergePath *) best_path);
963  break;
964  case T_HashJoin:
965  plan = (Plan *) create_hashjoin_plan(root,
966  (HashPath *) best_path);
967  break;
968  case T_NestLoop:
969  plan = (Plan *) create_nestloop_plan(root,
970  (NestPath *) best_path);
971  break;
972  default:
973  elog(ERROR, "unrecognized node type: %d",
974  (int) best_path->path.pathtype);
975  plan = NULL; /* keep compiler quiet */
976  break;
977  }
978 
979  /*
980  * If there are any pseudoconstant clauses attached to this node, insert a
981  * gating Result node that evaluates the pseudoconstants as one-time
982  * quals.
983  */
984  gating_clauses = get_gating_quals(root, best_path->joinrestrictinfo);
985  if (gating_clauses)
986  plan = create_gating_plan(root, (Path *) best_path, plan,
987  gating_clauses);
988 
989 #ifdef NOT_USED
990 
991  /*
992  * * Expensive function pullups may have pulled local predicates * into
993  * this path node. Put them in the qpqual of the plan node. * JMH,
994  * 6/15/92
995  */
996  if (get_loc_restrictinfo(best_path) != NIL)
997  set_qpqual((Plan) plan,
998  list_concat(get_qpqual((Plan) plan),
999  get_actual_clauses(get_loc_restrictinfo(best_path))));
1000 #endif
1001 
1002  return plan;
1003 }
1004 
1005 /*
1006  * create_append_plan
1007  * Create an Append plan for 'best_path' and (recursively) plans
1008  * for its subpaths.
1009  *
1010  * Returns a Plan node.
1011  */
1012 static Plan *
1014 {
1015  Append *plan;
1016  List *tlist = build_path_tlist(root, &best_path->path);
1017  List *subplans = NIL;
1018  ListCell *subpaths;
1019 
1020  /*
1021  * The subpaths list could be empty, if every child was proven empty by
1022  * constraint exclusion. In that case generate a dummy plan that returns
1023  * no rows.
1024  *
1025  * Note that an AppendPath with no members is also generated in certain
1026  * cases where there was no appending construct at all, but we know the
1027  * relation is empty (see set_dummy_rel_pathlist).
1028  */
1029  if (best_path->subpaths == NIL)
1030  {
1031  /* Generate a Result plan with constant-FALSE gating qual */
1032  Plan *plan;
1033 
1034  plan = (Plan *) make_result(tlist,
1035  (Node *) list_make1(makeBoolConst(false,
1036  false)),
1037  NULL);
1038 
1039  copy_generic_path_info(plan, (Path *) best_path);
1040 
1041  return plan;
1042  }
1043 
1044  /* Build the plan for each child */
1045  foreach(subpaths, best_path->subpaths)
1046  {
1047  Path *subpath = (Path *) lfirst(subpaths);
1048  Plan *subplan;
1049 
1050  /* Must insist that all children return the same tlist */
1051  subplan = create_plan_recurse(root, subpath, CP_EXACT_TLIST);
1052 
1053  subplans = lappend(subplans, subplan);
1054  }
1055 
1056  /*
1057  * XXX ideally, if there's just one child, we'd not bother to generate an
1058  * Append node but just return the single child. At the moment this does
1059  * not work because the varno of the child scan plan won't match the
1060  * parent-rel Vars it'll be asked to emit.
1061  */
1062 
1063  plan = make_append(subplans, best_path->first_partial_path,
1064  tlist, best_path->partitioned_rels);
1065 
1066  copy_generic_path_info(&plan->plan, (Path *) best_path);
1067 
1068  return (Plan *) plan;
1069 }
1070 
1071 /*
1072  * create_merge_append_plan
1073  * Create a MergeAppend plan for 'best_path' and (recursively) plans
1074  * for its subpaths.
1075  *
1076  * Returns a Plan node.
1077  */
1078 static Plan *
1080 {
1081  MergeAppend *node = makeNode(MergeAppend);
1082  Plan *plan = &node->plan;
1083  List *tlist = build_path_tlist(root, &best_path->path);
1084  List *pathkeys = best_path->path.pathkeys;
1085  List *subplans = NIL;
1086  ListCell *subpaths;
1087 
1088  /*
1089  * We don't have the actual creation of the MergeAppend node split out
1090  * into a separate make_xxx function. This is because we want to run
1091  * prepare_sort_from_pathkeys on it before we do so on the individual
1092  * child plans, to make cross-checking the sort info easier.
1093  */
1094  copy_generic_path_info(plan, (Path *) best_path);
1095  plan->targetlist = tlist;
1096  plan->qual = NIL;
1097  plan->lefttree = NULL;
1098  plan->righttree = NULL;
1099 
1100  /* Compute sort column info, and adjust MergeAppend's tlist as needed */
1101  (void) prepare_sort_from_pathkeys(plan, pathkeys,
1102  best_path->path.parent->relids,
1103  NULL,
1104  true,
1105  &node->numCols,
1106  &node->sortColIdx,
1107  &node->sortOperators,
1108  &node->collations,
1109  &node->nullsFirst);
1110 
1111  /*
1112  * Now prepare the child plans. We must apply prepare_sort_from_pathkeys
1113  * even to subplans that don't need an explicit sort, to make sure they
1114  * are returning the same sort key columns the MergeAppend expects.
1115  */
1116  foreach(subpaths, best_path->subpaths)
1117  {
1118  Path *subpath = (Path *) lfirst(subpaths);
1119  Plan *subplan;
1120  int numsortkeys;
1121  AttrNumber *sortColIdx;
1122  Oid *sortOperators;
1123  Oid *collations;
1124  bool *nullsFirst;
1125 
1126  /* Build the child plan */
1127  /* Must insist that all children return the same tlist */
1128  subplan = create_plan_recurse(root, subpath, CP_EXACT_TLIST);
1129 
1130  /* Compute sort column info, and adjust subplan's tlist as needed */
1131  subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
1132  subpath->parent->relids,
1133  node->sortColIdx,
1134  false,
1135  &numsortkeys,
1136  &sortColIdx,
1137  &sortOperators,
1138  &collations,
1139  &nullsFirst);
1140 
1141  /*
1142  * Check that we got the same sort key information. We just Assert
1143  * that the sortops match, since those depend only on the pathkeys;
1144  * but it seems like a good idea to check the sort column numbers
1145  * explicitly, to ensure the tlists really do match up.
1146  */
1147  Assert(numsortkeys == node->numCols);
1148  if (memcmp(sortColIdx, node->sortColIdx,
1149  numsortkeys * sizeof(AttrNumber)) != 0)
1150  elog(ERROR, "MergeAppend child's targetlist doesn't match MergeAppend");
1151  Assert(memcmp(sortOperators, node->sortOperators,
1152  numsortkeys * sizeof(Oid)) == 0);
1153  Assert(memcmp(collations, node->collations,
1154  numsortkeys * sizeof(Oid)) == 0);
1155  Assert(memcmp(nullsFirst, node->nullsFirst,
1156  numsortkeys * sizeof(bool)) == 0);
1157 
1158  /* Now, insert a Sort node if subplan isn't sufficiently ordered */
1159  if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
1160  {
1161  Sort *sort = make_sort(subplan, numsortkeys,
1162  sortColIdx, sortOperators,
1163  collations, nullsFirst);
1164 
1165  label_sort_with_costsize(root, sort, best_path->limit_tuples);
1166  subplan = (Plan *) sort;
1167  }
1168 
1169  subplans = lappend(subplans, subplan);
1170  }
1171 
1172  node->partitioned_rels = best_path->partitioned_rels;
1173  node->mergeplans = subplans;
1174 
1175  return (Plan *) node;
1176 }
1177 
1178 /*
1179  * create_result_plan
1180  * Create a Result plan for 'best_path'.
1181  * This is only used for degenerate cases, such as a query with an empty
1182  * jointree.
1183  *
1184  * Returns a Plan node.
1185  */
1186 static Result *
1188 {
1189  Result *plan;
1190  List *tlist;
1191  List *quals;
1192 
1193  tlist = build_path_tlist(root, &best_path->path);
1194 
1195  /* best_path->quals is just bare clauses */
1196  quals = order_qual_clauses(root, best_path->quals);
1197 
1198  plan = make_result(tlist, (Node *) quals, NULL);
1199 
1200  copy_generic_path_info(&plan->plan, (Path *) best_path);
1201 
1202  return plan;
1203 }
1204 
1205 /*
1206  * create_project_set_plan
1207  * Create a ProjectSet plan for 'best_path'.
1208  *
1209  * Returns a Plan node.
1210  */
1211 static ProjectSet *
1213 {
1214  ProjectSet *plan;
1215  Plan *subplan;
1216  List *tlist;
1217 
1218  /* Since we intend to project, we don't need to constrain child tlist */
1219  subplan = create_plan_recurse(root, best_path->subpath, 0);
1220 
1221  tlist = build_path_tlist(root, &best_path->path);
1222 
1223  plan = make_project_set(tlist, subplan);
1224 
1225  copy_generic_path_info(&plan->plan, (Path *) best_path);
1226 
1227  return plan;
1228 }
1229 
1230 /*
1231  * create_material_plan
1232  * Create a Material plan for 'best_path' and (recursively) plans
1233  * for its subpaths.
1234  *
1235  * Returns a Plan node.
1236  */
1237 static Material *
1238 create_material_plan(PlannerInfo *root, MaterialPath *best_path, int flags)
1239 {
1240  Material *plan;
1241  Plan *subplan;
1242 
1243  /*
1244  * We don't want any excess columns in the materialized tuples, so request
1245  * a smaller tlist. Otherwise, since Material doesn't project, tlist
1246  * requirements pass through.
1247  */
1248  subplan = create_plan_recurse(root, best_path->subpath,
1249  flags | CP_SMALL_TLIST);
1250 
1251  plan = make_material(subplan);
1252 
1253  copy_generic_path_info(&plan->plan, (Path *) best_path);
1254 
1255  return plan;
1256 }
1257 
1258 /*
1259  * create_unique_plan
1260  * Create a Unique plan for 'best_path' and (recursively) plans
1261  * for its subpaths.
1262  *
1263  * Returns a Plan node.
1264  */
1265 static Plan *
1266 create_unique_plan(PlannerInfo *root, UniquePath *best_path, int flags)
1267 {
1268  Plan *plan;
1269  Plan *subplan;
1270  List *in_operators;
1271  List *uniq_exprs;
1272  List *newtlist;
1273  int nextresno;
1274  bool newitems;
1275  int numGroupCols;
1276  AttrNumber *groupColIdx;
1277  int groupColPos;
1278  ListCell *l;
1279 
1280  /* Unique doesn't project, so tlist requirements pass through */
1281  subplan = create_plan_recurse(root, best_path->subpath, flags);
1282 
1283  /* Done if we don't need to do any actual unique-ifying */
1284  if (best_path->umethod == UNIQUE_PATH_NOOP)
1285  return subplan;
1286 
1287  /*
1288  * As constructed, the subplan has a "flat" tlist containing just the Vars
1289  * needed here and at upper levels. The values we are supposed to
1290  * unique-ify may be expressions in these variables. We have to add any
1291  * such expressions to the subplan's tlist.
1292  *
1293  * The subplan may have a "physical" tlist if it is a simple scan plan. If
1294  * we're going to sort, this should be reduced to the regular tlist, so
1295  * that we don't sort more data than we need to. For hashing, the tlist
1296  * should be left as-is if we don't need to add any expressions; but if we
1297  * do have to add expressions, then a projection step will be needed at
1298  * runtime anyway, so we may as well remove unneeded items. Therefore
1299  * newtlist starts from build_path_tlist() not just a copy of the
1300  * subplan's tlist; and we don't install it into the subplan unless we are
1301  * sorting or stuff has to be added.
1302  */
1303  in_operators = best_path->in_operators;
1304  uniq_exprs = best_path->uniq_exprs;
1305 
1306  /* initialize modified subplan tlist as just the "required" vars */
1307  newtlist = build_path_tlist(root, &best_path->path);
1308  nextresno = list_length(newtlist) + 1;
1309  newitems = false;
1310 
1311  foreach(l, uniq_exprs)
1312  {
1313  Expr *uniqexpr = lfirst(l);
1314  TargetEntry *tle;
1315 
1316  tle = tlist_member(uniqexpr, newtlist);
1317  if (!tle)
1318  {
1319  tle = makeTargetEntry((Expr *) uniqexpr,
1320  nextresno,
1321  NULL,
1322  false);
1323  newtlist = lappend(newtlist, tle);
1324  nextresno++;
1325  newitems = true;
1326  }
1327  }
1328 
1329  if (newitems || best_path->umethod == UNIQUE_PATH_SORT)
1330  {
1331  /*
1332  * If the top plan node can't do projections and its existing target
1333  * list isn't already what we need, we need to add a Result node to
1334  * help it along.
1335  */
1336  if (!is_projection_capable_plan(subplan) &&
1337  !tlist_same_exprs(newtlist, subplan->targetlist))
1338  subplan = inject_projection_plan(subplan, newtlist,
1339  best_path->path.parallel_safe);
1340  else
1341  subplan->targetlist = newtlist;
1342  }
1343 
1344  /*
1345  * Build control information showing which subplan output columns are to
1346  * be examined by the grouping step. Unfortunately we can't merge this
1347  * with the previous loop, since we didn't then know which version of the
1348  * subplan tlist we'd end up using.
1349  */
1350  newtlist = subplan->targetlist;
1351  numGroupCols = list_length(uniq_exprs);
1352  groupColIdx = (AttrNumber *) palloc(numGroupCols * sizeof(AttrNumber));
1353 
1354  groupColPos = 0;
1355  foreach(l, uniq_exprs)
1356  {
1357  Expr *uniqexpr = lfirst(l);
1358  TargetEntry *tle;
1359 
1360  tle = tlist_member(uniqexpr, newtlist);
1361  if (!tle) /* shouldn't happen */
1362  elog(ERROR, "failed to find unique expression in subplan tlist");
1363  groupColIdx[groupColPos++] = tle->resno;
1364  }
1365 
1366  if (best_path->umethod == UNIQUE_PATH_HASH)
1367  {
1368  Oid *groupOperators;
1369 
1370  /*
1371  * Get the hashable equality operators for the Agg node to use.
1372  * Normally these are the same as the IN clause operators, but if
1373  * those are cross-type operators then the equality operators are the
1374  * ones for the IN clause operators' RHS datatype.
1375  */
1376  groupOperators = (Oid *) palloc(numGroupCols * sizeof(Oid));
1377  groupColPos = 0;
1378  foreach(l, in_operators)
1379  {
1380  Oid in_oper = lfirst_oid(l);
1381  Oid eq_oper;
1382 
1383  if (!get_compatible_hash_operators(in_oper, NULL, &eq_oper))
1384  elog(ERROR, "could not find compatible hash operator for operator %u",
1385  in_oper);
1386  groupOperators[groupColPos++] = eq_oper;
1387  }
1388 
1389  /*
1390  * Since the Agg node is going to project anyway, we can give it the
1391  * minimum output tlist, without any stuff we might have added to the
1392  * subplan tlist.
1393  */
1394  plan = (Plan *) make_agg(build_path_tlist(root, &best_path->path),
1395  NIL,
1396  AGG_HASHED,
1398  numGroupCols,
1399  groupColIdx,
1400  groupOperators,
1401  NIL,
1402  NIL,
1403  best_path->path.rows,
1404  subplan);
1405  }
1406  else
1407  {
1408  List *sortList = NIL;
1409  Sort *sort;
1410 
1411  /* Create an ORDER BY list to sort the input compatibly */
1412  groupColPos = 0;
1413  foreach(l, in_operators)
1414  {
1415  Oid in_oper = lfirst_oid(l);
1416  Oid sortop;
1417  Oid eqop;
1418  TargetEntry *tle;
1419  SortGroupClause *sortcl;
1420 
1421  sortop = get_ordering_op_for_equality_op(in_oper, false);
1422  if (!OidIsValid(sortop)) /* shouldn't happen */
1423  elog(ERROR, "could not find ordering operator for equality operator %u",
1424  in_oper);
1425 
1426  /*
1427  * The Unique node will need equality operators. Normally these
1428  * are the same as the IN clause operators, but if those are
1429  * cross-type operators then the equality operators are the ones
1430  * for the IN clause operators' RHS datatype.
1431  */
1432  eqop = get_equality_op_for_ordering_op(sortop, NULL);
1433  if (!OidIsValid(eqop)) /* shouldn't happen */
1434  elog(ERROR, "could not find equality operator for ordering operator %u",
1435  sortop);
1436 
1437  tle = get_tle_by_resno(subplan->targetlist,
1438  groupColIdx[groupColPos]);
1439  Assert(tle != NULL);
1440 
1441  sortcl = makeNode(SortGroupClause);
1442  sortcl->tleSortGroupRef = assignSortGroupRef(tle,
1443  subplan->targetlist);
1444  sortcl->eqop = eqop;
1445  sortcl->sortop = sortop;
1446  sortcl->nulls_first = false;
1447  sortcl->hashable = false; /* no need to make this accurate */
1448  sortList = lappend(sortList, sortcl);
1449  groupColPos++;
1450  }
1451  sort = make_sort_from_sortclauses(sortList, subplan);
1452  label_sort_with_costsize(root, sort, -1.0);
1453  plan = (Plan *) make_unique_from_sortclauses((Plan *) sort, sortList);
1454  }
1455 
1456  /* Copy cost data from Path to Plan */
1457  copy_generic_path_info(plan, &best_path->path);
1458 
1459  return plan;
1460 }
1461 
1462 /*
1463  * create_gather_plan
1464  *
1465  * Create a Gather plan for 'best_path' and (recursively) plans
1466  * for its subpaths.
1467  */
1468 static Gather *
1470 {
1471  Gather *gather_plan;
1472  Plan *subplan;
1473  List *tlist;
1474 
1475  /*
1476  * Although the Gather node can project, we prefer to push down such work
1477  * to its child node, so demand an exact tlist from the child.
1478  */
1479  subplan = create_plan_recurse(root, best_path->subpath, CP_EXACT_TLIST);
1480 
1481  tlist = build_path_tlist(root, &best_path->path);
1482 
1483  gather_plan = make_gather(tlist,
1484  NIL,
1485  best_path->num_workers,
1487  best_path->single_copy,
1488  subplan);
1489 
1490  copy_generic_path_info(&gather_plan->plan, &best_path->path);
1491 
1492  /* use parallel mode for parallel plans. */
1493  root->glob->parallelModeNeeded = true;
1494 
1495  return gather_plan;
1496 }
1497 
1498 /*
1499  * create_gather_merge_plan
1500  *
1501  * Create a Gather Merge plan for 'best_path' and (recursively)
1502  * plans for its subpaths.
1503  */
1504 static GatherMerge *
1506 {
1507  GatherMerge *gm_plan;
1508  Plan *subplan;
1509  List *pathkeys = best_path->path.pathkeys;
1510  List *tlist = build_path_tlist(root, &best_path->path);
1511 
1512  /* As with Gather, it's best to project away columns in the workers. */
1513  subplan = create_plan_recurse(root, best_path->subpath, CP_EXACT_TLIST);
1514 
1515  /* Create a shell for a GatherMerge plan. */
1516  gm_plan = makeNode(GatherMerge);
1517  gm_plan->plan.targetlist = tlist;
1518  gm_plan->num_workers = best_path->num_workers;
1519  copy_generic_path_info(&gm_plan->plan, &best_path->path);
1520 
1521  /* Assign the rescan Param. */
1522  gm_plan->rescan_param = SS_assign_special_param(root);
1523 
1524  /* Gather Merge is pointless with no pathkeys; use Gather instead. */
1525  Assert(pathkeys != NIL);
1526 
1527  /* Compute sort column info, and adjust subplan's tlist as needed */
1528  subplan = prepare_sort_from_pathkeys(subplan, pathkeys,
1529  best_path->subpath->parent->relids,
1530  gm_plan->sortColIdx,
1531  false,
1532  &gm_plan->numCols,
1533  &gm_plan->sortColIdx,
1534  &gm_plan->sortOperators,
1535  &gm_plan->collations,
1536  &gm_plan->nullsFirst);
1537 
1538 
1539  /* Now, insert a Sort node if subplan isn't sufficiently ordered */
1540  if (!pathkeys_contained_in(pathkeys, best_path->subpath->pathkeys))
1541  subplan = (Plan *) make_sort(subplan, gm_plan->numCols,
1542  gm_plan->sortColIdx,
1543  gm_plan->sortOperators,
1544  gm_plan->collations,
1545  gm_plan->nullsFirst);
1546 
1547  /* Now insert the subplan under GatherMerge. */
1548  gm_plan->plan.lefttree = subplan;
1549 
1550  /* use parallel mode for parallel plans. */
1551  root->glob->parallelModeNeeded = true;
1552 
1553  return gm_plan;
1554 }
1555 
1556 /*
1557  * create_projection_plan
1558  *
1559  * Create a plan tree to do a projection step and (recursively) plans
1560  * for its subpaths. We may need a Result node for the projection,
1561  * but sometimes we can just let the subplan do the work.
1562  */
1563 static Plan *
1565 {
1566  Plan *plan;
1567  Plan *subplan;
1568  List *tlist;
1569 
1570  /* Since we intend to project, we don't need to constrain child tlist */
1571  subplan = create_plan_recurse(root, best_path->subpath, 0);
1572 
1573  tlist = build_path_tlist(root, &best_path->path);
1574 
1575  /*
1576  * We might not really need a Result node here, either because the subplan
1577  * can project or because it's returning the right list of expressions
1578  * anyway. Usually create_projection_path will have detected that and set
1579  * dummypp if we don't need a Result; but its decision can't be final,
1580  * because some createplan.c routines change the tlists of their nodes.
1581  * (An example is that create_merge_append_plan might add resjunk sort
1582  * columns to a MergeAppend.) So we have to recheck here. If we do
1583  * arrive at a different answer than create_projection_path did, we'll
1584  * have made slightly wrong cost estimates; but label the plan with the
1585  * cost estimates we actually used, not "corrected" ones. (XXX this could
1586  * be cleaned up if we moved more of the sortcolumn setup logic into Path
1587  * creation, but that would add expense to creating Paths we might end up
1588  * not using.)
1589  */
1590  if (is_projection_capable_path(best_path->subpath) ||
1591  tlist_same_exprs(tlist, subplan->targetlist))
1592  {
1593  /* Don't need a separate Result, just assign tlist to subplan */
1594  plan = subplan;
1595  plan->targetlist = tlist;
1596 
1597  /* Label plan with the estimated costs we actually used */
1598  plan->startup_cost = best_path->path.startup_cost;
1599  plan->total_cost = best_path->path.total_cost;
1600  plan->plan_rows = best_path->path.rows;
1601  plan->plan_width = best_path->path.pathtarget->width;
1602  plan->parallel_safe = best_path->path.parallel_safe;
1603  /* ... but don't change subplan's parallel_aware flag */
1604  }
1605  else
1606  {
1607  /* We need a Result node */
1608  plan = (Plan *) make_result(tlist, NULL, subplan);
1609 
1610  copy_generic_path_info(plan, (Path *) best_path);
1611  }
1612 
1613  return plan;
1614 }
1615 
1616 /*
1617  * inject_projection_plan
1618  * Insert a Result node to do a projection step.
1619  *
1620  * This is used in a few places where we decide on-the-fly that we need a
1621  * projection step as part of the tree generated for some Path node.
1622  * We should try to get rid of this in favor of doing it more honestly.
1623  *
1624  * One reason it's ugly is we have to be told the right parallel_safe marking
1625  * to apply (since the tlist might be unsafe even if the child plan is safe).
1626  */
1627 static Plan *
1628 inject_projection_plan(Plan *subplan, List *tlist, bool parallel_safe)
1629 {
1630  Plan *plan;
1631 
1632  plan = (Plan *) make_result(tlist, NULL, subplan);
1633 
1634  /*
1635  * In principle, we should charge tlist eval cost plus cpu_per_tuple per
1636  * row for the Result node. But the former has probably been factored in
1637  * already and the latter was not accounted for during Path construction,
1638  * so being formally correct might just make the EXPLAIN output look less
1639  * consistent not more so. Hence, just copy the subplan's cost.
1640  */
1641  copy_plan_costsize(plan, subplan);
1642  plan->parallel_safe = parallel_safe;
1643 
1644  return plan;
1645 }
1646 
1647 /*
1648  * create_sort_plan
1649  *
1650  * Create a Sort plan for 'best_path' and (recursively) plans
1651  * for its subpaths.
1652  */
1653 static Sort *
1654 create_sort_plan(PlannerInfo *root, SortPath *best_path, int flags)
1655 {
1656  Sort *plan;
1657  Plan *subplan;
1658 
1659  /*
1660  * We don't want any excess columns in the sorted tuples, so request a
1661  * smaller tlist. Otherwise, since Sort doesn't project, tlist
1662  * requirements pass through.
1663  */
1664  subplan = create_plan_recurse(root, best_path->subpath,
1665  flags | CP_SMALL_TLIST);
1666 
1667  plan = make_sort_from_pathkeys(subplan, best_path->path.pathkeys, NULL);
1668 
1669  copy_generic_path_info(&plan->plan, (Path *) best_path);
1670 
1671  return plan;
1672 }
1673 
1674 /*
1675  * create_group_plan
1676  *
1677  * Create a Group plan for 'best_path' and (recursively) plans
1678  * for its subpaths.
1679  */
1680 static Group *
1682 {
1683  Group *plan;
1684  Plan *subplan;
1685  List *tlist;
1686  List *quals;
1687 
1688  /*
1689  * Group can project, so no need to be terribly picky about child tlist,
1690  * but we do need grouping columns to be available
1691  */
1692  subplan = create_plan_recurse(root, best_path->subpath, CP_LABEL_TLIST);
1693 
1694  tlist = build_path_tlist(root, &best_path->path);
1695 
1696  quals = order_qual_clauses(root, best_path->qual);
1697 
1698  plan = make_group(tlist,
1699  quals,
1700  list_length(best_path->groupClause),
1702  subplan->targetlist),
1703  extract_grouping_ops(best_path->groupClause),
1704  subplan);
1705 
1706  copy_generic_path_info(&plan->plan, (Path *) best_path);
1707 
1708  return plan;
1709 }
1710 
1711 /*
1712  * create_upper_unique_plan
1713  *
1714  * Create a Unique plan for 'best_path' and (recursively) plans
1715  * for its subpaths.
1716  */
1717 static Unique *
1719 {
1720  Unique *plan;
1721  Plan *subplan;
1722 
1723  /*
1724  * Unique doesn't project, so tlist requirements pass through; moreover we
1725  * need grouping columns to be labeled.
1726  */
1727  subplan = create_plan_recurse(root, best_path->subpath,
1728  flags | CP_LABEL_TLIST);
1729 
1730  plan = make_unique_from_pathkeys(subplan,
1731  best_path->path.pathkeys,
1732  best_path->numkeys);
1733 
1734  copy_generic_path_info(&plan->plan, (Path *) best_path);
1735 
1736  return plan;
1737 }
1738 
1739 /*
1740  * create_agg_plan
1741  *
1742  * Create an Agg plan for 'best_path' and (recursively) plans
1743  * for its subpaths.
1744  */
1745 static Agg *
1747 {
1748  Agg *plan;
1749  Plan *subplan;
1750  List *tlist;
1751  List *quals;
1752 
1753  /*
1754  * Agg can project, so no need to be terribly picky about child tlist, but
1755  * we do need grouping columns to be available
1756  */
1757  subplan = create_plan_recurse(root, best_path->subpath, CP_LABEL_TLIST);
1758 
1759  tlist = build_path_tlist(root, &best_path->path);
1760 
1761  quals = order_qual_clauses(root, best_path->qual);
1762 
1763  plan = make_agg(tlist, quals,
1764  best_path->aggstrategy,
1765  best_path->aggsplit,
1766  list_length(best_path->groupClause),
1768  subplan->targetlist),
1769  extract_grouping_ops(best_path->groupClause),
1770  NIL,
1771  NIL,
1772  best_path->numGroups,
1773  subplan);
1774 
1775  copy_generic_path_info(&plan->plan, (Path *) best_path);
1776 
1777  return plan;
1778 }
1779 
1780 /*
1781  * Given a groupclause for a collection of grouping sets, produce the
1782  * corresponding groupColIdx.
1783  *
1784  * root->grouping_map maps the tleSortGroupRef to the actual column position in
1785  * the input tuple. So we get the ref from the entries in the groupclause and
1786  * look them up there.
1787  */
1788 static AttrNumber *
1789 remap_groupColIdx(PlannerInfo *root, List *groupClause)
1790 {
1791  AttrNumber *grouping_map = root->grouping_map;
1792  AttrNumber *new_grpColIdx;
1793  ListCell *lc;
1794  int i;
1795 
1796  Assert(grouping_map);
1797 
1798  new_grpColIdx = palloc0(sizeof(AttrNumber) * list_length(groupClause));
1799 
1800  i = 0;
1801  foreach(lc, groupClause)
1802  {
1803  SortGroupClause *clause = lfirst(lc);
1804 
1805  new_grpColIdx[i++] = grouping_map[clause->tleSortGroupRef];
1806  }
1807 
1808  return new_grpColIdx;
1809 }
1810 
1811 /*
1812  * create_groupingsets_plan
1813  * Create a plan for 'best_path' and (recursively) plans
1814  * for its subpaths.
1815  *
1816  * What we emit is an Agg plan with some vestigial Agg and Sort nodes
1817  * hanging off the side. The top Agg implements the last grouping set
1818  * specified in the GroupingSetsPath, and any additional grouping sets
1819  * each give rise to a subsidiary Agg and Sort node in the top Agg's
1820  * "chain" list. These nodes don't participate in the plan directly,
1821  * but they are a convenient way to represent the required data for
1822  * the extra steps.
1823  *
1824  * Returns a Plan node.
1825  */
1826 static Plan *
1828 {
1829  Agg *plan;
1830  Plan *subplan;
1831  List *rollups = best_path->rollups;
1832  AttrNumber *grouping_map;
1833  int maxref;
1834  List *chain;
1835  ListCell *lc;
1836 
1837  /* Shouldn't get here without grouping sets */
1838  Assert(root->parse->groupingSets);
1839  Assert(rollups != NIL);
1840 
1841  /*
1842  * Agg can project, so no need to be terribly picky about child tlist, but
1843  * we do need grouping columns to be available
1844  */
1845  subplan = create_plan_recurse(root, best_path->subpath, CP_LABEL_TLIST);
1846 
1847  /*
1848  * Compute the mapping from tleSortGroupRef to column index in the child's
1849  * tlist. First, identify max SortGroupRef in groupClause, for array
1850  * sizing.
1851  */
1852  maxref = 0;
1853  foreach(lc, root->parse->groupClause)
1854  {
1855  SortGroupClause *gc = (SortGroupClause *) lfirst(lc);
1856 
1857  if (gc->tleSortGroupRef > maxref)
1858  maxref = gc->tleSortGroupRef;
1859  }
1860 
1861  grouping_map = (AttrNumber *) palloc0((maxref + 1) * sizeof(AttrNumber));
1862 
1863  /* Now look up the column numbers in the child's tlist */
1864  foreach(lc, root->parse->groupClause)
1865  {
1866  SortGroupClause *gc = (SortGroupClause *) lfirst(lc);
1867  TargetEntry *tle = get_sortgroupclause_tle(gc, subplan->targetlist);
1868 
1869  grouping_map[gc->tleSortGroupRef] = tle->resno;
1870  }
1871 
1872  /*
1873  * During setrefs.c, we'll need the grouping_map to fix up the cols lists
1874  * in GroupingFunc nodes. Save it for setrefs.c to use.
1875  *
1876  * This doesn't work if we're in an inheritance subtree (see notes in
1877  * create_modifytable_plan). Fortunately we can't be because there would
1878  * never be grouping in an UPDATE/DELETE; but let's Assert that.
1879  */
1880  Assert(!root->hasInheritedTarget);
1881  Assert(root->grouping_map == NULL);
1882  root->grouping_map = grouping_map;
1883 
1884  /*
1885  * Generate the side nodes that describe the other sort and group
1886  * operations besides the top one. Note that we don't worry about putting
1887  * accurate cost estimates in the side nodes; only the topmost Agg node's
1888  * costs will be shown by EXPLAIN.
1889  */
1890  chain = NIL;
1891  if (list_length(rollups) > 1)
1892  {
1893  ListCell *lc2 = lnext(list_head(rollups));
1894  bool is_first_sort = ((RollupData *) linitial(rollups))->is_hashed;
1895 
1896  for_each_cell(lc, lc2)
1897  {
1898  RollupData *rollup = lfirst(lc);
1899  AttrNumber *new_grpColIdx;
1900  Plan *sort_plan = NULL;
1901  Plan *agg_plan;
1902  AggStrategy strat;
1903 
1904  new_grpColIdx = remap_groupColIdx(root, rollup->groupClause);
1905 
1906  if (!rollup->is_hashed && !is_first_sort)
1907  {
1908  sort_plan = (Plan *)
1910  new_grpColIdx,
1911  subplan);
1912  }
1913 
1914  if (!rollup->is_hashed)
1915  is_first_sort = false;
1916 
1917  if (rollup->is_hashed)
1918  strat = AGG_HASHED;
1919  else if (list_length(linitial(rollup->gsets)) == 0)
1920  strat = AGG_PLAIN;
1921  else
1922  strat = AGG_SORTED;
1923 
1924  agg_plan = (Plan *) make_agg(NIL,
1925  NIL,
1926  strat,
1928  list_length((List *) linitial(rollup->gsets)),
1929  new_grpColIdx,
1931  rollup->gsets,
1932  NIL,
1933  rollup->numGroups,
1934  sort_plan);
1935 
1936  /*
1937  * Remove stuff we don't need to avoid bloating debug output.
1938  */
1939  if (sort_plan)
1940  {
1941  sort_plan->targetlist = NIL;
1942  sort_plan->lefttree = NULL;
1943  }
1944 
1945  chain = lappend(chain, agg_plan);
1946  }
1947  }
1948 
1949  /*
1950  * Now make the real Agg node
1951  */
1952  {
1953  RollupData *rollup = linitial(rollups);
1954  AttrNumber *top_grpColIdx;
1955  int numGroupCols;
1956 
1957  top_grpColIdx = remap_groupColIdx(root, rollup->groupClause);
1958 
1959  numGroupCols = list_length((List *) linitial(rollup->gsets));
1960 
1961  plan = make_agg(build_path_tlist(root, &best_path->path),
1962  best_path->qual,
1963  best_path->aggstrategy,
1965  numGroupCols,
1966  top_grpColIdx,
1968  rollup->gsets,
1969  chain,
1970  rollup->numGroups,
1971  subplan);
1972 
1973  /* Copy cost data from Path to Plan */
1974  copy_generic_path_info(&plan->plan, &best_path->path);
1975  }
1976 
1977  return (Plan *) plan;
1978 }
1979 
1980 /*
1981  * create_minmaxagg_plan
1982  *
1983  * Create a Result plan for 'best_path' and (recursively) plans
1984  * for its subpaths.
1985  */
1986 static Result *
1988 {
1989  Result *plan;
1990  List *tlist;
1991  ListCell *lc;
1992 
1993  /* Prepare an InitPlan for each aggregate's subquery. */
1994  foreach(lc, best_path->mmaggregates)
1995  {
1996  MinMaxAggInfo *mminfo = (MinMaxAggInfo *) lfirst(lc);
1997  PlannerInfo *subroot = mminfo->subroot;
1998  Query *subparse = subroot->parse;
1999  Plan *plan;
2000 
2001  /*
2002  * Generate the plan for the subquery. We already have a Path, but we
2003  * have to convert it to a Plan and attach a LIMIT node above it.
2004  * Since we are entering a different planner context (subroot),
2005  * recurse to create_plan not create_plan_recurse.
2006  */
2007  plan = create_plan(subroot, mminfo->path);
2008 
2009  plan = (Plan *) make_limit(plan,
2010  subparse->limitOffset,
2011  subparse->limitCount);
2012 
2013  /* Must apply correct cost/width data to Limit node */
2014  plan->startup_cost = mminfo->path->startup_cost;
2015  plan->total_cost = mminfo->pathcost;
2016  plan->plan_rows = 1;
2017  plan->plan_width = mminfo->path->pathtarget->width;
2018  plan->parallel_aware = false;
2019  plan->parallel_safe = mminfo->path->parallel_safe;
2020 
2021  /* Convert the plan into an InitPlan in the outer query. */
2022  SS_make_initplan_from_plan(root, subroot, plan, mminfo->param);
2023  }
2024 
2025  /* Generate the output plan --- basically just a Result */
2026  tlist = build_path_tlist(root, &best_path->path);
2027 
2028  plan = make_result(tlist, (Node *) best_path->quals, NULL);
2029 
2030  copy_generic_path_info(&plan->plan, (Path *) best_path);
2031 
2032  /*
2033  * During setrefs.c, we'll need to replace references to the Agg nodes
2034  * with InitPlan output params. (We can't just do that locally in the
2035  * MinMaxAgg node, because path nodes above here may have Agg references
2036  * as well.) Save the mmaggregates list to tell setrefs.c to do that.
2037  *
2038  * This doesn't work if we're in an inheritance subtree (see notes in
2039  * create_modifytable_plan). Fortunately we can't be because there would
2040  * never be aggregates in an UPDATE/DELETE; but let's Assert that.
2041  */
2042  Assert(!root->hasInheritedTarget);
2043  Assert(root->minmax_aggs == NIL);
2044  root->minmax_aggs = best_path->mmaggregates;
2045 
2046  return plan;
2047 }
2048 
2049 /*
2050  * create_windowagg_plan
2051  *
2052  * Create a WindowAgg plan for 'best_path' and (recursively) plans
2053  * for its subpaths.
2054  */
2055 static WindowAgg *
2057 {
2058  WindowAgg *plan;
2059  WindowClause *wc = best_path->winclause;
2060  Plan *subplan;
2061  List *tlist;
2062  int numsortkeys;
2063  AttrNumber *sortColIdx;
2064  Oid *sortOperators;
2065  Oid *collations;
2066  bool *nullsFirst;
2067  int partNumCols;
2068  AttrNumber *partColIdx;
2069  Oid *partOperators;
2070  int ordNumCols;
2071  AttrNumber *ordColIdx;
2072  Oid *ordOperators;
2073 
2074  /*
2075  * WindowAgg can project, so no need to be terribly picky about child
2076  * tlist, but we do need grouping columns to be available
2077  */
2078  subplan = create_plan_recurse(root, best_path->subpath, CP_LABEL_TLIST);
2079 
2080  tlist = build_path_tlist(root, &best_path->path);
2081 
2082  /*
2083  * We shouldn't need to actually sort, but it's convenient to use
2084  * prepare_sort_from_pathkeys to identify the input's sort columns.
2085  */
2086  subplan = prepare_sort_from_pathkeys(subplan,
2087  best_path->winpathkeys,
2088  NULL,
2089  NULL,
2090  false,
2091  &numsortkeys,
2092  &sortColIdx,
2093  &sortOperators,
2094  &collations,
2095  &nullsFirst);
2096 
2097  /* Now deconstruct that into partition and ordering portions */
2099  wc,
2100  subplan->targetlist,
2101  numsortkeys,
2102  sortColIdx,
2103  &partNumCols,
2104  &partColIdx,
2105  &partOperators,
2106  &ordNumCols,
2107  &ordColIdx,
2108  &ordOperators);
2109 
2110  /* And finally we can make the WindowAgg node */
2111  plan = make_windowagg(tlist,
2112  wc->winref,
2113  partNumCols,
2114  partColIdx,
2115  partOperators,
2116  ordNumCols,
2117  ordColIdx,
2118  ordOperators,
2119  wc->frameOptions,
2120  wc->startOffset,
2121  wc->endOffset,
2122  subplan);
2123 
2124  copy_generic_path_info(&plan->plan, (Path *) best_path);
2125 
2126  return plan;
2127 }
2128 
2129 /*
2130  * get_column_info_for_window
2131  * Get the partitioning/ordering column numbers and equality operators
2132  * for a WindowAgg node.
2133  *
2134  * This depends on the behavior of planner.c's make_pathkeys_for_window!
2135  *
2136  * We are given the target WindowClause and an array of the input column
2137  * numbers associated with the resulting pathkeys. In the easy case, there
2138  * are the same number of pathkey columns as partitioning + ordering columns
2139  * and we just have to copy some data around. However, it's possible that
2140  * some of the original partitioning + ordering columns were eliminated as
2141  * redundant during the transformation to pathkeys. (This can happen even
2142  * though the parser gets rid of obvious duplicates. A typical scenario is a
2143  * window specification "PARTITION BY x ORDER BY y" coupled with a clause
2144  * "WHERE x = y" that causes the two sort columns to be recognized as
2145  * redundant.) In that unusual case, we have to work a lot harder to
2146  * determine which keys are significant.
2147  *
2148  * The method used here is a bit brute-force: add the sort columns to a list
2149  * one at a time and note when the resulting pathkey list gets longer. But
2150  * it's a sufficiently uncommon case that a faster way doesn't seem worth
2151  * the amount of code refactoring that'd be needed.
2152  */
2153 static void
2155  int numSortCols, AttrNumber *sortColIdx,
2156  int *partNumCols,
2157  AttrNumber **partColIdx,
2158  Oid **partOperators,
2159  int *ordNumCols,
2160  AttrNumber **ordColIdx,
2161  Oid **ordOperators)
2162 {
2163  int numPart = list_length(wc->partitionClause);
2164  int numOrder = list_length(wc->orderClause);
2165 
2166  if (numSortCols == numPart + numOrder)
2167  {
2168  /* easy case */
2169  *partNumCols = numPart;
2170  *partColIdx = sortColIdx;
2171  *partOperators = extract_grouping_ops(wc->partitionClause);
2172  *ordNumCols = numOrder;
2173  *ordColIdx = sortColIdx + numPart;
2174  *ordOperators = extract_grouping_ops(wc->orderClause);
2175  }
2176  else
2177  {
2178  List *sortclauses;
2179  List *pathkeys;
2180  int scidx;
2181  ListCell *lc;
2182 
2183  /* first, allocate what's certainly enough space for the arrays */
2184  *partNumCols = 0;
2185  *partColIdx = (AttrNumber *) palloc(numPart * sizeof(AttrNumber));
2186  *partOperators = (Oid *) palloc(numPart * sizeof(Oid));
2187  *ordNumCols = 0;
2188  *ordColIdx = (AttrNumber *) palloc(numOrder * sizeof(AttrNumber));
2189  *ordOperators = (Oid *) palloc(numOrder * sizeof(Oid));
2190  sortclauses = NIL;
2191  pathkeys = NIL;
2192  scidx = 0;
2193  foreach(lc, wc->partitionClause)
2194  {
2195  SortGroupClause *sgc = (SortGroupClause *) lfirst(lc);
2196  List *new_pathkeys;
2197 
2198  sortclauses = lappend(sortclauses, sgc);
2199  new_pathkeys = make_pathkeys_for_sortclauses(root,
2200  sortclauses,
2201  tlist);
2202  if (list_length(new_pathkeys) > list_length(pathkeys))
2203  {
2204  /* this sort clause is actually significant */
2205  (*partColIdx)[*partNumCols] = sortColIdx[scidx++];
2206  (*partOperators)[*partNumCols] = sgc->eqop;
2207  (*partNumCols)++;
2208  pathkeys = new_pathkeys;
2209  }
2210  }
2211  foreach(lc, wc->orderClause)
2212  {
2213  SortGroupClause *sgc = (SortGroupClause *) lfirst(lc);
2214  List *new_pathkeys;
2215 
2216  sortclauses = lappend(sortclauses, sgc);
2217  new_pathkeys = make_pathkeys_for_sortclauses(root,
2218  sortclauses,
2219  tlist);
2220  if (list_length(new_pathkeys) > list_length(pathkeys))
2221  {
2222  /* this sort clause is actually significant */
2223  (*ordColIdx)[*ordNumCols] = sortColIdx[scidx++];
2224  (*ordOperators)[*ordNumCols] = sgc->eqop;
2225  (*ordNumCols)++;
2226  pathkeys = new_pathkeys;
2227  }
2228  }
2229  /* complain if we didn't eat exactly the right number of sort cols */
2230  if (scidx != numSortCols)
2231  elog(ERROR, "failed to deconstruct sort operators into partitioning/ordering operators");
2232  }
2233 }
2234 
2235 /*
2236  * create_setop_plan
2237  *
2238  * Create a SetOp plan for 'best_path' and (recursively) plans
2239  * for its subpaths.
2240  */
2241 static SetOp *
2242 create_setop_plan(PlannerInfo *root, SetOpPath *best_path, int flags)
2243 {
2244  SetOp *plan;
2245  Plan *subplan;
2246  long numGroups;
2247 
2248  /*
2249  * SetOp doesn't project, so tlist requirements pass through; moreover we
2250  * need grouping columns to be labeled.
2251  */
2252  subplan = create_plan_recurse(root, best_path->subpath,
2253  flags | CP_LABEL_TLIST);
2254 
2255  /* Convert numGroups to long int --- but 'ware overflow! */
2256  numGroups = (long) Min(best_path->numGroups, (double) LONG_MAX);
2257 
2258  plan = make_setop(best_path->cmd,
2259  best_path->strategy,
2260  subplan,
2261  best_path->distinctList,
2262  best_path->flagColIdx,
2263  best_path->firstFlag,
2264  numGroups);
2265 
2266  copy_generic_path_info(&plan->plan, (Path *) best_path);
2267 
2268  return plan;
2269 }
2270 
2271 /*
2272  * create_recursiveunion_plan
2273  *
2274  * Create a RecursiveUnion plan for 'best_path' and (recursively) plans
2275  * for its subpaths.
2276  */
2277 static RecursiveUnion *
2279 {
2280  RecursiveUnion *plan;
2281  Plan *leftplan;
2282  Plan *rightplan;
2283  List *tlist;
2284  long numGroups;
2285 
2286  /* Need both children to produce same tlist, so force it */
2287  leftplan = create_plan_recurse(root, best_path->leftpath, CP_EXACT_TLIST);
2288  rightplan = create_plan_recurse(root, best_path->rightpath, CP_EXACT_TLIST);
2289 
2290  tlist = build_path_tlist(root, &best_path->path);
2291 
2292  /* Convert numGroups to long int --- but 'ware overflow! */
2293  numGroups = (long) Min(best_path->numGroups, (double) LONG_MAX);
2294 
2295  plan = make_recursive_union(tlist,
2296  leftplan,
2297  rightplan,
2298  best_path->wtParam,
2299  best_path->distinctList,
2300  numGroups);
2301 
2302  copy_generic_path_info(&plan->plan, (Path *) best_path);
2303 
2304  return plan;
2305 }
2306 
2307 /*
2308  * create_lockrows_plan
2309  *
2310  * Create a LockRows plan for 'best_path' and (recursively) plans
2311  * for its subpaths.
2312  */
2313 static LockRows *
2315  int flags)
2316 {
2317  LockRows *plan;
2318  Plan *subplan;
2319 
2320  /* LockRows doesn't project, so tlist requirements pass through */
2321  subplan = create_plan_recurse(root, best_path->subpath, flags);
2322 
2323  plan = make_lockrows(subplan, best_path->rowMarks, best_path->epqParam);
2324 
2325  copy_generic_path_info(&plan->plan, (Path *) best_path);
2326 
2327  return plan;
2328 }
2329 
2330 /*
2331  * create_modifytable_plan
2332  * Create a ModifyTable plan for 'best_path'.
2333  *
2334  * Returns a Plan node.
2335  */
2336 static ModifyTable *
2338 {
2339  ModifyTable *plan;
2340  List *subplans = NIL;
2341  ListCell *subpaths,
2342  *subroots;
2343 
2344  /* Build the plan for each input path */
2345  forboth(subpaths, best_path->subpaths,
2346  subroots, best_path->subroots)
2347  {
2348  Path *subpath = (Path *) lfirst(subpaths);
2349  PlannerInfo *subroot = (PlannerInfo *) lfirst(subroots);
2350  Plan *subplan;
2351 
2352  /*
2353  * In an inherited UPDATE/DELETE, reference the per-child modified
2354  * subroot while creating Plans from Paths for the child rel. This is
2355  * a kluge, but otherwise it's too hard to ensure that Plan creation
2356  * functions (particularly in FDWs) don't depend on the contents of
2357  * "root" matching what they saw at Path creation time. The main
2358  * downside is that creation functions for Plans that might appear
2359  * below a ModifyTable cannot expect to modify the contents of "root"
2360  * and have it "stick" for subsequent processing such as setrefs.c.
2361  * That's not great, but it seems better than the alternative.
2362  */
2363  subplan = create_plan_recurse(subroot, subpath, CP_EXACT_TLIST);
2364 
2365  /* Transfer resname/resjunk labeling, too, to keep executor happy */
2366  apply_tlist_labeling(subplan->targetlist, subroot->processed_tlist);
2367 
2368  subplans = lappend(subplans, subplan);
2369  }
2370 
2371  plan = make_modifytable(root,
2372  best_path->operation,
2373  best_path->canSetTag,
2374  best_path->nominalRelation,
2375  best_path->partitioned_rels,
2376  best_path->resultRelations,
2377  subplans,
2378  best_path->withCheckOptionLists,
2379  best_path->returningLists,
2380  best_path->rowMarks,
2381  best_path->onconflict,
2382  best_path->epqParam);
2383 
2384  copy_generic_path_info(&plan->plan, &best_path->path);
2385 
2386  return plan;
2387 }
2388 
2389 /*
2390  * create_limit_plan
2391  *
2392  * Create a Limit plan for 'best_path' and (recursively) plans
2393  * for its subpaths.
2394  */
2395 static Limit *
2396 create_limit_plan(PlannerInfo *root, LimitPath *best_path, int flags)
2397 {
2398  Limit *plan;
2399  Plan *subplan;
2400 
2401  /* Limit doesn't project, so tlist requirements pass through */
2402  subplan = create_plan_recurse(root, best_path->subpath, flags);
2403 
2404  plan = make_limit(subplan,
2405  best_path->limitOffset,
2406  best_path->limitCount);
2407 
2408  copy_generic_path_info(&plan->plan, (Path *) best_path);
2409 
2410  return plan;
2411 }
2412 
2413 
2414 /*****************************************************************************
2415  *
2416  * BASE-RELATION SCAN METHODS
2417  *
2418  *****************************************************************************/
2419 
2420 
2421 /*
2422  * create_seqscan_plan
2423  * Returns a seqscan plan for the base relation scanned by 'best_path'
2424  * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
2425  */
2426 static SeqScan *
2428  List *tlist, List *scan_clauses)
2429 {
2430  SeqScan *scan_plan;
2431  Index scan_relid = best_path->parent->relid;
2432 
2433  /* it should be a base rel... */
2434  Assert(scan_relid > 0);
2435  Assert(best_path->parent->rtekind == RTE_RELATION);
2436 
2437  /* Sort clauses into best execution order */
2438  scan_clauses = order_qual_clauses(root, scan_clauses);
2439 
2440  /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
2441  scan_clauses = extract_actual_clauses(scan_clauses, false);
2442 
2443  /* Replace any outer-relation variables with nestloop params */
2444  if (best_path->param_info)
2445  {
2446  scan_clauses = (List *)
2447  replace_nestloop_params(root, (Node *) scan_clauses);
2448  }
2449 
2450  scan_plan = make_seqscan(tlist,
2451  scan_clauses,
2452  scan_relid);
2453 
2454  copy_generic_path_info(&scan_plan->plan, best_path);
2455 
2456  return scan_plan;
2457 }
2458 
2459 /*
2460  * create_samplescan_plan
2461  * Returns a samplescan plan for the base relation scanned by 'best_path'
2462  * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
2463  */
2464 static SampleScan *
2466  List *tlist, List *scan_clauses)
2467 {
2468  SampleScan *scan_plan;
2469  Index scan_relid = best_path->parent->relid;
2470  RangeTblEntry *rte;
2471  TableSampleClause *tsc;
2472 
2473  /* it should be a base rel with a tablesample clause... */
2474  Assert(scan_relid > 0);
2475  rte = planner_rt_fetch(scan_relid, root);
2476  Assert(rte->rtekind == RTE_RELATION);
2477  tsc = rte->tablesample;
2478  Assert(tsc != NULL);
2479 
2480  /* Sort clauses into best execution order */
2481  scan_clauses = order_qual_clauses(root, scan_clauses);
2482 
2483  /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
2484  scan_clauses = extract_actual_clauses(scan_clauses, false);
2485 
2486  /* Replace any outer-relation variables with nestloop params */
2487  if (best_path->param_info)
2488  {
2489  scan_clauses = (List *)
2490  replace_nestloop_params(root, (Node *) scan_clauses);
2491  tsc = (TableSampleClause *)
2492  replace_nestloop_params(root, (Node *) tsc);
2493  }
2494 
2495  scan_plan = make_samplescan(tlist,
2496  scan_clauses,
2497  scan_relid,
2498  tsc);
2499 
2500  copy_generic_path_info(&scan_plan->scan.plan, best_path);
2501 
2502  return scan_plan;
2503 }
2504 
2505 /*
2506  * create_indexscan_plan
2507  * Returns an indexscan plan for the base relation scanned by 'best_path'
2508  * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
2509  *
2510  * We use this for both plain IndexScans and IndexOnlyScans, because the
2511  * qual preprocessing work is the same for both. Note that the caller tells
2512  * us which to build --- we don't look at best_path->path.pathtype, because
2513  * create_bitmap_subplan needs to be able to override the prior decision.
2514  */
2515 static Scan *
2517  IndexPath *best_path,
2518  List *tlist,
2519  List *scan_clauses,
2520  bool indexonly)
2521 {
2522  Scan *scan_plan;
2523  List *indexquals = best_path->indexquals;
2524  List *indexorderbys = best_path->indexorderbys;
2525  Index baserelid = best_path->path.parent->relid;
2526  Oid indexoid = best_path->indexinfo->indexoid;
2527  List *qpqual;
2528  List *stripped_indexquals;
2529  List *fixed_indexquals;
2530  List *fixed_indexorderbys;
2531  List *indexorderbyops = NIL;
2532  ListCell *l;
2533 
2534  /* it should be a base rel... */
2535  Assert(baserelid > 0);
2536  Assert(best_path->path.parent->rtekind == RTE_RELATION);
2537 
2538  /*
2539  * Build "stripped" indexquals structure (no RestrictInfos) to pass to
2540  * executor as indexqualorig
2541  */
2542  stripped_indexquals = get_actual_clauses(indexquals);
2543 
2544  /*
2545  * The executor needs a copy with the indexkey on the left of each clause
2546  * and with index Vars substituted for table ones.
2547  */
2548  fixed_indexquals = fix_indexqual_references(root, best_path);
2549 
2550  /*
2551  * Likewise fix up index attr references in the ORDER BY expressions.
2552  */
2553  fixed_indexorderbys = fix_indexorderby_references(root, best_path);
2554 
2555  /*
2556  * The qpqual list must contain all restrictions not automatically handled
2557  * by the index, other than pseudoconstant clauses which will be handled
2558  * by a separate gating plan node. All the predicates in the indexquals
2559  * will be checked (either by the index itself, or by nodeIndexscan.c),
2560  * but if there are any "special" operators involved then they must be
2561  * included in qpqual. The upshot is that qpqual must contain
2562  * scan_clauses minus whatever appears in indexquals.
2563  *
2564  * In normal cases simple pointer equality checks will be enough to spot
2565  * duplicate RestrictInfos, so we try that first.
2566  *
2567  * Another common case is that a scan_clauses entry is generated from the
2568  * same EquivalenceClass as some indexqual, and is therefore redundant
2569  * with it, though not equal. (This happens when indxpath.c prefers a
2570  * different derived equality than what generate_join_implied_equalities
2571  * picked for a parameterized scan's ppi_clauses.)
2572  *
2573  * In some situations (particularly with OR'd index conditions) we may
2574  * have scan_clauses that are not equal to, but are logically implied by,
2575  * the index quals; so we also try a predicate_implied_by() check to see
2576  * if we can discard quals that way. (predicate_implied_by assumes its
2577  * first input contains only immutable functions, so we have to check
2578  * that.)
2579  *
2580  * Note: if you change this bit of code you should also look at
2581  * extract_nonindex_conditions() in costsize.c.
2582  */
2583  qpqual = NIL;
2584  foreach(l, scan_clauses)
2585  {
2586  RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
2587 
2588  if (rinfo->pseudoconstant)
2589  continue; /* we may drop pseudoconstants here */
2590  if (list_member_ptr(indexquals, rinfo))
2591  continue; /* simple duplicate */
2592  if (is_redundant_derived_clause(rinfo, indexquals))
2593  continue; /* derived from same EquivalenceClass */
2594  if (!contain_mutable_functions((Node *) rinfo->clause) &&
2595  predicate_implied_by(list_make1(rinfo->clause), indexquals, false))
2596  continue; /* provably implied by indexquals */
2597  qpqual = lappend(qpqual, rinfo);
2598  }
2599 
2600  /* Sort clauses into best execution order */
2601  qpqual = order_qual_clauses(root, qpqual);
2602 
2603  /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
2604  qpqual = extract_actual_clauses(qpqual, false);
2605 
2606  /*
2607  * We have to replace any outer-relation variables with nestloop params in
2608  * the indexqualorig, qpqual, and indexorderbyorig expressions. A bit
2609  * annoying to have to do this separately from the processing in
2610  * fix_indexqual_references --- rethink this when generalizing the inner
2611  * indexscan support. But note we can't really do this earlier because
2612  * it'd break the comparisons to predicates above ... (or would it? Those
2613  * wouldn't have outer refs)
2614  */
2615  if (best_path->path.param_info)
2616  {
2617  stripped_indexquals = (List *)
2618  replace_nestloop_params(root, (Node *) stripped_indexquals);
2619  qpqual = (List *)
2620  replace_nestloop_params(root, (Node *) qpqual);
2621  indexorderbys = (List *)
2622  replace_nestloop_params(root, (Node *) indexorderbys);
2623  }
2624 
2625  /*
2626  * If there are ORDER BY expressions, look up the sort operators for their
2627  * result datatypes.
2628  */
2629  if (indexorderbys)
2630  {
2631  ListCell *pathkeyCell,
2632  *exprCell;
2633 
2634  /*
2635  * PathKey contains OID of the btree opfamily we're sorting by, but
2636  * that's not quite enough because we need the expression's datatype
2637  * to look up the sort operator in the operator family.
2638  */
2639  Assert(list_length(best_path->path.pathkeys) == list_length(indexorderbys));
2640  forboth(pathkeyCell, best_path->path.pathkeys, exprCell, indexorderbys)
2641  {
2642  PathKey *pathkey = (PathKey *) lfirst(pathkeyCell);
2643  Node *expr = (Node *) lfirst(exprCell);
2644  Oid exprtype = exprType(expr);
2645  Oid sortop;
2646 
2647  /* Get sort operator from opfamily */
2648  sortop = get_opfamily_member(pathkey->pk_opfamily,
2649  exprtype,
2650  exprtype,
2651  pathkey->pk_strategy);
2652  if (!OidIsValid(sortop))
2653  elog(ERROR, "missing operator %d(%u,%u) in opfamily %u",
2654  pathkey->pk_strategy, exprtype, exprtype, pathkey->pk_opfamily);
2655  indexorderbyops = lappend_oid(indexorderbyops, sortop);
2656  }
2657  }
2658 
2659  /* Finally ready to build the plan node */
2660  if (indexonly)
2661  scan_plan = (Scan *) make_indexonlyscan(tlist,
2662  qpqual,
2663  baserelid,
2664  indexoid,
2665  fixed_indexquals,
2666  fixed_indexorderbys,
2667  best_path->indexinfo->indextlist,
2668  best_path->indexscandir);
2669  else
2670  scan_plan = (Scan *) make_indexscan(tlist,
2671  qpqual,
2672  baserelid,
2673  indexoid,
2674  fixed_indexquals,
2675  stripped_indexquals,
2676  fixed_indexorderbys,
2677  indexorderbys,
2678  indexorderbyops,
2679  best_path->indexscandir);
2680 
2681  copy_generic_path_info(&scan_plan->plan, &best_path->path);
2682 
2683  return scan_plan;
2684 }
2685 
2686 /*
2687  * create_bitmap_scan_plan
2688  * Returns a bitmap scan plan for the base relation scanned by 'best_path'
2689  * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
2690  */
2691 static BitmapHeapScan *
2693  BitmapHeapPath *best_path,
2694  List *tlist,
2695  List *scan_clauses)
2696 {
2697  Index baserelid = best_path->path.parent->relid;
2698  Plan *bitmapqualplan;
2699  List *bitmapqualorig;
2700  List *indexquals;
2701  List *indexECs;
2702  List *qpqual;
2703  ListCell *l;
2704  BitmapHeapScan *scan_plan;
2705 
2706  /* it should be a base rel... */
2707  Assert(baserelid > 0);
2708  Assert(best_path->path.parent->rtekind == RTE_RELATION);
2709 
2710  /* Process the bitmapqual tree into a Plan tree and qual lists */
2711  bitmapqualplan = create_bitmap_subplan(root, best_path->bitmapqual,
2712  &bitmapqualorig, &indexquals,
2713  &indexECs);
2714 
2715  if (best_path->path.parallel_aware)
2716  bitmap_subplan_mark_shared(bitmapqualplan);
2717 
2718  /*
2719  * The qpqual list must contain all restrictions not automatically handled
2720  * by the index, other than pseudoconstant clauses which will be handled
2721  * by a separate gating plan node. All the predicates in the indexquals
2722  * will be checked (either by the index itself, or by
2723  * nodeBitmapHeapscan.c), but if there are any "special" operators
2724  * involved then they must be added to qpqual. The upshot is that qpqual
2725  * must contain scan_clauses minus whatever appears in indexquals.
2726  *
2727  * This loop is similar to the comparable code in create_indexscan_plan(),
2728  * but with some differences because it has to compare the scan clauses to
2729  * stripped (no RestrictInfos) indexquals. See comments there for more
2730  * info.
2731  *
2732  * In normal cases simple equal() checks will be enough to spot duplicate
2733  * clauses, so we try that first. We next see if the scan clause is
2734  * redundant with any top-level indexqual by virtue of being generated
2735  * from the same EC. After that, try predicate_implied_by().
2736  *
2737  * Unlike create_indexscan_plan(), the predicate_implied_by() test here is
2738  * useful for getting rid of qpquals that are implied by index predicates,
2739  * because the predicate conditions are included in the "indexquals"
2740  * returned by create_bitmap_subplan(). Bitmap scans have to do it that
2741  * way because predicate conditions need to be rechecked if the scan
2742  * becomes lossy, so they have to be included in bitmapqualorig.
2743  */
2744  qpqual = NIL;
2745  foreach(l, scan_clauses)
2746  {
2747  RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
2748  Node *clause = (Node *) rinfo->clause;
2749 
2750  if (rinfo->pseudoconstant)
2751  continue; /* we may drop pseudoconstants here */
2752  if (list_member(indexquals, clause))
2753  continue; /* simple duplicate */
2754  if (rinfo->parent_ec && list_member_ptr(indexECs, rinfo->parent_ec))
2755  continue; /* derived from same EquivalenceClass */
2756  if (!contain_mutable_functions(clause) &&
2757  predicate_implied_by(list_make1(clause), indexquals, false))
2758  continue; /* provably implied by indexquals */
2759  qpqual = lappend(qpqual, rinfo);
2760  }
2761 
2762  /* Sort clauses into best execution order */
2763  qpqual = order_qual_clauses(root, qpqual);
2764 
2765  /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
2766  qpqual = extract_actual_clauses(qpqual, false);
2767 
2768  /*
2769  * When dealing with special operators, we will at this point have
2770  * duplicate clauses in qpqual and bitmapqualorig. We may as well drop
2771  * 'em from bitmapqualorig, since there's no point in making the tests
2772  * twice.
2773  */
2774  bitmapqualorig = list_difference_ptr(bitmapqualorig, qpqual);
2775 
2776  /*
2777  * We have to replace any outer-relation variables with nestloop params in
2778  * the qpqual and bitmapqualorig expressions. (This was already done for
2779  * expressions attached to plan nodes in the bitmapqualplan tree.)
2780  */
2781  if (best_path->path.param_info)
2782  {
2783  qpqual = (List *)
2784  replace_nestloop_params(root, (Node *) qpqual);
2785  bitmapqualorig = (List *)
2786  replace_nestloop_params(root, (Node *) bitmapqualorig);
2787  }
2788 
2789  /* Finally ready to build the plan node */
2790  scan_plan = make_bitmap_heapscan(tlist,
2791  qpqual,
2792  bitmapqualplan,
2793  bitmapqualorig,
2794  baserelid);
2795 
2796  copy_generic_path_info(&scan_plan->scan.plan, &best_path->path);
2797 
2798  return scan_plan;
2799 }
2800 
2801 /*
2802  * Given a bitmapqual tree, generate the Plan tree that implements it
2803  *
2804  * As byproducts, we also return in *qual and *indexqual the qual lists
2805  * (in implicit-AND form, without RestrictInfos) describing the original index
2806  * conditions and the generated indexqual conditions. (These are the same in
2807  * simple cases, but when special index operators are involved, the former
2808  * list includes the special conditions while the latter includes the actual
2809  * indexable conditions derived from them.) Both lists include partial-index
2810  * predicates, because we have to recheck predicates as well as index
2811  * conditions if the bitmap scan becomes lossy.
2812  *
2813  * In addition, we return a list of EquivalenceClass pointers for all the
2814  * top-level indexquals that were possibly-redundantly derived from ECs.
2815  * This allows removal of scan_clauses that are redundant with such quals.
2816  * (We do not attempt to detect such redundancies for quals that are within
2817  * OR subtrees. This could be done in a less hacky way if we returned the
2818  * indexquals in RestrictInfo form, but that would be slower and still pretty
2819  * messy, since we'd have to build new RestrictInfos in many cases.)
2820  */
2821 static Plan *
2823  List **qual, List **indexqual, List **indexECs)
2824 {
2825  Plan *plan;
2826 
2827  if (IsA(bitmapqual, BitmapAndPath))
2828  {
2829  BitmapAndPath *apath = (BitmapAndPath *) bitmapqual;
2830  List *subplans = NIL;
2831  List *subquals = NIL;
2832  List *subindexquals = NIL;
2833  List *subindexECs = NIL;
2834  ListCell *l;
2835 
2836  /*
2837  * There may well be redundant quals among the subplans, since a
2838  * top-level WHERE qual might have gotten used to form several
2839  * different index quals. We don't try exceedingly hard to eliminate
2840  * redundancies, but we do eliminate obvious duplicates by using
2841  * list_concat_unique.
2842  */
2843  foreach(l, apath->bitmapquals)
2844  {
2845  Plan *subplan;
2846  List *subqual;
2847  List *subindexqual;
2848  List *subindexEC;
2849 
2850  subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
2851  &subqual, &subindexqual,
2852  &subindexEC);
2853  subplans = lappend(subplans, subplan);
2854  subquals = list_concat_unique(subquals, subqual);
2855  subindexquals = list_concat_unique(subindexquals, subindexqual);
2856  /* Duplicates in indexECs aren't worth getting rid of */
2857  subindexECs = list_concat(subindexECs, subindexEC);
2858  }
2859  plan = (Plan *) make_bitmap_and(subplans);
2860  plan->startup_cost = apath->path.startup_cost;
2861  plan->total_cost = apath->path.total_cost;
2862  plan->plan_rows =
2863  clamp_row_est(apath->bitmapselectivity * apath->path.parent->tuples);
2864  plan->plan_width = 0; /* meaningless */
2865  plan->parallel_aware = false;
2866  plan->parallel_safe = apath->path.parallel_safe;
2867  *qual = subquals;
2868  *indexqual = subindexquals;
2869  *indexECs = subindexECs;
2870  }
2871  else if (IsA(bitmapqual, BitmapOrPath))
2872  {
2873  BitmapOrPath *opath = (BitmapOrPath *) bitmapqual;
2874  List *subplans = NIL;
2875  List *subquals = NIL;
2876  List *subindexquals = NIL;
2877  bool const_true_subqual = false;
2878  bool const_true_subindexqual = false;
2879  ListCell *l;
2880 
2881  /*
2882  * Here, we only detect qual-free subplans. A qual-free subplan would
2883  * cause us to generate "... OR true ..." which we may as well reduce
2884  * to just "true". We do not try to eliminate redundant subclauses
2885  * because (a) it's not as likely as in the AND case, and (b) we might
2886  * well be working with hundreds or even thousands of OR conditions,
2887  * perhaps from a long IN list. The performance of list_append_unique
2888  * would be unacceptable.
2889  */
2890  foreach(l, opath->bitmapquals)
2891  {
2892  Plan *subplan;
2893  List *subqual;
2894  List *subindexqual;
2895  List *subindexEC;
2896 
2897  subplan = create_bitmap_subplan(root, (Path *) lfirst(l),
2898  &subqual, &subindexqual,
2899  &subindexEC);
2900  subplans = lappend(subplans, subplan);
2901  if (subqual == NIL)
2902  const_true_subqual = true;
2903  else if (!const_true_subqual)
2904  subquals = lappend(subquals,
2905  make_ands_explicit(subqual));
2906  if (subindexqual == NIL)
2907  const_true_subindexqual = true;
2908  else if (!const_true_subindexqual)
2909  subindexquals = lappend(subindexquals,
2910  make_ands_explicit(subindexqual));
2911  }
2912 
2913  /*
2914  * In the presence of ScalarArrayOpExpr quals, we might have built
2915  * BitmapOrPaths with just one subpath; don't add an OR step.
2916  */
2917  if (list_length(subplans) == 1)
2918  {
2919  plan = (Plan *) linitial(subplans);
2920  }
2921  else
2922  {
2923  plan = (Plan *) make_bitmap_or(subplans);
2924  plan->startup_cost = opath->path.startup_cost;
2925  plan->total_cost = opath->path.total_cost;
2926  plan->plan_rows =
2927  clamp_row_est(opath->bitmapselectivity * opath->path.parent->tuples);
2928  plan->plan_width = 0; /* meaningless */
2929  plan->parallel_aware = false;
2930  plan->parallel_safe = opath->path.parallel_safe;
2931  }
2932 
2933  /*
2934  * If there were constant-TRUE subquals, the OR reduces to constant
2935  * TRUE. Also, avoid generating one-element ORs, which could happen
2936  * due to redundancy elimination or ScalarArrayOpExpr quals.
2937  */
2938  if (const_true_subqual)
2939  *qual = NIL;
2940  else if (list_length(subquals) <= 1)
2941  *qual = subquals;
2942  else
2943  *qual = list_make1(make_orclause(subquals));
2944  if (const_true_subindexqual)
2945  *indexqual = NIL;
2946  else if (list_length(subindexquals) <= 1)
2947  *indexqual = subindexquals;
2948  else
2949  *indexqual = list_make1(make_orclause(subindexquals));
2950  *indexECs = NIL;
2951  }
2952  else if (IsA(bitmapqual, IndexPath))
2953  {
2954  IndexPath *ipath = (IndexPath *) bitmapqual;
2955  IndexScan *iscan;
2956  List *subindexECs;
2957  ListCell *l;
2958 
2959  /* Use the regular indexscan plan build machinery... */
2960  iscan = castNode(IndexScan,
2961  create_indexscan_plan(root, ipath,
2962  NIL, NIL, false));
2963  /* then convert to a bitmap indexscan */
2964  plan = (Plan *) make_bitmap_indexscan(iscan->scan.scanrelid,
2965  iscan->indexid,
2966  iscan->indexqual,
2967  iscan->indexqualorig);
2968  /* and set its cost/width fields appropriately */
2969  plan->startup_cost = 0.0;
2970  plan->total_cost = ipath->indextotalcost;
2971  plan->plan_rows =
2972  clamp_row_est(ipath->indexselectivity * ipath->path.parent->tuples);
2973  plan->plan_width = 0; /* meaningless */
2974  plan->parallel_aware = false;
2975  plan->parallel_safe = ipath->path.parallel_safe;
2976  *qual = get_actual_clauses(ipath->indexclauses);
2977  *indexqual = get_actual_clauses(ipath->indexquals);
2978  foreach(l, ipath->indexinfo->indpred)
2979  {
2980  Expr *pred = (Expr *) lfirst(l);
2981 
2982  /*
2983  * We know that the index predicate must have been implied by the
2984  * query condition as a whole, but it may or may not be implied by
2985  * the conditions that got pushed into the bitmapqual. Avoid
2986  * generating redundant conditions.
2987  */
2988  if (!predicate_implied_by(list_make1(pred), ipath->indexclauses,
2989  false))
2990  {
2991  *qual = lappend(*qual, pred);
2992  *indexqual = lappend(*indexqual, pred);
2993  }
2994  }
2995  subindexECs = NIL;
2996  foreach(l, ipath->indexquals)
2997  {
2998  RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);
2999 
3000  if (rinfo->parent_ec)
3001  subindexECs = lappend(subindexECs, rinfo->parent_ec);
3002  }
3003  *indexECs = subindexECs;
3004  }
3005  else
3006  {
3007  elog(ERROR, "unrecognized node type: %d", nodeTag(bitmapqual));
3008  plan = NULL; /* keep compiler quiet */
3009  }
3010 
3011  return plan;
3012 }
3013 
3014 /*
3015  * create_tidscan_plan
3016  * Returns a tidscan plan for the base relation scanned by 'best_path'
3017  * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3018  */
3019 static TidScan *
3021  List *tlist, List *scan_clauses)
3022 {
3023  TidScan *scan_plan;
3024  Index scan_relid = best_path->path.parent->relid;
3025  List *tidquals = best_path->tidquals;
3026  List *ortidquals;
3027 
3028  /* it should be a base rel... */
3029  Assert(scan_relid > 0);
3030  Assert(best_path->path.parent->rtekind == RTE_RELATION);
3031 
3032  /* Sort clauses into best execution order */
3033  scan_clauses = order_qual_clauses(root, scan_clauses);
3034 
3035  /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3036  scan_clauses = extract_actual_clauses(scan_clauses, false);
3037 
3038  /* Replace any outer-relation variables with nestloop params */
3039  if (best_path->path.param_info)
3040  {
3041  tidquals = (List *)
3042  replace_nestloop_params(root, (Node *) tidquals);
3043  scan_clauses = (List *)
3044  replace_nestloop_params(root, (Node *) scan_clauses);
3045  }
3046 
3047  /*
3048  * Remove any clauses that are TID quals. This is a bit tricky since the
3049  * tidquals list has implicit OR semantics.
3050  */
3051  ortidquals = tidquals;
3052  if (list_length(ortidquals) > 1)
3053  ortidquals = list_make1(make_orclause(ortidquals));
3054  scan_clauses = list_difference(scan_clauses, ortidquals);
3055 
3056  scan_plan = make_tidscan(tlist,
3057  scan_clauses,
3058  scan_relid,
3059  tidquals);
3060 
3061  copy_generic_path_info(&scan_plan->scan.plan, &best_path->path);
3062 
3063  return scan_plan;
3064 }
3065 
3066 /*
3067  * create_subqueryscan_plan
3068  * Returns a subqueryscan plan for the base relation scanned by 'best_path'
3069  * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3070  */
3071 static SubqueryScan *
3073  List *tlist, List *scan_clauses)
3074 {
3075  SubqueryScan *scan_plan;
3076  RelOptInfo *rel = best_path->path.parent;
3077  Index scan_relid = rel->relid;
3078  Plan *subplan;
3079 
3080  /* it should be a subquery base rel... */
3081  Assert(scan_relid > 0);
3082  Assert(rel->rtekind == RTE_SUBQUERY);
3083 
3084  /*
3085  * Recursively create Plan from Path for subquery. Since we are entering
3086  * a different planner context (subroot), recurse to create_plan not
3087  * create_plan_recurse.
3088  */
3089  subplan = create_plan(rel->subroot, best_path->subpath);
3090 
3091  /* Sort clauses into best execution order */
3092  scan_clauses = order_qual_clauses(root, scan_clauses);
3093 
3094  /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3095  scan_clauses = extract_actual_clauses(scan_clauses, false);
3096 
3097  /* Replace any outer-relation variables with nestloop params */
3098  if (best_path->path.param_info)
3099  {
3100  scan_clauses = (List *)
3101  replace_nestloop_params(root, (Node *) scan_clauses);
3103  rel->subplan_params);
3104  }
3105 
3106  scan_plan = make_subqueryscan(tlist,
3107  scan_clauses,
3108  scan_relid,
3109  subplan);
3110 
3111  copy_generic_path_info(&scan_plan->scan.plan, &best_path->path);
3112 
3113  return scan_plan;
3114 }
3115 
3116 /*
3117  * create_functionscan_plan
3118  * Returns a functionscan plan for the base relation scanned by 'best_path'
3119  * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3120  */
3121 static FunctionScan *
3123  List *tlist, List *scan_clauses)
3124 {
3125  FunctionScan *scan_plan;
3126  Index scan_relid = best_path->parent->relid;
3127  RangeTblEntry *rte;
3128  List *functions;
3129 
3130  /* it should be a function base rel... */
3131  Assert(scan_relid > 0);
3132  rte = planner_rt_fetch(scan_relid, root);
3133  Assert(rte->rtekind == RTE_FUNCTION);
3134  functions = rte->functions;
3135 
3136  /* Sort clauses into best execution order */
3137  scan_clauses = order_qual_clauses(root, scan_clauses);
3138 
3139  /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3140  scan_clauses = extract_actual_clauses(scan_clauses, false);
3141 
3142  /* Replace any outer-relation variables with nestloop params */
3143  if (best_path->param_info)
3144  {
3145  scan_clauses = (List *)
3146  replace_nestloop_params(root, (Node *) scan_clauses);
3147  /* The function expressions could contain nestloop params, too */
3148  functions = (List *) replace_nestloop_params(root, (Node *) functions);
3149  }
3150 
3151  scan_plan = make_functionscan(tlist, scan_clauses, scan_relid,
3152  functions, rte->funcordinality);
3153 
3154  copy_generic_path_info(&scan_plan->scan.plan, best_path);
3155 
3156  return scan_plan;
3157 }
3158 
3159 /*
3160  * create_tablefuncscan_plan
3161  * Returns a tablefuncscan plan for the base relation scanned by 'best_path'
3162  * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3163  */
3164 static TableFuncScan *
3166  List *tlist, List *scan_clauses)
3167 {
3168  TableFuncScan *scan_plan;
3169  Index scan_relid = best_path->parent->relid;
3170  RangeTblEntry *rte;
3171  TableFunc *tablefunc;
3172 
3173  /* it should be a function base rel... */
3174  Assert(scan_relid > 0);
3175  rte = planner_rt_fetch(scan_relid, root);
3176  Assert(rte->rtekind == RTE_TABLEFUNC);
3177  tablefunc = rte->tablefunc;
3178 
3179  /* Sort clauses into best execution order */
3180  scan_clauses = order_qual_clauses(root, scan_clauses);
3181 
3182  /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3183  scan_clauses = extract_actual_clauses(scan_clauses, false);
3184 
3185  /* Replace any outer-relation variables with nestloop params */
3186  if (best_path->param_info)
3187  {
3188  scan_clauses = (List *)
3189  replace_nestloop_params(root, (Node *) scan_clauses);
3190  /* The function expressions could contain nestloop params, too */
3191  tablefunc = (TableFunc *) replace_nestloop_params(root, (Node *) tablefunc);
3192  }
3193 
3194  scan_plan = make_tablefuncscan(tlist, scan_clauses, scan_relid,
3195  tablefunc);
3196 
3197  copy_generic_path_info(&scan_plan->scan.plan, best_path);
3198 
3199  return scan_plan;
3200 }
3201 
3202 /*
3203  * create_valuesscan_plan
3204  * Returns a valuesscan plan for the base relation scanned by 'best_path'
3205  * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3206  */
3207 static ValuesScan *
3209  List *tlist, List *scan_clauses)
3210 {
3211  ValuesScan *scan_plan;
3212  Index scan_relid = best_path->parent->relid;
3213  RangeTblEntry *rte;
3214  List *values_lists;
3215 
3216  /* it should be a values base rel... */
3217  Assert(scan_relid > 0);
3218  rte = planner_rt_fetch(scan_relid, root);
3219  Assert(rte->rtekind == RTE_VALUES);
3220  values_lists = rte->values_lists;
3221 
3222  /* Sort clauses into best execution order */
3223  scan_clauses = order_qual_clauses(root, scan_clauses);
3224 
3225  /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3226  scan_clauses = extract_actual_clauses(scan_clauses, false);
3227 
3228  /* Replace any outer-relation variables with nestloop params */
3229  if (best_path->param_info)
3230  {
3231  scan_clauses = (List *)
3232  replace_nestloop_params(root, (Node *) scan_clauses);
3233  /* The values lists could contain nestloop params, too */
3234  values_lists = (List *)
3235  replace_nestloop_params(root, (Node *) values_lists);
3236  }
3237 
3238  scan_plan = make_valuesscan(tlist, scan_clauses, scan_relid,
3239  values_lists);
3240 
3241  copy_generic_path_info(&scan_plan->scan.plan, best_path);
3242 
3243  return scan_plan;
3244 }
3245 
3246 /*
3247  * create_ctescan_plan
3248  * Returns a ctescan plan for the base relation scanned by 'best_path'
3249  * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3250  */
3251 static CteScan *
3253  List *tlist, List *scan_clauses)
3254 {
3255  CteScan *scan_plan;
3256  Index scan_relid = best_path->parent->relid;
3257  RangeTblEntry *rte;
3258  SubPlan *ctesplan = NULL;
3259  int plan_id;
3260  int cte_param_id;
3261  PlannerInfo *cteroot;
3262  Index levelsup;
3263  int ndx;
3264  ListCell *lc;
3265 
3266  Assert(scan_relid > 0);
3267  rte = planner_rt_fetch(scan_relid, root);
3268  Assert(rte->rtekind == RTE_CTE);
3269  Assert(!rte->self_reference);
3270 
3271  /*
3272  * Find the referenced CTE, and locate the SubPlan previously made for it.
3273  */
3274  levelsup = rte->ctelevelsup;
3275  cteroot = root;
3276  while (levelsup-- > 0)
3277  {
3278  cteroot = cteroot->parent_root;
3279  if (!cteroot) /* shouldn't happen */
3280  elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
3281  }
3282 
3283  /*
3284  * Note: cte_plan_ids can be shorter than cteList, if we are still working
3285  * on planning the CTEs (ie, this is a side-reference from another CTE).
3286  * So we mustn't use forboth here.
3287  */
3288  ndx = 0;
3289  foreach(lc, cteroot->parse->cteList)
3290  {
3291  CommonTableExpr *cte = (CommonTableExpr *) lfirst(lc);
3292 
3293  if (strcmp(cte->ctename, rte->ctename) == 0)
3294  break;
3295  ndx++;
3296  }
3297  if (lc == NULL) /* shouldn't happen */
3298  elog(ERROR, "could not find CTE \"%s\"", rte->ctename);
3299  if (ndx >= list_length(cteroot->cte_plan_ids))
3300  elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
3301  plan_id = list_nth_int(cteroot->cte_plan_ids, ndx);
3302  Assert(plan_id > 0);
3303  foreach(lc, cteroot->init_plans)
3304  {
3305  ctesplan = (SubPlan *) lfirst(lc);
3306  if (ctesplan->plan_id == plan_id)
3307  break;
3308  }
3309  if (lc == NULL) /* shouldn't happen */
3310  elog(ERROR, "could not find plan for CTE \"%s\"", rte->ctename);
3311 
3312  /*
3313  * We need the CTE param ID, which is the sole member of the SubPlan's
3314  * setParam list.
3315  */
3316  cte_param_id = linitial_int(ctesplan->setParam);
3317 
3318  /* Sort clauses into best execution order */
3319  scan_clauses = order_qual_clauses(root, scan_clauses);
3320 
3321  /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3322  scan_clauses = extract_actual_clauses(scan_clauses, false);
3323 
3324  /* Replace any outer-relation variables with nestloop params */
3325  if (best_path->param_info)
3326  {
3327  scan_clauses = (List *)
3328  replace_nestloop_params(root, (Node *) scan_clauses);
3329  }
3330 
3331  scan_plan = make_ctescan(tlist, scan_clauses, scan_relid,
3332  plan_id, cte_param_id);
3333 
3334  copy_generic_path_info(&scan_plan->scan.plan, best_path);
3335 
3336  return scan_plan;
3337 }
3338 
3339 /*
3340  * create_namedtuplestorescan_plan
3341  * Returns a tuplestorescan plan for the base relation scanned by
3342  * 'best_path' with restriction clauses 'scan_clauses' and targetlist
3343  * 'tlist'.
3344  */
3345 static NamedTuplestoreScan *
3347  List *tlist, List *scan_clauses)
3348 {
3349  NamedTuplestoreScan *scan_plan;
3350  Index scan_relid = best_path->parent->relid;
3351  RangeTblEntry *rte;
3352 
3353  Assert(scan_relid > 0);
3354  rte = planner_rt_fetch(scan_relid, root);
3356 
3357  /* Sort clauses into best execution order */
3358  scan_clauses = order_qual_clauses(root, scan_clauses);
3359 
3360  /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3361  scan_clauses = extract_actual_clauses(scan_clauses, false);
3362 
3363  /* Replace any outer-relation variables with nestloop params */
3364  if (best_path->param_info)
3365  {
3366  scan_clauses = (List *)
3367  replace_nestloop_params(root, (Node *) scan_clauses);
3368  }
3369 
3370  scan_plan = make_namedtuplestorescan(tlist, scan_clauses, scan_relid,
3371  rte->enrname);
3372 
3373  copy_generic_path_info(&scan_plan->scan.plan, best_path);
3374 
3375  return scan_plan;
3376 }
3377 
3378 /*
3379  * create_worktablescan_plan
3380  * Returns a worktablescan plan for the base relation scanned by 'best_path'
3381  * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3382  */
3383 static WorkTableScan *
3385  List *tlist, List *scan_clauses)
3386 {
3387  WorkTableScan *scan_plan;
3388  Index scan_relid = best_path->parent->relid;
3389  RangeTblEntry *rte;
3390  Index levelsup;
3391  PlannerInfo *cteroot;
3392 
3393  Assert(scan_relid > 0);
3394  rte = planner_rt_fetch(scan_relid, root);
3395  Assert(rte->rtekind == RTE_CTE);
3396  Assert(rte->self_reference);
3397 
3398  /*
3399  * We need to find the worktable param ID, which is in the plan level
3400  * that's processing the recursive UNION, which is one level *below* where
3401  * the CTE comes from.
3402  */
3403  levelsup = rte->ctelevelsup;
3404  if (levelsup == 0) /* shouldn't happen */
3405  elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
3406  levelsup--;
3407  cteroot = root;
3408  while (levelsup-- > 0)
3409  {
3410  cteroot = cteroot->parent_root;
3411  if (!cteroot) /* shouldn't happen */
3412  elog(ERROR, "bad levelsup for CTE \"%s\"", rte->ctename);
3413  }
3414  if (cteroot->wt_param_id < 0) /* shouldn't happen */
3415  elog(ERROR, "could not find param ID for CTE \"%s\"", rte->ctename);
3416 
3417  /* Sort clauses into best execution order */
3418  scan_clauses = order_qual_clauses(root, scan_clauses);
3419 
3420  /* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
3421  scan_clauses = extract_actual_clauses(scan_clauses, false);
3422 
3423  /* Replace any outer-relation variables with nestloop params */
3424  if (best_path->param_info)
3425  {
3426  scan_clauses = (List *)
3427  replace_nestloop_params(root, (Node *) scan_clauses);
3428  }
3429 
3430  scan_plan = make_worktablescan(tlist, scan_clauses, scan_relid,
3431  cteroot->wt_param_id);
3432 
3433  copy_generic_path_info(&scan_plan->scan.plan, best_path);
3434 
3435  return scan_plan;
3436 }
3437 
3438 /*
3439  * create_foreignscan_plan
3440  * Returns a foreignscan plan for the relation scanned by 'best_path'
3441  * with restriction clauses 'scan_clauses' and targetlist 'tlist'.
3442  */
3443 static ForeignScan *
3445  List *tlist, List *scan_clauses)
3446 {
3447  ForeignScan *scan_plan;
3448  RelOptInfo *rel = best_path->path.parent;
3449  Index scan_relid = rel->relid;
3450  Oid rel_oid = InvalidOid;
3451  Plan *outer_plan = NULL;
3452 
3453  Assert(rel->fdwroutine != NULL);
3454 
3455  /* transform the child path if any */
3456  if (best_path->fdw_outerpath)
3457  outer_plan = create_plan_recurse(root, best_path->fdw_outerpath,
3458  CP_EXACT_TLIST);
3459 
3460  /*
3461  * If we're scanning a base relation, fetch its OID. (Irrelevant if
3462  * scanning a join relation.)
3463  */
3464  if (scan_relid > 0)
3465  {
3466  RangeTblEntry *rte;
3467 
3468  Assert(rel->rtekind == RTE_RELATION);
3469  rte = planner_rt_fetch(scan_relid, root);
3470  Assert(rte->rtekind == RTE_RELATION);
3471  rel_oid = rte->relid;
3472  }
3473 
3474  /*
3475  * Sort clauses into best execution order. We do this first since the FDW
3476  * might have more info than we do and wish to adjust the ordering.
3477  */
3478  scan_clauses = order_qual_clauses(root, scan_clauses);
3479 
3480  /*
3481  * Let the FDW perform its processing on the restriction clauses and
3482  * generate the plan node. Note that the FDW might remove restriction
3483  * clauses that it intends to execute remotely, or even add more (if it
3484  * has selected some join clauses for remote use but also wants them
3485  * rechecked locally).
3486  */
3487  scan_plan = rel->fdwroutine->GetForeignPlan(root, rel, rel_oid,
3488  best_path,
3489  tlist, scan_clauses,
3490  outer_plan);
3491 
3492  /* Copy cost data from Path to Plan; no need to make FDW do this */
3493  copy_generic_path_info(&scan_plan->scan.plan, &best_path->path);
3494 
3495  /* Copy foreign server OID; likewise, no need to make FDW do this */
3496  scan_plan->fs_server = rel->serverid;
3497 
3498  /*
3499  * Likewise, copy the relids that are represented by this foreign scan. An
3500  * upper rel doesn't have relids set, but it covers all the base relations
3501  * participating in the underlying scan, so use root's all_baserels.
3502  */
3503  if (IS_UPPER_REL(rel))
3504  scan_plan->fs_relids = root->all_baserels;
3505  else
3506  scan_plan->fs_relids = best_path->path.parent->relids;
3507 
3508  /*
3509  * If this is a foreign join, and to make it valid to push down we had to
3510  * assume that the current user is the same as some user explicitly named
3511  * in the query, mark the finished plan as depending on the current user.
3512  */
3513  if (rel->useridiscurrent)
3514  root->glob->dependsOnRole = true;
3515 
3516  /*
3517  * Replace any outer-relation variables with nestloop params in the qual,
3518  * fdw_exprs and fdw_recheck_quals expressions. We do this last so that
3519  * the FDW doesn't have to be involved. (Note that parts of fdw_exprs or
3520  * fdw_recheck_quals could have come from join clauses, so doing this
3521  * beforehand on the scan_clauses wouldn't work.) We assume
3522  * fdw_scan_tlist contains no such variables.
3523  */
3524  if (best_path->path.param_info)
3525  {
3526  scan_plan->scan.plan.qual = (List *)
3527  replace_nestloop_params(root, (Node *) scan_plan->scan.plan.qual);
3528  scan_plan->fdw_exprs = (List *)
3529  replace_nestloop_params(root, (Node *) scan_plan->fdw_exprs);
3530  scan_plan->fdw_recheck_quals = (List *)
3532  (Node *) scan_plan->fdw_recheck_quals);
3533  }
3534 
3535  /*
3536  * If rel is a base relation, detect whether any system columns are
3537  * requested from the rel. (If rel is a join relation, rel->relid will be
3538  * 0, but there can be no Var with relid 0 in the rel's targetlist or the
3539  * restriction clauses, so we skip this in that case. Note that any such
3540  * columns in base relations that were joined are assumed to be contained
3541  * in fdw_scan_tlist.) This is a bit of a kluge and might go away
3542  * someday, so we intentionally leave it out of the API presented to FDWs.
3543  */
3544  scan_plan->fsSystemCol = false;
3545  if (scan_relid > 0)
3546  {
3547  Bitmapset *attrs_used = NULL;
3548  ListCell *lc;
3549  int i;
3550 
3551  /*
3552  * First, examine all the attributes needed for joins or final output.
3553  * Note: we must look at rel's targetlist, not the attr_needed data,
3554  * because attr_needed isn't computed for inheritance child rels.
3555  */
3556  pull_varattnos((Node *) rel->reltarget->exprs, scan_relid, &attrs_used);
3557 
3558  /* Add all the attributes used by restriction clauses. */
3559  foreach(lc, rel->baserestrictinfo)
3560  {
3561  RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
3562 
3563  pull_varattnos((Node *) rinfo->clause, scan_relid, &attrs_used);
3564  }
3565 
3566  /* Now, are any system columns requested from rel? */
3567  for (i = FirstLowInvalidHeapAttributeNumber + 1; i < 0; i++)
3568  {
3570  {
3571  scan_plan->fsSystemCol = true;
3572  break;
3573  }
3574  }
3575 
3576  bms_free(attrs_used);
3577  }
3578 
3579  return scan_plan;
3580 }
3581 
3582 /*
3583  * create_custom_plan
3584  *
3585  * Transform a CustomPath into a Plan.
3586  */
3587 static CustomScan *
3589  List *tlist, List *scan_clauses)
3590 {
3591  CustomScan *cplan;
3592  RelOptInfo *rel = best_path->path.parent;
3593  List *custom_plans = NIL;
3594  ListCell *lc;
3595 
3596  /* Recursively transform child paths. */
3597  foreach(lc, best_path->custom_paths)
3598  {
3599  Plan *plan = create_plan_recurse(root, (Path *) lfirst(lc),
3600  CP_EXACT_TLIST);
3601 
3602  custom_plans = lappend(custom_plans, plan);
3603  }
3604 
3605  /*
3606  * Sort clauses into the best execution order, although custom-scan
3607  * provider can reorder them again.
3608  */
3609  scan_clauses = order_qual_clauses(root, scan_clauses);
3610 
3611  /*
3612  * Invoke custom plan provider to create the Plan node represented by the
3613  * CustomPath.
3614  */
3615  cplan = castNode(CustomScan,
3616  best_path->methods->PlanCustomPath(root,
3617  rel,
3618  best_path,
3619  tlist,
3620  scan_clauses,
3621  custom_plans));
3622 
3623  /*
3624  * Copy cost data from Path to Plan; no need to make custom-plan providers
3625  * do this
3626  */
3627  copy_generic_path_info(&cplan->scan.plan, &best_path->path);
3628 
3629  /* Likewise, copy the relids that are represented by this custom scan */
3630  cplan->custom_relids = best_path->path.parent->relids;
3631 
3632  /*
3633  * Replace any outer-relation variables with nestloop params in the qual
3634  * and custom_exprs expressions. We do this last so that the custom-plan
3635  * provider doesn't have to be involved. (Note that parts of custom_exprs
3636  * could have come from join clauses, so doing this beforehand on the
3637  * scan_clauses wouldn't work.) We assume custom_scan_tlist contains no
3638  * such variables.
3639  */
3640  if (best_path->path.param_info)
3641  {
3642  cplan->scan.plan.qual = (List *)
3643  replace_nestloop_params(root, (Node *) cplan->scan.plan.qual);
3644  cplan->custom_exprs = (List *)
3645  replace_nestloop_params(root, (Node *) cplan->custom_exprs);
3646  }
3647 
3648  return cplan;
3649 }
3650 
3651 
3652 /*****************************************************************************
3653  *
3654  * JOIN METHODS
3655  *
3656  *****************************************************************************/
3657 
3658 static NestLoop *
3660  NestPath *best_path)
3661 {
3662  NestLoop *join_plan;
3663  Plan *outer_plan;
3664  Plan *inner_plan;
3665  List *tlist = build_path_tlist(root, &best_path->path);
3666  List *joinrestrictclauses = best_path->joinrestrictinfo;
3667  List *joinclauses;
3668  List *otherclauses;
3669  Relids outerrelids;
3670  List *nestParams;
3671  Relids saveOuterRels = root->curOuterRels;
3672  ListCell *cell;
3673  ListCell *prev;
3674  ListCell *next;
3675 
3676  /* NestLoop can project, so no need to be picky about child tlists */
3677  outer_plan = create_plan_recurse(root, best_path->outerjoinpath, 0);
3678 
3679  /* For a nestloop, include outer relids in curOuterRels for inner side */
3680  root->curOuterRels = bms_union(root->curOuterRels,
3681  best_path->outerjoinpath->parent->relids);
3682 
3683  inner_plan = create_plan_recurse(root, best_path->innerjoinpath, 0);
3684 
3685  /* Restore curOuterRels */
3686  bms_free(root->curOuterRels);
3687  root->curOuterRels = saveOuterRels;
3688 
3689  /* Sort join qual clauses into best execution order */
3690  joinrestrictclauses = order_qual_clauses(root, joinrestrictclauses);
3691 
3692  /* Get the join qual clauses (in plain expression form) */
3693  /* Any pseudoconstant clauses are ignored here */
3694  if (IS_OUTER_JOIN(best_path->jointype))
3695  {
3696  extract_actual_join_clauses(joinrestrictclauses,
3697  &joinclauses, &otherclauses);
3698  }
3699  else
3700  {
3701  /* We can treat all clauses alike for an inner join */
3702  joinclauses = extract_actual_clauses(joinrestrictclauses, false);
3703  otherclauses = NIL;
3704  }
3705 
3706  /* Replace any outer-relation variables with nestloop params */
3707  if (best_path->path.param_info)
3708  {
3709  joinclauses = (List *)
3710  replace_nestloop_params(root, (Node *) joinclauses);
3711  otherclauses = (List *)
3712  replace_nestloop_params(root, (Node *) otherclauses);
3713  }
3714 
3715  /*
3716  * Identify any nestloop parameters that should be supplied by this join
3717  * node, and move them from root->curOuterParams to the nestParams list.
3718  */
3719  outerrelids = best_path->outerjoinpath->parent->relids;
3720  nestParams = NIL;
3721  prev = NULL;
3722  for (cell = list_head(root->curOuterParams); cell; cell = next)
3723  {
3724  NestLoopParam *nlp = (NestLoopParam *) lfirst(cell);
3725 
3726  next = lnext(cell);
3727  if (IsA(nlp->paramval, Var) &&
3728  bms_is_member(nlp->paramval->varno, outerrelids))
3729  {
3731  cell, prev);
3732  nestParams = lappend(nestParams, nlp);
3733  }
3734  else if (IsA(nlp->paramval, PlaceHolderVar) &&
3735  bms_overlap(((PlaceHolderVar *) nlp->paramval)->phrels,
3736  outerrelids) &&
3738  (PlaceHolderVar *) nlp->paramval,
3739  false)->ph_eval_at,
3740  outerrelids))
3741  {
3743  cell, prev);
3744  nestParams = lappend(nestParams, nlp);
3745  }
3746  else
3747  prev = cell;
3748  }
3749 
3750  join_plan = make_nestloop(tlist,
3751  joinclauses,
3752  otherclauses,
3753  nestParams,
3754  outer_plan,
3755  inner_plan,
3756  best_path->jointype,
3757  best_path->inner_unique);
3758 
3759  copy_generic_path_info(&join_plan->join.plan, &best_path->path);
3760 
3761  return join_plan;
3762 }
3763 
3764 static MergeJoin *
3766  MergePath *best_path)
3767 {
3768  MergeJoin *join_plan;
3769  Plan *outer_plan;
3770  Plan *inner_plan;
3771  List *tlist = build_path_tlist(root, &best_path->jpath.path);
3772  List *joinclauses;
3773  List *otherclauses;
3774  List *mergeclauses;
3775  List *outerpathkeys;
3776  List *innerpathkeys;
3777  int nClauses;
3778  Oid *mergefamilies;
3779  Oid *mergecollations;
3780  int *mergestrategies;
3781  bool *mergenullsfirst;
3782  int i;
3783  ListCell *lc;
3784  ListCell *lop;
3785  ListCell *lip;
3786  Path *outer_path = best_path->jpath.outerjoinpath;
3787  Path *inner_path = best_path->jpath.innerjoinpath;
3788 
3789  /*
3790  * MergeJoin can project, so we don't have to demand exact tlists from the
3791  * inputs. However, if we're intending to sort an input's result, it's
3792  * best to request a small tlist so we aren't sorting more data than
3793  * necessary.
3794  */
3795  outer_plan = create_plan_recurse(root, best_path->jpath.outerjoinpath,
3796  (best_path->outersortkeys != NIL) ? CP_SMALL_TLIST : 0);
3797 
3798  inner_plan = create_plan_recurse(root, best_path->jpath.innerjoinpath,
3799  (best_path->innersortkeys != NIL) ? CP_SMALL_TLIST : 0);
3800 
3801  /* Sort join qual clauses into best execution order */
3802  /* NB: do NOT reorder the mergeclauses */
3803  joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
3804 
3805  /* Get the join qual clauses (in plain expression form) */
3806  /* Any pseudoconstant clauses are ignored here */
3807  if (IS_OUTER_JOIN(best_path->jpath.jointype))
3808  {
3809  extract_actual_join_clauses(joinclauses,
3810  &joinclauses, &otherclauses);
3811  }
3812  else
3813  {
3814  /* We can treat all clauses alike for an inner join */
3815  joinclauses = extract_actual_clauses(joinclauses, false);
3816  otherclauses = NIL;
3817  }
3818 
3819  /*
3820  * Remove the mergeclauses from the list of join qual clauses, leaving the
3821  * list of quals that must be checked as qpquals.
3822  */
3823  mergeclauses = get_actual_clauses(best_path->path_mergeclauses);
3824  joinclauses = list_difference(joinclauses, mergeclauses);
3825 
3826  /*
3827  * Replace any outer-relation variables with nestloop params. There
3828  * should not be any in the mergeclauses.
3829  */
3830  if (best_path->jpath.path.param_info)
3831  {
3832  joinclauses = (List *)
3833  replace_nestloop_params(root, (Node *) joinclauses);
3834  otherclauses = (List *)
3835  replace_nestloop_params(root, (Node *) otherclauses);
3836  }
3837 
3838  /*
3839  * Rearrange mergeclauses, if needed, so that the outer variable is always
3840  * on the left; mark the mergeclause restrictinfos with correct
3841  * outer_is_left status.
3842  */
3843  mergeclauses = get_switched_clauses(best_path->path_mergeclauses,
3844  best_path->jpath.outerjoinpath->parent->relids);
3845 
3846  /*
3847  * Create explicit sort nodes for the outer and inner paths if necessary.
3848  */
3849  if (best_path->outersortkeys)
3850  {
3851  Relids outer_relids = outer_path->parent->relids;
3852  Sort *sort = make_sort_from_pathkeys(outer_plan,
3853  best_path->outersortkeys,
3854  outer_relids);
3855 
3856  label_sort_with_costsize(root, sort, -1.0);
3857  outer_plan = (Plan *) sort;
3858  outerpathkeys = best_path->outersortkeys;
3859  }
3860  else
3861  outerpathkeys = best_path->jpath.outerjoinpath->pathkeys;
3862 
3863  if (best_path->innersortkeys)
3864  {
3865  Relids inner_relids = inner_path->parent->relids;
3866  Sort *sort = make_sort_from_pathkeys(inner_plan,
3867  best_path->innersortkeys,
3868  inner_relids);
3869 
3870  label_sort_with_costsize(root, sort, -1.0);
3871  inner_plan = (Plan *) sort;
3872  innerpathkeys = best_path->innersortkeys;
3873  }
3874  else
3875  innerpathkeys = best_path->jpath.innerjoinpath->pathkeys;
3876 
3877  /*
3878  * If specified, add a materialize node to shield the inner plan from the
3879  * need to handle mark/restore.
3880  */
3881  if (best_path->materialize_inner)
3882  {
3883  Plan *matplan = (Plan *) make_material(inner_plan);
3884 
3885  /*
3886  * We assume the materialize will not spill to disk, and therefore
3887  * charge just cpu_operator_cost per tuple. (Keep this estimate in
3888  * sync with final_cost_mergejoin.)
3889  */
3890  copy_plan_costsize(matplan, inner_plan);
3891  matplan->total_cost += cpu_operator_cost * matplan->plan_rows;
3892 
3893  inner_plan = matplan;
3894  }
3895 
3896  /*
3897  * Compute the opfamily/collation/strategy/nullsfirst arrays needed by the
3898  * executor. The information is in the pathkeys for the two inputs, but
3899  * we need to be careful about the possibility of mergeclauses sharing a
3900  * pathkey (compare find_mergeclauses_for_pathkeys()).
3901  */
3902  nClauses = list_length(mergeclauses);
3903  Assert(nClauses == list_length(best_path->path_mergeclauses));
3904  mergefamilies = (Oid *) palloc(nClauses * sizeof(Oid));
3905  mergecollations = (Oid *) palloc(nClauses * sizeof(Oid));
3906  mergestrategies = (int *) palloc(nClauses * sizeof(int));
3907  mergenullsfirst = (bool *) palloc(nClauses * sizeof(bool));
3908 
3909  lop = list_head(outerpathkeys);
3910  lip = list_head(innerpathkeys);
3911  i = 0;
3912  foreach(lc, best_path->path_mergeclauses)
3913  {
3914  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc);
3915  EquivalenceClass *oeclass;
3916  EquivalenceClass *ieclass;
3917  PathKey *opathkey;
3918  PathKey *ipathkey;
3919  EquivalenceClass *opeclass;
3920  EquivalenceClass *ipeclass;
3921  ListCell *l2;
3922 
3923  /* fetch outer/inner eclass from mergeclause */
3924  if (rinfo->outer_is_left)
3925  {
3926  oeclass = rinfo->left_ec;
3927  ieclass = rinfo->right_ec;
3928  }
3929  else
3930  {
3931  oeclass = rinfo->right_ec;
3932  ieclass = rinfo->left_ec;
3933  }
3934  Assert(oeclass != NULL);
3935  Assert(ieclass != NULL);
3936 
3937  /*
3938  * For debugging purposes, we check that the eclasses match the paths'
3939  * pathkeys. In typical cases the merge clauses are one-to-one with
3940  * the pathkeys, but when dealing with partially redundant query
3941  * conditions, we might have clauses that re-reference earlier path
3942  * keys. The case that we need to reject is where a pathkey is
3943  * entirely skipped over.
3944  *
3945  * lop and lip reference the first as-yet-unused pathkey elements;
3946  * it's okay to match them, or any element before them. If they're
3947  * NULL then we have found all pathkey elements to be used.
3948  */
3949  if (lop)
3950  {
3951  opathkey = (PathKey *) lfirst(lop);
3952  opeclass = opathkey->pk_eclass;
3953  if (oeclass == opeclass)
3954  {
3955  /* fast path for typical case */
3956  lop = lnext(lop);
3957  }
3958  else
3959  {
3960  /* redundant clauses ... must match something before lop */
3961  foreach(l2, outerpathkeys)
3962  {
3963  if (l2 == lop)
3964  break;
3965  opathkey = (PathKey *) lfirst(l2);
3966  opeclass = opathkey->pk_eclass;
3967  if (oeclass == opeclass)
3968  break;
3969  }
3970  if (oeclass != opeclass)
3971  elog(ERROR, "outer pathkeys do not match mergeclauses");
3972  }
3973  }
3974  else
3975  {
3976  /* redundant clauses ... must match some already-used pathkey */
3977  opathkey = NULL;
3978  opeclass = NULL;
3979  foreach(l2, outerpathkeys)
3980  {
3981  opathkey = (PathKey *) lfirst(l2);
3982  opeclass = opathkey->pk_eclass;
3983  if (oeclass == opeclass)
3984  break;
3985  }
3986  if (l2 == NULL)
3987  elog(ERROR, "outer pathkeys do not match mergeclauses");
3988  }
3989 
3990  if (lip)
3991  {
3992  ipathkey = (PathKey *) lfirst(lip);
3993  ipeclass = ipathkey->pk_eclass;
3994  if (ieclass == ipeclass)
3995  {
3996  /* fast path for typical case */
3997  lip = lnext(lip);
3998  }
3999  else
4000  {
4001  /* redundant clauses ... must match something before lip */
4002  foreach(l2, innerpathkeys)
4003  {
4004  if (l2 == lip)
4005  break;
4006  ipathkey = (PathKey *) lfirst(l2);
4007  ipeclass = ipathkey->pk_eclass;
4008  if (ieclass == ipeclass)
4009  break;
4010  }
4011  if (ieclass != ipeclass)
4012  elog(ERROR, "inner pathkeys do not match mergeclauses");
4013  }
4014  }
4015  else
4016  {
4017  /* redundant clauses ... must match some already-used pathkey */
4018  ipathkey = NULL;
4019  ipeclass = NULL;
4020  foreach(l2, innerpathkeys)
4021  {
4022  ipathkey = (PathKey *) lfirst(l2);
4023  ipeclass = ipathkey->pk_eclass;
4024  if (ieclass == ipeclass)
4025  break;
4026  }
4027  if (l2 == NULL)
4028  elog(ERROR, "inner pathkeys do not match mergeclauses");
4029  }
4030 
4031  /* pathkeys should match each other too (more debugging) */
4032  if (opathkey->pk_opfamily != ipathkey->pk_opfamily ||
4033  opathkey->pk_eclass->ec_collation != ipathkey->pk_eclass->ec_collation ||
4034  opathkey->pk_strategy != ipathkey->pk_strategy ||
4035  opathkey->pk_nulls_first != ipathkey->pk_nulls_first)
4036  elog(ERROR, "left and right pathkeys do not match in mergejoin");
4037 
4038  /* OK, save info for executor */
4039  mergefamilies[i] = opathkey->pk_opfamily;
4040  mergecollations[i] = opathkey->pk_eclass->ec_collation;
4041  mergestrategies[i] = opathkey->pk_strategy;
4042  mergenullsfirst[i] = opathkey->pk_nulls_first;
4043  i++;
4044  }
4045 
4046  /*
4047  * Note: it is not an error if we have additional pathkey elements (i.e.,
4048  * lop or lip isn't NULL here). The input paths might be better-sorted
4049  * than we need for the current mergejoin.
4050  */
4051 
4052  /*
4053  * Now we can build the mergejoin node.
4054  */
4055  join_plan = make_mergejoin(tlist,
4056  joinclauses,
4057  otherclauses,
4058  mergeclauses,
4059  mergefamilies,
4060  mergecollations,
4061  mergestrategies,
4062  mergenullsfirst,
4063  outer_plan,
4064  inner_plan,
4065  best_path->jpath.jointype,
4066  best_path->jpath.inner_unique,
4067  best_path->skip_mark_restore);
4068 
4069  /* Costs of sort and material steps are included in path cost already */
4070  copy_generic_path_info(&join_plan->join.plan, &best_path->jpath.path);
4071 
4072  return join_plan;
4073 }
4074 
4075 static HashJoin *
4077  HashPath *best_path)
4078 {
4079  HashJoin *join_plan;
4080  Hash *hash_plan;
4081  Plan *outer_plan;
4082  Plan *inner_plan;
4083  List *tlist = build_path_tlist(root, &best_path->jpath.path);
4084  List *joinclauses;
4085  List *otherclauses;
4086  List *hashclauses;
4087  Oid skewTable = InvalidOid;
4088  AttrNumber skewColumn = InvalidAttrNumber;
4089  bool skewInherit = false;
4090 
4091  /*
4092  * HashJoin can project, so we don't have to demand exact tlists from the
4093  * inputs. However, it's best to request a small tlist from the inner
4094  * side, so that we aren't storing more data than necessary. Likewise, if
4095  * we anticipate batching, request a small tlist from the outer side so
4096  * that we don't put extra data in the outer batch files.
4097  */
4098  outer_plan = create_plan_recurse(root, best_path->jpath.outerjoinpath,
4099  (best_path->num_batches > 1) ? CP_SMALL_TLIST : 0);
4100 
4101  inner_plan = create_plan_recurse(root, best_path->jpath.innerjoinpath,
4102  CP_SMALL_TLIST);
4103 
4104  /* Sort join qual clauses into best execution order */
4105  joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
4106  /* There's no point in sorting the hash clauses ... */
4107 
4108  /* Get the join qual clauses (in plain expression form) */
4109  /* Any pseudoconstant clauses are ignored here */
4110  if (IS_OUTER_JOIN(best_path->jpath.jointype))
4111  {
4112  extract_actual_join_clauses(joinclauses,
4113  &joinclauses, &otherclauses);
4114  }
4115  else
4116  {
4117  /* We can treat all clauses alike for an inner join */
4118  joinclauses = extract_actual_clauses(joinclauses, false);
4119  otherclauses = NIL;
4120  }
4121 
4122  /*
4123  * Remove the hashclauses from the list of join qual clauses, leaving the
4124  * list of quals that must be checked as qpquals.
4125  */
4126  hashclauses = get_actual_clauses(best_path->path_hashclauses);
4127  joinclauses = list_difference(joinclauses, hashclauses);
4128 
4129  /*
4130  * Replace any outer-relation variables with nestloop params. There
4131  * should not be any in the hashclauses.
4132  */
4133  if (best_path->jpath.path.param_info)
4134  {
4135  joinclauses = (List *)
4136  replace_nestloop_params(root, (Node *) joinclauses);
4137  otherclauses = (List *)
4138  replace_nestloop_params(root, (Node *) otherclauses);
4139  }
4140 
4141  /*
4142  * Rearrange hashclauses, if needed, so that the outer variable is always
4143  * on the left.
4144  */
4145  hashclauses = get_switched_clauses(best_path->path_hashclauses,
4146  best_path->jpath.outerjoinpath->parent->relids);
4147 
4148  /*
4149  * If there is a single join clause and we can identify the outer variable
4150  * as a simple column reference, supply its identity for possible use in
4151  * skew optimization. (Note: in principle we could do skew optimization
4152  * with multiple join clauses, but we'd have to be able to determine the
4153  * most common combinations of outer values, which we don't currently have
4154  * enough stats for.)
4155  */
4156  if (list_length(hashclauses) == 1)
4157  {
4158  OpExpr *clause = (OpExpr *) linitial(hashclauses);
4159  Node *node;
4160 
4161  Assert(is_opclause(clause));
4162  node = (Node *) linitial(clause->args);
4163  if (IsA(node, RelabelType))
4164  node = (Node *) ((RelabelType *) node)->arg;
4165  if (IsA(node, Var))
4166  {
4167  Var *var = (Var *) node;
4168  RangeTblEntry *rte;
4169 
4170  rte = root->simple_rte_array[var->varno];
4171  if (rte->rtekind == RTE_RELATION)
4172  {
4173  skewTable = rte->relid;
4174  skewColumn = var->varattno;
4175  skewInherit = rte->inh;
4176  }
4177  }
4178  }
4179 
4180  /*
4181  * Build the hash node and hash join node.
4182  */
4183  hash_plan = make_hash(inner_plan,
4184  skewTable,
4185  skewColumn,
4186  skewInherit);
4187 
4188  /*
4189  * Set Hash node's startup & total costs equal to total cost of input
4190  * plan; this only affects EXPLAIN display not decisions.
4191  */
4192  copy_plan_costsize(&hash_plan->plan, inner_plan);
4193  hash_plan->plan.startup_cost = hash_plan->plan.total_cost;
4194 
4195  /*
4196  * If parallel-aware, the executor will also need an estimate of the total
4197  * number of rows expected from all participants so that it can size the
4198  * shared hash table.
4199  */
4200  if (best_path->jpath.path.parallel_aware)
4201  {
4202  hash_plan->plan.parallel_aware = true;
4203  hash_plan->rows_total = best_path->inner_rows_total;
4204  }
4205 
4206  join_plan = make_hashjoin(tlist,
4207  joinclauses,
4208  otherclauses,
4209  hashclauses,
4210  outer_plan,
4211  (Plan *) hash_plan,
4212  best_path->jpath.jointype,
4213  best_path->jpath.inner_unique);
4214 
4215  copy_generic_path_info(&join_plan->join.plan, &best_path->jpath.path);
4216 
4217  return join_plan;
4218 }
4219 
4220 
4221 /*****************************************************************************
4222  *
4223  * SUPPORTING ROUTINES
4224  *
4225  *****************************************************************************/
4226 
4227 /*
4228  * replace_nestloop_params
4229  * Replace outer-relation Vars and PlaceHolderVars in the given expression
4230  * with nestloop Params
4231  *
4232  * All Vars and PlaceHolderVars belonging to the relation(s) identified by
4233  * root->curOuterRels are replaced by Params, and entries are added to
4234  * root->curOuterParams if not already present.
4235  */
4236 static Node *
4238 {
4239  /* No setup needed for tree walk, so away we go */
4240  return replace_nestloop_params_mutator(expr, root);
4241 }
4242 
4243 static Node *
4245 {
4246  if (node == NULL)
4247  return NULL;
4248  if (IsA(node, Var))
4249  {
4250  Var *var = (Var *) node;
4251  Param *param;
4252  NestLoopParam *nlp;
4253  ListCell *lc;
4254 
4255  /* Upper-level Vars should be long gone at this point */
4256  Assert(var->varlevelsup == 0);
4257  /* If not to be replaced, we can just return the Var unmodified */
4258  if (!bms_is_member(var->varno, root->curOuterRels))
4259  return node;
4260  /* Create a Param representing the Var */
4261  param = assign_nestloop_param_var(root, var);
4262  /* Is this param already listed in root->curOuterParams? */
4263  foreach(lc, root->curOuterParams)
4264  {
4265  nlp = (NestLoopParam *) lfirst(lc);
4266  if (nlp->paramno == param->paramid)
4267  {
4268  Assert(equal(var, nlp->paramval));
4269  /* Present, so we can just return the Param */
4270  return (Node *) param;
4271  }
4272  }
4273  /* No, so add it */
4274  nlp = makeNode(NestLoopParam);
4275  nlp->paramno = param->paramid;
4276  nlp->paramval = var;
4277  root->curOuterParams = lappend(root->curOuterParams, nlp);
4278  /* And return the replacement Param */
4279  return (Node *) param;
4280  }
4281  if (IsA(node, PlaceHolderVar))
4282  {
4283  PlaceHolderVar *phv = (PlaceHolderVar *) node;
4284  Param *param;
4285  NestLoopParam *nlp;
4286  ListCell *lc;
4287 
4288  /* Upper-level PlaceHolderVars should be long gone at this point */
4289  Assert(phv->phlevelsup == 0);
4290 
4291  /*
4292  * Check whether we need to replace the PHV. We use bms_overlap as a
4293  * cheap/quick test to see if the PHV might be evaluated in the outer
4294  * rels, and then grab its PlaceHolderInfo to tell for sure.
4295  */
4296  if (!bms_overlap(phv->phrels, root->curOuterRels) ||
4297  !bms_is_subset(find_placeholder_info(root, phv, false)->ph_eval_at,
4298  root->curOuterRels))
4299  {
4300  /*
4301  * We can't replace the whole PHV, but we might still need to
4302  * replace Vars or PHVs within its expression, in case it ends up
4303  * actually getting evaluated here. (It might get evaluated in
4304  * this plan node, or some child node; in the latter case we don't
4305  * really need to process the expression here, but we haven't got
4306  * enough info to tell if that's the case.) Flat-copy the PHV
4307  * node and then recurse on its expression.
4308  *
4309  * Note that after doing this, we might have different
4310  * representations of the contents of the same PHV in different
4311  * parts of the plan tree. This is OK because equal() will just
4312  * match on phid/phlevelsup, so setrefs.c will still recognize an
4313  * upper-level reference to a lower-level copy of the same PHV.
4314  */
4316 
4317  memcpy(newphv, phv, sizeof(PlaceHolderVar));
4318  newphv->phexpr = (Expr *)
4320  root);
4321  return (Node *) newphv;
4322  }
4323  /* Create a Param representing the PlaceHolderVar */
4324  param = assign_nestloop_param_placeholdervar(root, phv);
4325  /* Is this param already listed in root->curOuterParams? */
4326  foreach(lc, root->curOuterParams)
4327  {
4328  nlp = (NestLoopParam *) lfirst(lc);
4329  if (nlp->paramno == param->paramid)
4330  {
4331  Assert(equal(phv, nlp->paramval));
4332  /* Present, so we can just return the Param */
4333  return (Node *) param;
4334  }
4335  }
4336  /* No, so add it */
4337  nlp = makeNode(NestLoopParam);
4338  nlp->paramno = param->paramid;
4339  nlp->paramval = (Var *) phv;
4340  root->curOuterParams = lappend(root->curOuterParams, nlp);
4341  /* And return the replacement Param */
4342  return (Node *) param;
4343  }
4344  return expression_tree_mutator(node,
4346  (void *) root);
4347 }
4348 
4349 /*
4350  * process_subquery_nestloop_params
4351  * Handle params of a parameterized subquery that need to be fed
4352  * from an outer nestloop.
4353  *
4354  * Currently, that would be *all* params that a subquery in FROM has demanded
4355  * from the current query level, since they must be LATERAL references.
4356  *
4357  * The subplan's references to the outer variables are already represented
4358  * as PARAM_EXEC Params, so we need not modify the subplan here. What we
4359  * do need to do is add entries to root->curOuterParams to signal the parent
4360  * nestloop plan node that it must provide these values.
4361  */
4362 static void
4364 {
4365  ListCell *ppl;
4366 
4367  foreach(ppl, subplan_params)
4368  {
4369  PlannerParamItem *pitem = (PlannerParamItem *) lfirst(ppl);
4370 
4371  if (IsA(pitem->item, Var))
4372  {
4373  Var *var = (Var *) pitem->item;
4374  NestLoopParam *nlp;
4375  ListCell *lc;
4376 
4377  /* If not from a nestloop outer rel, complain */
4378  if (!bms_is_member(var->varno, root->curOuterRels))
4379  elog(ERROR, "non-LATERAL parameter required by subquery");
4380  /* Is this param already listed in root->curOuterParams? */
4381  foreach(lc, root->curOuterParams)
4382  {
4383  nlp = (NestLoopParam *) lfirst(lc);
4384  if (nlp->paramno == pitem->paramId)
4385  {
4386  Assert(equal(var, nlp->paramval));
4387  /* Present, so nothing to do */
4388  break;
4389  }
4390  }
4391  if (lc == NULL)
4392  {
4393  /* No, so add it */
4394  nlp = makeNode(NestLoopParam);
4395  nlp->paramno = pitem->paramId;
4396  nlp->paramval = copyObject(var);
4397  root->curOuterParams = lappend(root->curOuterParams, nlp);
4398  }
4399  }
4400  else if (IsA(pitem->item, PlaceHolderVar))
4401  {
4402  PlaceHolderVar *phv = (PlaceHolderVar *) pitem->item;
4403  NestLoopParam *nlp;
4404  ListCell *lc;
4405 
4406  /* If not from a nestloop outer rel, complain */
4407  if (!bms_is_subset(find_placeholder_info(root, phv, false)->ph_eval_at,
4408  root->curOuterRels))
4409  elog(ERROR, "non-LATERAL parameter required by subquery");
4410  /* Is this param already listed in root->curOuterParams? */
4411  foreach(lc, root->curOuterParams)
4412  {
4413  nlp = (NestLoopParam *) lfirst(lc);
4414  if (nlp->paramno == pitem->paramId)
4415  {
4416  Assert(equal(phv, nlp->paramval));
4417  /* Present, so nothing to do */
4418  break;
4419  }
4420  }
4421  if (lc == NULL)
4422  {
4423  /* No, so add it */
4424  nlp = makeNode(NestLoopParam);
4425  nlp->paramno = pitem->paramId;
4426  nlp->paramval = (Var *) copyObject(phv);
4427  root->curOuterParams = lappend(root->curOuterParams, nlp);
4428  }
4429  }
4430  else
4431  elog(ERROR, "unexpected type of subquery parameter");
4432  }
4433 }
4434 
4435 /*
4436  * fix_indexqual_references
4437  * Adjust indexqual clauses to the form the executor's indexqual
4438  * machinery needs.
4439  *
4440  * We have four tasks here:
4441  * * Remove RestrictInfo nodes from the input clauses.
4442  * * Replace any outer-relation Var or PHV nodes with nestloop Params.
4443  * (XXX eventually, that responsibility should go elsewhere?)
4444  * * Index keys must be represented by Var nodes with varattno set to the
4445  * index's attribute number, not the attribute number in the original rel.
4446  * * If the index key is on the right, commute the clause to put it on the
4447  * left.
4448  *
4449  * The result is a modified copy of the path's indexquals list --- the
4450  * original is not changed. Note also that the copy shares no substructure
4451  * with the original; this is needed in case there is a subplan in it (we need
4452  * two separate copies of the subplan tree, or things will go awry).
4453  */
4454 static List *
4456 {
4457  IndexOptInfo *index = index_path->indexinfo;
4458  List *fixed_indexquals;
4459  ListCell *lcc,
4460  *lci;
4461 
4462  fixed_indexquals = NIL;
4463 
4464  forboth(lcc, index_path->indexquals, lci, index_path->indexqualcols)
4465  {
4466  RestrictInfo *rinfo = lfirst_node(RestrictInfo, lcc);
4467  int indexcol = lfirst_int(lci);
4468  Node *clause;
4469 
4470  /*
4471  * Replace any outer-relation variables with nestloop params.
4472  *
4473  * This also makes a copy of the clause, so it's safe to modify it
4474  * in-place below.
4475  */
4476  clause = replace_nestloop_params(root, (Node *) rinfo->clause);
4477 
4478  if (IsA(clause, OpExpr))
4479  {
4480  OpExpr *op = (OpExpr *) clause;
4481 
4482  if (list_length(op->args) != 2)
4483  elog(ERROR, "indexqual clause is not binary opclause");
4484 
4485  /*
4486  * Check to see if the indexkey is on the right; if so, commute
4487  * the clause. The indexkey should be the side that refers to
4488  * (only) the base relation.
4489  */
4490  if (!bms_equal(rinfo->left_relids, index->rel->relids))
4491  CommuteOpExpr(op);
4492 
4493  /*
4494  * Now replace the indexkey expression with an index Var.
4495  */
4497  index,
4498  indexcol);
4499  }
4500  else if (IsA(clause, RowCompareExpr))
4501  {
4502  RowCompareExpr *rc = (RowCompareExpr *) clause;
4503  Expr *newrc;
4504  List *indexcolnos;
4505  bool var_on_left;
4506  ListCell *lca,
4507  *lcai;
4508 
4509  /*
4510  * Re-discover which index columns are used in the rowcompare.
4511  */
4512  newrc = adjust_rowcompare_for_index(rc,
4513  index,
4514  indexcol,
4515  &indexcolnos,
4516  &var_on_left);
4517 
4518  /*
4519  * Trouble if adjust_rowcompare_for_index thought the
4520  * RowCompareExpr didn't match the index as-is; the clause should
4521  * have gone through that routine already.
4522  */
4523  if (newrc != (Expr *) rc)
4524  elog(ERROR, "inconsistent results from adjust_rowcompare_for_index");
4525 
4526  /*
4527  * Check to see if the indexkey is on the right; if so, commute
4528  * the clause.
4529  */
4530  if (!var_on_left)
4532 
4533  /*
4534  * Now replace the indexkey expressions with index Vars.
4535  */
4536  Assert(list_length(rc->largs) == list_length(indexcolnos));
4537  forboth(lca, rc->largs, lcai, indexcolnos)
4538  {
4539  lfirst(lca) = fix_indexqual_operand(lfirst(lca),
4540  index,
4541  lfirst_int(lcai));
4542  }
4543  }
4544  else if (IsA(clause, ScalarArrayOpExpr))
4545  {
4546  ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) clause;
4547 
4548  /* Never need to commute... */
4549 
4550  /* Replace the indexkey expression with an index Var. */
4552  index,
4553  indexcol);
4554  }
4555  else if (IsA(clause, NullTest))
4556  {
4557  NullTest *nt = (NullTest *) clause;
4558 
4559  /* Replace the indexkey expression with an index Var. */
4560  nt->arg = (Expr *) fix_indexqual_operand((Node *) nt->arg,
4561  index,
4562  indexcol);
4563  }
4564  else
4565  elog(ERROR, "unsupported indexqual type: %d",
4566  (int) nodeTag(clause));
4567 
4568  fixed_indexquals = lappend(fixed_indexquals, clause);
4569  }
4570 
4571  return fixed_indexquals;
4572 }
4573 
4574 /*
4575  * fix_indexorderby_references
4576  * Adjust indexorderby clauses to the form the executor's index
4577  * machinery needs.
4578  *
4579  * This is a simplified version of fix_indexqual_references. The input does
4580  * not have RestrictInfo nodes, and we assume that indxpath.c already
4581  * commuted the clauses to put the index keys on the left. Also, we don't
4582  * bother to support any cases except simple OpExprs, since nothing else
4583  * is allowed for ordering operators.
4584  */
4585 static List *
4587 {
4588  IndexOptInfo *index = index_path->indexinfo;
4589  List *fixed_indexorderbys;
4590  ListCell *lcc,
4591  *lci;
4592 
4593  fixed_indexorderbys = NIL;
4594 
4595  forboth(lcc, index_path->indexorderbys, lci, index_path->indexorderbycols)
4596  {
4597  Node *clause = (Node *) lfirst(lcc);
4598  int indexcol = lfirst_int(lci);
4599 
4600  /*
4601  * Replace any outer-relation variables with nestloop params.
4602  *
4603  * This also makes a copy of the clause, so it's safe to modify it
4604  * in-place below.
4605  */
4606  clause = replace_nestloop_params(root, clause);
4607 
4608  if (IsA(clause, OpExpr))
4609  {
4610  OpExpr *op = (OpExpr *) clause;
4611 
4612  if (list_length(op->args) != 2)
4613  elog(ERROR, "indexorderby clause is not binary opclause");
4614 
4615  /*
4616  * Now replace the indexkey expression with an index Var.
4617  */
4619  index,
4620  indexcol);
4621  }
4622  else
4623  elog(ERROR, "unsupported indexorderby type: %d",
4624  (int) nodeTag(clause));
4625 
4626  fixed_indexorderbys = lappend(fixed_indexorderbys, clause);
4627  }
4628 
4629  return fixed_indexorderbys;
4630 }
4631 
4632 /*
4633  * fix_indexqual_operand
4634  * Convert an indexqual expression to a Var referencing the index column.
4635  *
4636  * We represent index keys by Var nodes having varno == INDEX_VAR and varattno
4637  * equal to the index's attribute number (index column position).
4638  *
4639  * Most of the code here is just for sanity cross-checking that the given
4640  * expression actually matches the index column it's claimed to.
4641  */
4642 static Node *
4644 {
4645  Var *result;
4646  int pos;
4647  ListCell *indexpr_item;
4648 
4649  /*
4650  * Remove any binary-compatible relabeling of the indexkey
4651  */
4652  if (IsA(node, RelabelType))
4653  node = (Node *) ((RelabelType *) node)->arg;
4654 
4655  Assert(indexcol >= 0 && indexcol < index->ncolumns);
4656 
4657  if (index->indexkeys[indexcol] != 0)
4658  {
4659  /* It's a simple index column */
4660  if (IsA(node, Var) &&
4661  ((Var *) node)->varno == index->rel->relid &&
4662  ((Var *) node)->varattno == index->indexkeys[indexcol])
4663  {
4664  result = (Var *) copyObject(node);
4665  result->varno = INDEX_VAR;
4666  result->varattno = indexcol + 1;
4667  return (Node *) result;
4668  }
4669  else
4670  elog(ERROR, "index key does not match expected index column");
4671  }
4672 
4673  /* It's an index expression, so find and cross-check the expression */
4674  indexpr_item = list_head(index->indexprs);
4675  for (pos = 0; pos < index->ncolumns; pos++)
4676  {
4677  if (index->indexkeys[pos] == 0)
4678  {
4679  if (indexpr_item == NULL)
4680  elog(ERROR, "too few entries in indexprs list");
4681  if (pos == indexcol)
4682  {
4683  Node *indexkey;
4684 
4685  indexkey = (Node *) lfirst(indexpr_item);
4686  if (indexkey && IsA(indexkey, RelabelType))
4687  indexkey = (Node *) ((RelabelType *) indexkey)->arg;
4688  if (equal(node, indexkey))
4689  {
4690  result = makeVar(INDEX_VAR, indexcol + 1,
4691  exprType(lfirst(indexpr_item)), -1,
4692  exprCollation(lfirst(indexpr_item)),
4693  0);
4694  return (Node *) result;
4695  }
4696  else
4697  elog(ERROR, "index key does not match expected index column");
4698  }
4699  indexpr_item = lnext(indexpr_item);
4700  }
4701  }
4702 
4703  /* Oops... */
4704  elog(ERROR, "index key does not match expected index column");
4705  return NULL; /* keep compiler quiet */
4706 }
4707 
4708 /*
4709  * get_switched_clauses
4710  * Given a list of merge or hash joinclauses (as RestrictInfo nodes),
4711  * extract the bare clauses, and rearrange the elements within the
4712  * clauses, if needed, so the outer join variable is on the left and
4713  * the inner is on the right. The original clause data structure is not
4714  * touched; a modified list is returned. We do, however, set the transient
4715  * outer_is_left field in each RestrictInfo to show which side was which.
4716  */
4717 static List *
4718 get_switched_clauses(List *clauses, Relids outerrelids)
4719 {
4720  List *t_list = NIL;
4721  ListCell *l;
4722 
4723  foreach(l, clauses)
4724  {
4725  RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(l);
4726  OpExpr *clause = (OpExpr *) restrictinfo->clause;
4727 
4728  Assert(is_opclause(clause));
4729  if (bms_is_subset(restrictinfo->right_relids, outerrelids))
4730  {
4731  /*
4732  * Duplicate just enough of the structure to allow commuting the
4733  * clause without changing the original list. Could use
4734  * copyObject, but a complete deep copy is overkill.
4735  */
4736  OpExpr *temp = makeNode(OpExpr);
4737 
4738  temp->opno = clause->opno;
4739  temp->opfuncid = InvalidOid;
4740  temp->opresulttype = clause->opresulttype;
4741  temp->opretset = clause->opretset;
4742  temp->opcollid = clause->opcollid;
4743  temp->inputcollid = clause->inputcollid;
4744  temp->args = list_copy(clause->args);
4745  temp->location = clause->location;
4746  /* Commute it --- note this modifies the temp node in-place. */
4747  CommuteOpExpr(temp);
4748  t_list = lappend(t_list, temp);
4749  restrictinfo->outer_is_left = false;
4750  }
4751  else
4752  {
4753  Assert(bms_is_subset(restrictinfo->left_relids, outerrelids));
4754  t_list = lappend(t_list, clause);
4755  restrictinfo->outer_is_left = true;
4756  }
4757  }
4758  return t_list;
4759 }
4760 
4761 /*
4762  * order_qual_clauses
4763  * Given a list of qual clauses that will all be evaluated at the same
4764  * plan node, sort the list into the order we want to check the quals
4765  * in at runtime.
4766  *
4767  * When security barrier quals are used in the query, we may have quals with
4768  * different security levels in the list. Quals of lower security_level
4769  * must go before quals of higher security_level, except that we can grant
4770  * exceptions to move up quals that are leakproof. When security level
4771  * doesn't force the decision, we prefer to order clauses by estimated
4772  * execution cost, cheapest first.
4773  *
4774  * Ideally the order should be driven by a combination of execution cost and
4775  * selectivity, but it's not immediately clear how to account for both,
4776  * and given the uncertainty of the estimates the reliability of the decisions
4777  * would be doubtful anyway. So we just order by security level then
4778  * estimated per-tuple cost, being careful not to change the order when
4779  * (as is often the case) the estimates are identical.
4780  *
4781  * Although this will work on either bare clauses or RestrictInfos, it's
4782  * much faster to apply it to RestrictInfos, since it can re-use cost
4783  * information that is cached in RestrictInfos. XXX in the bare-clause
4784  * case, we are also not able to apply security considerations. That is
4785  * all right for the moment, because the bare-clause case doesn't occur
4786  * anywhere that barrier quals could be present, but it would be better to
4787  * get rid of it.
4788  *
4789  * Note: some callers pass lists that contain entries that will later be
4790  * removed; this is the easiest way to let this routine see RestrictInfos
4791  * instead of bare clauses. This is another reason why trying to consider
4792  * selectivity in the ordering would likely do the wrong thing.
4793  */
4794 static List *
4796 {
4797  typedef struct
4798  {
4799  Node *clause;
4800  Cost cost;
4801  Index security_level;
4802  } QualItem;
4803  int nitems = list_length(clauses);
4804  QualItem *items;
4805  ListCell *lc;
4806  int i;
4807  List *result;
4808 
4809  /* No need to work hard for 0 or 1 clause */
4810  if (nitems <= 1)
4811  return clauses;
4812 
4813  /*
4814  * Collect the items and costs into an array. This is to avoid repeated
4815  * cost_qual_eval work if the inputs aren't RestrictInfos.
4816  */
4817  items = (QualItem *) palloc(nitems * sizeof(QualItem));
4818  i = 0;
4819  foreach(lc, clauses)
4820  {
4821  Node *clause = (Node *) lfirst(lc);
4822  QualCost qcost;
4823 
4824  cost_qual_eval_node(&qcost, clause, root);
4825  items[i].clause = clause;
4826  items[i].cost = qcost.per_tuple;
4827  if (IsA(clause, RestrictInfo))
4828  {
4829  RestrictInfo *rinfo = (RestrictInfo *) clause;
4830 
4831  /*
4832  * If a clause is leakproof, it doesn't have to be constrained by
4833  * its nominal security level. If it's also reasonably cheap
4834  * (here defined as 10X cpu_operator_cost), pretend it has
4835  * security_level 0, which will allow it to go in front of
4836  * more-expensive quals of lower security levels. Of course, that
4837  * will also force it to go in front of cheaper quals of its own
4838  * security level, which is not so great, but we can alleviate
4839  * that risk by applying the cost limit cutoff.
4840  */
4841  if (rinfo->leakproof && items[i].cost < 10 * cpu_operator_cost)
4842  items[i].security_level = 0;
4843  else
4844  items[i].security_level = rinfo->security_level;
4845  }
4846  else
4847  items[i].security_level = 0;
4848  i++;
4849  }
4850 
4851  /*
4852  * Sort. We don't use qsort() because it's not guaranteed stable for
4853  * equal keys. The expected number of entries is small enough that a
4854  * simple insertion sort should be good enough.
4855  */
4856  for (i = 1; i < nitems; i++)
4857  {
4858  QualItem newitem = items[i];
4859  int j;
4860 
4861  /* insert newitem into the already-sorted subarray */
4862  for (j = i; j > 0; j--)
4863  {
4864  QualItem *olditem = &items[j - 1];
4865 
4866  if (newitem.security_level > olditem->security_level ||
4867  (newitem.security_level == olditem->security_level &&
4868  newitem.cost >= olditem->cost))
4869  break;
4870  items[j] = *olditem;
4871  }
4872  items[j] = newitem;
4873  }
4874 
4875  /* Convert back to a list */
4876  result = NIL;
4877  for (i = 0; i < nitems; i++)
4878  result = lappend(result, items[i].clause);
4879 
4880  return result;
4881 }
4882 
4883 /*
4884  * Copy cost and size info from a Path node to the Plan node created from it.
4885  * The executor usually won't use this info, but it's needed by EXPLAIN.
4886  * Also copy the parallel-related flags, which the executor *will* use.
4887  */
4888 static void
4890 {
4891  dest->startup_cost = src->startup_cost;
4892  dest->total_cost = src->total_cost;
4893  dest->plan_rows = src->rows;
4894  dest->plan_width = src->pathtarget->width;
4895  dest->parallel_aware = src->parallel_aware;
4896  dest->parallel_safe = src->parallel_safe;
4897 }
4898 
4899 /*
4900  * Copy cost and size info from a lower plan node to an inserted node.
4901  * (Most callers alter the info after copying it.)
4902  */
4903 static void
4905 {
4906  dest->startup_cost = src->startup_cost;
4907  dest->total_cost = src->total_cost;
4908  dest->plan_rows = src->plan_rows;
4909  dest->plan_width = src->plan_width;
4910  /* Assume the inserted node is not parallel-aware. */
4911  dest->parallel_aware = false;
4912  /* Assume the inserted node is parallel-safe, if child plan is. */
4913  dest->parallel_safe = src->parallel_safe;
4914 }
4915 
4916 /*
4917  * Some places in this file build Sort nodes that don't have a directly
4918  * corresponding Path node. The cost of the sort is, or should have been,
4919  * included in the cost of the Path node we're working from, but since it's
4920  * not split out, we have to re-figure it using cost_sort(). This is just
4921  * to label the Sort node nicely for EXPLAIN.
4922  *
4923  * limit_tuples is as for cost_sort (in particular, pass -1 if no limit)
4924  */
4925 static void
4926 label_sort_with_costsize(PlannerInfo *root, Sort *plan, double limit_tuples)
4927 {
4928  Plan *lefttree = plan->plan.lefttree;
4929  Path sort_path; /* dummy for result of cost_sort */
4930 
4931  cost_sort(&sort_path, root, NIL,
4932  lefttree->total_cost,
4933  lefttree->plan_rows,
4934  lefttree->plan_width,
4935  0.0,
4936  work_mem,
4937  limit_tuples);
4938  plan->plan.startup_cost = sort_path.startup_cost;
4939  plan->plan.total_cost = sort_path.total_cost;
4940  plan->plan.plan_rows = lefttree->plan_rows;
4941  plan->plan.plan_width = lefttree->plan_width;
4942  plan->plan.parallel_aware = false;
4943  plan->plan.parallel_safe = lefttree->parallel_safe;
4944 }
4945 
4946 /*
4947  * bitmap_subplan_mark_shared
4948  * Set isshared flag in bitmap subplan so that it will be created in
4949  * shared memory.
4950  */
4951 static void
4953 {
4954  if (IsA(plan, BitmapAnd))
4956  linitial(((BitmapAnd *) plan)->bitmapplans));
4957  else if (IsA(plan, BitmapOr))
4958  {
4959  ((BitmapOr *) plan)->isshared = true;
4961  linitial(((BitmapOr *) plan)->bitmapplans));
4962  }
4963  else if (IsA(plan, BitmapIndexScan))
4964  ((BitmapIndexScan *) plan)->isshared = true;
4965  else
4966  elog(ERROR, "unrecognized node type: %d", nodeTag(plan));
4967 }
4968 
4969 /*****************************************************************************
4970  *
4971  * PLAN NODE BUILDING ROUTINES
4972  *
4973  * In general, these functions are not passed the original Path and therefore
4974  * leave it to the caller to fill in the cost/width fields from the Path,
4975  * typically by calling copy_generic_path_info(). This convention is
4976  * somewhat historical, but it does support a few places above where we build
4977  * a plan node without having an exactly corresponding Path node. Under no
4978  * circumstances should one of these functions do its own cost calculations,
4979  * as that would be redundant with calculations done while building Paths.
4980  *
4981  *****************************************************************************/
4982 
4983 static SeqScan *
4985  List *qpqual,
4986  Index scanrelid)
4987 {
4988  SeqScan *node = makeNode(SeqScan);
4989  Plan *plan = &node->plan;
4990 
4991  plan->targetlist = qptlist;
4992  plan->qual = qpqual;
4993  plan->lefttree = NULL;
4994  plan->righttree = NULL;
4995  node->scanrelid = scanrelid;
4996 
4997  return node;
4998 }
4999 
5000 static SampleScan *
5002  List *qpqual,
5003  Index scanrelid,
5004  TableSampleClause *tsc)
5005 {
5006  SampleScan *node = makeNode(SampleScan);
5007  Plan *plan = &node->scan.plan;
5008 
5009  plan->targetlist = qptlist;
5010  plan->qual = qpqual;
5011  plan->lefttree = NULL;
5012  plan->righttree = NULL;
5013  node->scan.scanrelid = scanrelid;
5014  node->tablesample = tsc;
5015 
5016  return node;
5017 }
5018 
5019 static IndexScan *
5021  List *qpqual,
5022  Index scanrelid,
5023  Oid indexid,
5024  List *indexqual,
5025  List *indexqualorig,
5026  List *indexorderby,
5027  List *indexorderbyorig,
5028  List *indexorderbyops,
5029  ScanDirection indexscandir)
5030 {
5031  IndexScan *node = makeNode(IndexScan);
5032  Plan *plan = &node->scan.plan;
5033 
5034  plan->targetlist = qptlist;
5035  plan->qual = qpqual;
5036  plan->lefttree = NULL;
5037  plan->righttree = NULL;
5038  node->scan.scanrelid = scanrelid;
5039  node->indexid = indexid;
5040  node->indexqual = indexqual;
5041  node->indexqualorig = indexqualorig;
5042  node->indexorderby = indexorderby;
5043  node->indexorderbyorig = indexorderbyorig;
5044  node->indexorderbyops = indexorderbyops;
5045  node->indexorderdir = indexscandir;
5046 
5047  return node;
5048 }
5049 
5050 static IndexOnlyScan *
5052  List *qpqual,
5053  Index scanrelid,
5054  Oid indexid,
5055  List *indexqual,
5056  List *indexorderby,
5057  List *indextlist,
5058  ScanDirection indexscandir)
5059 {
5061  Plan *plan = &node->scan.plan;
5062 
5063  plan->targetlist = qptlist;
5064  plan->qual = qpqual;
5065  plan->lefttree = NULL;
5066  plan->righttree = NULL;
5067  node->scan.scanrelid = scanrelid;
5068  node->indexid = indexid;
5069  node->indexqual = indexqual;
5070  node->indexorderby = indexorderby;
5071  node->indextlist = indextlist;
5072  node->indexorderdir = indexscandir;
5073 
5074  return node;
5075 }
5076 
5077 static BitmapIndexScan *
5079  Oid indexid,
5080  List *indexqual,
5081  List *indexqualorig)
5082 {
5084  Plan *plan = &node->scan.plan;
5085 
5086  plan->targetlist = NIL; /* not used */
5087  plan->qual = NIL; /* not used */
5088  plan->lefttree = NULL;
5089  plan->righttree = NULL;
5090  node->scan.scanrelid = scanrelid;
5091  node->indexid = indexid;
5092  node->indexqual = indexqual;
5093  node->indexqualorig = indexqualorig;
5094 
5095  return node;
5096 }
5097 
5098 static BitmapHeapScan *
5100  List *qpqual,
5101  Plan *lefttree,
5102  List *bitmapqualorig,
5103  Index scanrelid)
5104 {
5106  Plan *plan = &node->scan.plan;
5107 
5108  plan->targetlist = qptlist;
5109  plan->qual = qpqual;
5110  plan->lefttree = lefttree;
5111  plan->righttree = NULL;
5112  node->scan.scanrelid = scanrelid;
5113  node->bitmapqualorig = bitmapqualorig;
5114 
5115  return node;
5116 }
5117 
5118 static TidScan *
5120  List *qpqual,
5121  Index scanrelid,
5122  List *tidquals)
5123 {
5124  TidScan *node = makeNode(TidScan);
5125  Plan *plan = &node->scan.plan;
5126 
5127  plan->targetlist = qptlist;
5128  plan->qual = qpqual;
5129  plan->lefttree = NULL;
5130  plan->righttree = NULL;
5131  node->scan.scanrelid = scanrelid;
5132  node->tidquals = tidquals;
5133 
5134  return node;
5135 }
5136 
5137 static SubqueryScan *
5139  List *qpqual,
5140  Index scanrelid,
5141  Plan *subplan)
5142 {
5144  Plan *plan = &node->scan.plan;
5145 
5146  plan->targetlist = qptlist;
5147  plan->qual = qpqual;
5148  plan->lefttree = NULL;
5149  plan->righttree = NULL;
5150  node->scan.scanrelid = scanrelid;
5151  node->subplan = subplan;
5152 
5153  return node;
5154 }
5155 
5156 static FunctionScan *
5158  List *qpqual,
5159  Index scanrelid,
5160  List *functions,
5161  bool funcordinality)
5162 {
5164  Plan *plan = &node->scan.plan;
5165 
5166  plan->targetlist = qptlist;
5167  plan->qual = qpqual;
5168  plan->lefttree = NULL;
5169  plan->righttree = NULL;
5170  node->scan.scanrelid = scanrelid;
5171  node->functions = functions;
5172  node->funcordinality = funcordinality;
5173 
5174  return node;
5175 }
5176 
5177 static TableFuncScan *
5179  List *qpqual,
5180  Index scanrelid,
5181  TableFunc *tablefunc)
5182 {
5184  Plan *plan = &node->scan.plan;
5185 
5186  plan->targetlist = qptlist;
5187  plan->qual = qpqual;
5188  plan->lefttree = NULL;
5189  plan->righttree = NULL;
5190  node->scan.scanrelid = scanrelid;
5191  node->tablefunc = tablefunc;
5192 
5193  return node;
5194 }
5195 
5196 static ValuesScan *
5198  List *qpqual,
5199  Index scanrelid,
5200  List *values_lists)
5201 {
5202  ValuesScan *node = makeNode(ValuesScan);
5203  Plan *plan = &node->scan.plan;
5204 
5205  plan->targetlist = qptlist;
5206  plan->qual = qpqual;
5207  plan->lefttree = NULL;
5208  plan->righttree = NULL;
5209  node->scan.scanrelid = scanrelid;
5210  node->values_lists = values_lists;
5211 
5212  return node;
5213 }
5214 
5215 static CteScan *
5217  List *qpqual,
5218  Index scanrelid,
5219  int ctePlanId,
5220  int cteParam)
5221 {
5222  CteScan *node = makeNode(CteScan);
5223  Plan *plan = &node->scan.plan;
5224 
5225  plan->targetlist = qptlist;
5226  plan->qual = qpqual;
5227  plan->lefttree = NULL;
5228  plan->righttree = NULL;
5229  node->scan.scanrelid = scanrelid;
5230  node->ctePlanId = ctePlanId;
5231  node->cteParam = cteParam;
5232 
5233  return node;
5234 }
5235 
5236 static NamedTuplestoreScan *
5238  List *qpqual,
5239  Index scanrelid,
5240  char *enrname)
5241 {
5243  Plan *plan = &node->scan.plan;
5244 
5245  /* cost should be inserted by caller */
5246  plan->targetlist = qptlist;
5247  plan->qual = qpqual;
5248  plan->lefttree = NULL;
5249  plan->righttree = NULL;
5250  node->scan.scanrelid = scanrelid;
5251  node->enrname = enrname;
5252 
5253  return node;
5254 }
5255 
5256 static WorkTableScan *
5258  List *qpqual,
5259  Index scanrelid,
5260  int wtParam)
5261 {
5263  Plan *plan = &node->scan.plan;
5264 
5265  plan->targetlist = qptlist;
5266  plan->qual = qpqual;
5267  plan->lefttree = NULL;
5268  plan->righttree = NULL;
5269  node->scan.scanrelid = scanrelid;
5270  node->wtParam = wtParam;
5271 
5272  return node;
5273 }
5274 
5275 ForeignScan *
5277  List *qpqual,
5278  Index scanrelid,
5279  List *fdw_exprs,
5280  List *fdw_private,
5281  List *fdw_scan_tlist,
5282  List *fdw_recheck_quals,
5283  Plan *outer_plan)
5284 {
5285  ForeignScan *node = makeNode(ForeignScan);
5286  Plan *plan = &node->scan.plan;
5287 
5288  /* cost will be filled in by create_foreignscan_plan */
5289  plan->targetlist = qptlist;
5290  plan->qual = qpqual;
5291  plan->lefttree = outer_plan;
5292  plan->righttree = NULL;
5293  node->scan.scanrelid = scanrelid;
5294  node->operation = CMD_SELECT;
5295  /* fs_server will be filled in by create_foreignscan_plan */
5296  node->fs_server = InvalidOid;
5297  node->fdw_exprs = fdw_exprs;
5298  node->fdw_private = fdw_private;
5299  node->fdw_scan_tlist = fdw_scan_tlist;
5300  node->fdw_recheck_quals = fdw_recheck_quals;
5301  /* fs_relids will be filled in by create_foreignscan_plan */
5302  node->fs_relids = NULL;
5303  /* fsSystemCol will be filled in by create_foreignscan_plan */
5304  node->fsSystemCol = false;
5305 
5306  return node;
5307 }
5308 
5309 static Append *
5310 make_append(List *appendplans, int first_partial_plan,
5311  List *tlist, List *partitioned_rels)
5312 {
5313  Append *node = makeNode(Append);
5314  Plan *plan = &node->plan;
5315 
5316  plan->targetlist = tlist;
5317  plan->qual = NIL;
5318  plan->lefttree = NULL;
5319  plan->righttree = NULL;
5320  node->partitioned_rels = partitioned_rels;
5321  node->appendplans = appendplans;
5322  node->first_partial_plan = first_partial_plan;
5323 
5324  return node;
5325 }
5326 
5327 static RecursiveUnion *
5329  Plan *lefttree,
5330  Plan *righttree,
5331  int wtParam,
5332  List *distinctList,
5333  long numGroups)
5334 {
5336  Plan *plan = &node->plan;
5337  int numCols = list_length(distinctList);
5338 
5339  plan->targetlist = tlist;
5340  plan->qual = NIL;
5341  plan->lefttree = lefttree;
5342  plan->righttree = righttree;
5343  node->wtParam = wtParam;
5344 
5345  /*
5346  * convert SortGroupClause list into arrays of attr indexes and equality
5347  * operators, as wanted by executor
5348  */
5349  node->numCols = numCols;
5350  if (numCols > 0)
5351  {
5352  int keyno = 0;
5353  AttrNumber *dupColIdx;
5354  Oid *dupOperators;
5355  ListCell *slitem;
5356 
5357  dupColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
5358  dupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
5359 
5360  foreach(slitem, distinctList)
5361  {
5362  SortGroupClause *sortcl = (SortGroupClause *) lfirst(slitem);
5363  TargetEntry *tle = get_sortgroupclause_tle(sortcl,
5364  plan->targetlist);
5365 
5366  dupColIdx[keyno] = tle->resno;
5367  dupOperators[keyno] = sortcl->eqop;
5368  Assert(OidIsValid(dupOperators[keyno]));
5369  keyno++;
5370  }
5371  node->dupColIdx = dupColIdx;
5372  node->dupOperators = dupOperators;
5373  }
5374  node->numGroups = numGroups;
5375 
5376  return node;
5377 }
5378 
5379 static BitmapAnd *
5380 make_bitmap_and(List *bitmapplans)
5381 {
5382  BitmapAnd *node = makeNode(BitmapAnd);
5383  Plan *plan = &node->plan;
5384 
5385  plan->targetlist = NIL;
5386  plan->qual = NIL;
5387  plan->lefttree = NULL;
5388  plan->righttree = NULL;
5389  node->bitmapplans = bitmapplans;
5390 
5391  return node;
5392 }
5393 
5394 static BitmapOr *
5395 make_bitmap_or(List *bitmapplans)
5396 {
5397  BitmapOr *node = makeNode(BitmapOr);
5398  Plan *plan = &node->plan;
5399 
5400  plan->targetlist = NIL;
5401  plan->qual = NIL;
5402  plan->lefttree = NULL;
5403  plan->righttree = NULL;
5404  node->bitmapplans = bitmapplans;
5405 
5406  return node;
5407 }
5408 
5409 static NestLoop *
5411  List *joinclauses,
5412  List *otherclauses,
5413  List *nestParams,
5414  Plan *lefttree,
5415  Plan *righttree,
5416  JoinType jointype,
5417  bool inner_unique)
5418 {
5419  NestLoop *node = makeNode(NestLoop);
5420  Plan *plan = &node->join.plan;
5421 
5422  plan->targetlist = tlist;
5423  plan->qual = otherclauses;
5424  plan->lefttree = lefttree;
5425  plan->righttree = righttree;
5426  node->join.jointype = jointype;
5427  node->join.inner_unique = inner_unique;
5428  node->join.joinqual = joinclauses;
5429  node->nestParams = nestParams;
5430 
5431  return node;
5432 }
5433 
5434 static HashJoin *
5436  List *joinclauses,
5437  List *otherclauses,
5438  List *hashclauses,
5439  Plan *lefttree,
5440  Plan *righttree,
5441  JoinType jointype,
5442  bool inner_unique)
5443 {
5444  HashJoin *node = makeNode(HashJoin);
5445  Plan *plan = &node->join.plan;
5446 
5447  plan->targetlist = tlist;
5448  plan->qual = otherclauses;
5449  plan->lefttree = lefttree;
5450  plan->righttree = righttree;
5451  node->hashclauses = hashclauses;
5452  node->join.jointype = jointype;
5453  node->join.inner_unique = inner_unique;
5454  node->join.joinqual = joinclauses;
5455 
5456  return node;
5457 }
5458 
5459 static Hash *
5460 make_hash(Plan *lefttree,
5461  Oid skewTable,
5462  AttrNumber skewColumn,
5463  bool skewInherit)
5464 {
5465  Hash *node = makeNode(Hash);
5466  Plan *plan = &node->plan;
5467 
5468  plan->targetlist = lefttree->targetlist;
5469  plan->qual = NIL;
5470  plan->lefttree = lefttree;
5471  plan->righttree = NULL;
5472 
5473  node->skewTable = skewTable;
5474  node->skewColumn = skewColumn;
5475  node->skewInherit = skewInherit;
5476 
5477  return node;
5478 }
5479 
5480 static MergeJoin *
5482  List *joinclauses,
5483  List *otherclauses,
5484  List *mergeclauses,
5485  Oid *mergefamilies,
5486  Oid *mergecollations,
5487  int *mergestrategies,
5488  bool *mergenullsfirst,
5489  Plan *lefttree,
5490  Plan *righttree,
5491  JoinType jointype,
5492  bool inner_unique,
5493  bool skip_mark_restore)
5494 {
5495  MergeJoin *node = makeNode(MergeJoin);
5496  Plan *plan = &node->join.plan;
5497 
5498  plan->targetlist = tlist;
5499  plan->qual = otherclauses;
5500  plan->lefttree = lefttree;
5501  plan->righttree = righttree;
5502  node->skip_mark_restore = skip_mark_restore;
5503  node->mergeclauses = mergeclauses;
5504  node->mergeFamilies = mergefamilies;
5505  node->mergeCollations = mergecollations;
5506  node->mergeStrategies = mergestrategies;
5507  node->mergeNullsFirst = mergenullsfirst;
5508  node->join.jointype = jointype;
5509  node->join.inner_unique = inner_unique;
5510  node->join.joinqual = joinclauses;
5511 
5512  return node;
5513 }
5514 
5515 /*
5516  * make_sort --- basic routine to build a Sort plan node
5517  *
5518  * Caller must have built the sortColIdx, sortOperators, collations, and
5519  * nullsFirst arrays already.
5520  */
5521 static Sort *
5522 make_sort(Plan *lefttree, int numCols,
5523  AttrNumber *sortColIdx, Oid *sortOperators,
5524  Oid *collations, bool *nullsFirst)
5525 {
5526  Sort *node = makeNode(Sort);
5527  Plan *plan = &node->plan;
5528 
5529  plan->targetlist = lefttree->targetlist;
5530  plan->qual = NIL;
5531  plan->lefttree = lefttree;
5532  plan->righttree = NULL;
5533  node->numCols = numCols;
5534  node->sortColIdx = sortColIdx;
5535  node->sortOperators = sortOperators;
5536  node->collations = collations;
5537  node->nullsFirst = nullsFirst;
5538 
5539  return node;
5540 }
5541 
5542 /*
5543  * prepare_sort_from_pathkeys
5544  * Prepare to sort according to given pathkeys
5545  *
5546  * This is used to set up for Sort, MergeAppend, and Gather Merge nodes. It
5547  * calculates the executor's representation of the sort key information, and
5548  * adjusts the plan targetlist if needed to add resjunk sort columns.
5549  *
5550  * Input parameters:
5551  * 'lefttree' is the plan node which yields input tuples
5552  * 'pathkeys' is the list of pathkeys by which the result is to be sorted
5553  * 'relids' identifies the child relation being sorted, if any
5554  * 'reqColIdx' is NULL or an array of required sort key column numbers
5555  * 'adjust_tlist_in_place' is true if lefttree must be modified in-place
5556  *
5557  * We must convert the pathkey information into arrays of sort key column
5558  * numbers, sort operator OIDs, collation OIDs, and nulls-first flags,
5559  * which is the representation the executor wants. These are returned into
5560  * the output parameters *p_numsortkeys etc.
5561  *
5562  * When looking for matches to an EquivalenceClass's members, we will only
5563  * consider child EC members if they belong to given 'relids'. This protects
5564  * against possible incorrect matches to child expressions that contain no
5565  * Vars.
5566  *
5567  * If reqColIdx isn't NULL then it contains sort key column numbers that
5568  * we should match. This is used when making child plans for a MergeAppend;
5569  * it's an error if we can't match the columns.
5570  *
5571  * If the pathkeys include expressions that aren't simple Vars, we will
5572  * usually need to add resjunk items to the input plan's targetlist to
5573  * compute these expressions, since a Sort or MergeAppend node itself won't
5574  * do any such calculations. If the input plan type isn't one that can do
5575  * projections, this means adding a Result node just to do the projection.
5576  * However, the caller can pass adjust_tlist_in_place = true to force the
5577  * lefttree tlist to be modified in-place regardless of whether the node type
5578  * can project --- we use this for fixing the tlist of MergeAppend itself.
5579  *
5580  * Returns the node which is to be the input to the Sort (either lefttree,
5581  * or a Result stacked atop lefttree).
5582  */
5583 static Plan *
5584 prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
5585  Relids relids,
5586  const AttrNumber *reqColIdx,
5587  bool adjust_tlist_in_place,
5588  int *p_numsortkeys,
5589  AttrNumber **p_sortColIdx,
5590  Oid **p_sortOperators,
5591  Oid **p_collations,
5592  bool **p_nullsFirst)
5593 {
5594  List *tlist = lefttree->targetlist;
5595  ListCell *i;
5596  int numsortkeys;
5597  AttrNumber *sortColIdx;
5598  Oid *sortOperators;
5599  Oid *collations;
5600  bool *nullsFirst;
5601 
5602  /*
5603  * We will need at most list_length(pathkeys) sort columns; possibly less
5604  */
5605  numsortkeys = list_length(pathkeys);
5606  sortColIdx = (AttrNumber *) palloc(numsortkeys * sizeof(AttrNumber));
5607  sortOperators = (Oid *) palloc(numsortkeys * sizeof(Oid));
5608  collations = (Oid *) palloc(numsortkeys * sizeof(Oid));
5609  nullsFirst = (bool *) palloc(numsortkeys * sizeof(bool));
5610 
5611  numsortkeys = 0;
5612 
5613  foreach(i, pathkeys)
5614  {
5615  PathKey *pathkey = (PathKey *) lfirst(i);
5616  EquivalenceClass *ec = pathkey->pk_eclass;
5617  EquivalenceMember *em;
5618  TargetEntry *tle = NULL;
5619  Oid pk_datatype = InvalidOid;
5620  Oid sortop;
5621  ListCell *j;
5622 
5623  if (ec->ec_has_volatile)
5624  {
5625  /*
5626  * If the pathkey's EquivalenceClass is volatile, then it must
5627  * have come from an ORDER BY clause, and we have to match it to
5628  * that same targetlist entry.
5629  */
5630  if (ec->ec_sortref == 0) /* can't happen */
5631  elog(ERROR, "volatile EquivalenceClass has no sortref");
5632  tle = get_sortgroupref_tle(ec->ec_sortref, tlist);
5633  Assert(tle);
5634  Assert(list_length(ec->ec_members) == 1);
5635  pk_datatype = ((EquivalenceMember *) linitial(ec->ec_members))->em_datatype;
5636  }
5637  else if (reqColIdx != NULL)
5638  {
5639  /*
5640  * If we are given a sort column number to match, only consider
5641  * the single TLE at that position. It's possible that there is
5642  * no such TLE, in which case fall through and generate a resjunk
5643  * targetentry (we assume this must have happened in the parent
5644  * plan as well). If there is a TLE but it doesn't match the
5645  * pathkey's EC, we do the same, which is probably the wrong thing
5646  * but we'll leave it to caller to complain about the mismatch.
5647  */
5648  tle = get_tle_by_resno(tlist, reqColIdx[numsortkeys]);
5649  if (tle)
5650  {
5651  em = find_ec_member_for_tle(ec, tle, relids);
5652  if (em)
5653  {
5654  /* found expr at right place in tlist */
5655  pk_datatype = em->em_datatype;
5656  }
5657  else
5658  tle = NULL;
5659  }
5660  }
5661  else
5662  {
5663  /*
5664  * Otherwise, we can sort by any non-constant expression listed in
5665  * the pathkey's EquivalenceClass. For now, we take the first
5666  * tlist item found in the EC. If there's no match, we'll generate
5667  * a resjunk entry using the first EC member that is an expression
5668  * in the input's vars. (The non-const restriction only matters
5669  * if the EC is below_outer_join; but if it isn't, it won't
5670  * contain consts anyway, else we'd have discarded the pathkey as
5671  * redundant.)
5672  *
5673  * XXX if we have a choice, is there any way of figuring out which
5674  * might be cheapest to execute? (For example, int4lt is likely