PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
tlist.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * tlist.c
4  * Target list manipulation routines
5  *
6  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
7  * Portions Copyright (c) 1994, Regents of the University of California
8  *
9  *
10  * IDENTIFICATION
11  * src/backend/optimizer/util/tlist.c
12  *
13  *-------------------------------------------------------------------------
14  */
15 #include "postgres.h"
16 
17 #include "nodes/makefuncs.h"
18 #include "nodes/nodeFuncs.h"
19 #include "optimizer/cost.h"
20 #include "optimizer/tlist.h"
21 
22 
23 /* Test if an expression node represents a SRF call. Beware multiple eval! */
24 #define IS_SRF_CALL(node) \
25  ((IsA(node, FuncExpr) && ((FuncExpr *) (node))->funcretset) || \
26  (IsA(node, OpExpr) && ((OpExpr *) (node))->opretset))
27 
28 /* Workspace for split_pathtarget_walker */
29 typedef struct
30 {
31  List *input_target_exprs; /* exprs available from input */
32  List *level_srfs; /* list of lists of SRF exprs */
33  List *level_input_vars; /* vars needed by SRFs of each level */
34  List *level_input_srfs; /* SRFs needed by SRFs of each level */
35  List *current_input_vars; /* vars needed in current subexpr */
36  List *current_input_srfs; /* SRFs needed in current subexpr */
37  int current_depth; /* max SRF depth in current subexpr */
39 
40 static bool split_pathtarget_walker(Node *node,
41  split_pathtarget_context *context);
42 
43 
44 /*****************************************************************************
45  * Target list creation and searching utilities
46  *****************************************************************************/
47 
48 /*
49  * tlist_member
50  * Finds the (first) member of the given tlist whose expression is
51  * equal() to the given expression. Result is NULL if no such member.
52  */
54 tlist_member(Expr *node, List *targetlist)
55 {
56  ListCell *temp;
57 
58  foreach(temp, targetlist)
59  {
60  TargetEntry *tlentry = (TargetEntry *) lfirst(temp);
61 
62  if (equal(node, tlentry->expr))
63  return tlentry;
64  }
65  return NULL;
66 }
67 
68 /*
69  * tlist_member_ignore_relabel
70  * Same as above, except that we ignore top-level RelabelType nodes
71  * while checking for a match. This is needed for some scenarios
72  * involving binary-compatible sort operations.
73  */
76 {
77  ListCell *temp;
78 
79  while (node && IsA(node, RelabelType))
80  node = ((RelabelType *) node)->arg;
81 
82  foreach(temp, targetlist)
83  {
84  TargetEntry *tlentry = (TargetEntry *) lfirst(temp);
85  Expr *tlexpr = tlentry->expr;
86 
87  while (tlexpr && IsA(tlexpr, RelabelType))
88  tlexpr = ((RelabelType *) tlexpr)->arg;
89 
90  if (equal(node, tlexpr))
91  return tlentry;
92  }
93  return NULL;
94 }
95 
96 /*
97  * tlist_member_match_var
98  * Same as above, except that we match the provided Var on the basis
99  * of varno/varattno/varlevelsup/vartype only, rather than full equal().
100  *
101  * This is needed in some cases where we can't be sure of an exact typmod
102  * match. For safety, though, we insist on vartype match.
103  */
104 static TargetEntry *
105 tlist_member_match_var(Var *var, List *targetlist)
106 {
107  ListCell *temp;
108 
109  foreach(temp, targetlist)
110  {
111  TargetEntry *tlentry = (TargetEntry *) lfirst(temp);
112  Var *tlvar = (Var *) tlentry->expr;
113 
114  if (!tlvar || !IsA(tlvar, Var))
115  continue;
116  if (var->varno == tlvar->varno &&
117  var->varattno == tlvar->varattno &&
118  var->varlevelsup == tlvar->varlevelsup &&
119  var->vartype == tlvar->vartype)
120  return tlentry;
121  }
122  return NULL;
123 }
124 
125 /*
126  * add_to_flat_tlist
127  * Add more items to a flattened tlist (if they're not already in it)
128  *
129  * 'tlist' is the flattened tlist
130  * 'exprs' is a list of expressions (usually, but not necessarily, Vars)
131  *
132  * Returns the extended tlist.
133  */
134 List *
135 add_to_flat_tlist(List *tlist, List *exprs)
136 {
137  int next_resno = list_length(tlist) + 1;
138  ListCell *lc;
139 
140  foreach(lc, exprs)
141  {
142  Expr *expr = (Expr *) lfirst(lc);
143 
144  if (!tlist_member(expr, tlist))
145  {
146  TargetEntry *tle;
147 
148  tle = makeTargetEntry(copyObject(expr), /* copy needed?? */
149  next_resno++,
150  NULL,
151  false);
152  tlist = lappend(tlist, tle);
153  }
154  }
155  return tlist;
156 }
157 
158 
159 /*
160  * get_tlist_exprs
161  * Get just the expression subtrees of a tlist
162  *
163  * Resjunk columns are ignored unless includeJunk is true
164  */
165 List *
166 get_tlist_exprs(List *tlist, bool includeJunk)
167 {
168  List *result = NIL;
169  ListCell *l;
170 
171  foreach(l, tlist)
172  {
173  TargetEntry *tle = (TargetEntry *) lfirst(l);
174 
175  if (tle->resjunk && !includeJunk)
176  continue;
177 
178  result = lappend(result, tle->expr);
179  }
180  return result;
181 }
182 
183 
184 /*
185  * count_nonjunk_tlist_entries
186  * What it says ...
187  */
188 int
190 {
191  int len = 0;
192  ListCell *l;
193 
194  foreach(l, tlist)
195  {
196  TargetEntry *tle = (TargetEntry *) lfirst(l);
197 
198  if (!tle->resjunk)
199  len++;
200  }
201  return len;
202 }
203 
204 
205 /*
206  * tlist_same_exprs
207  * Check whether two target lists contain the same expressions
208  *
209  * Note: this function is used to decide whether it's safe to jam a new tlist
210  * into a non-projection-capable plan node. Obviously we can't do that unless
211  * the node's tlist shows it already returns the column values we want.
212  * However, we can ignore the TargetEntry attributes resname, ressortgroupref,
213  * resorigtbl, resorigcol, and resjunk, because those are only labelings that
214  * don't affect the row values computed by the node. (Moreover, if we didn't
215  * ignore them, we'd frequently fail to make the desired optimization, since
216  * the planner tends to not bother to make resname etc. valid in intermediate
217  * plan nodes.) Note that on success, the caller must still jam the desired
218  * tlist into the plan node, else it won't have the desired labeling fields.
219  */
220 bool
221 tlist_same_exprs(List *tlist1, List *tlist2)
222 {
223  ListCell *lc1,
224  *lc2;
225 
226  if (list_length(tlist1) != list_length(tlist2))
227  return false; /* not same length, so can't match */
228 
229  forboth(lc1, tlist1, lc2, tlist2)
230  {
231  TargetEntry *tle1 = (TargetEntry *) lfirst(lc1);
232  TargetEntry *tle2 = (TargetEntry *) lfirst(lc2);
233 
234  if (!equal(tle1->expr, tle2->expr))
235  return false;
236  }
237 
238  return true;
239 }
240 
241 
242 /*
243  * Does tlist have same output datatypes as listed in colTypes?
244  *
245  * Resjunk columns are ignored if junkOK is true; otherwise presence of
246  * a resjunk column will always cause a 'false' result.
247  *
248  * Note: currently no callers care about comparing typmods.
249  */
250 bool
251 tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK)
252 {
253  ListCell *l;
254  ListCell *curColType = list_head(colTypes);
255 
256  foreach(l, tlist)
257  {
258  TargetEntry *tle = (TargetEntry *) lfirst(l);
259 
260  if (tle->resjunk)
261  {
262  if (!junkOK)
263  return false;
264  }
265  else
266  {
267  if (curColType == NULL)
268  return false; /* tlist longer than colTypes */
269  if (exprType((Node *) tle->expr) != lfirst_oid(curColType))
270  return false;
271  curColType = lnext(curColType);
272  }
273  }
274  if (curColType != NULL)
275  return false; /* tlist shorter than colTypes */
276  return true;
277 }
278 
279 /*
280  * Does tlist have same exposed collations as listed in colCollations?
281  *
282  * Identical logic to the above, but for collations.
283  */
284 bool
285 tlist_same_collations(List *tlist, List *colCollations, bool junkOK)
286 {
287  ListCell *l;
288  ListCell *curColColl = list_head(colCollations);
289 
290  foreach(l, tlist)
291  {
292  TargetEntry *tle = (TargetEntry *) lfirst(l);
293 
294  if (tle->resjunk)
295  {
296  if (!junkOK)
297  return false;
298  }
299  else
300  {
301  if (curColColl == NULL)
302  return false; /* tlist longer than colCollations */
303  if (exprCollation((Node *) tle->expr) != lfirst_oid(curColColl))
304  return false;
305  curColColl = lnext(curColColl);
306  }
307  }
308  if (curColColl != NULL)
309  return false; /* tlist shorter than colCollations */
310  return true;
311 }
312 
313 /*
314  * apply_tlist_labeling
315  * Apply the TargetEntry labeling attributes of src_tlist to dest_tlist
316  *
317  * This is useful for reattaching column names etc to a plan's final output
318  * targetlist.
319  */
320 void
321 apply_tlist_labeling(List *dest_tlist, List *src_tlist)
322 {
323  ListCell *ld,
324  *ls;
325 
326  Assert(list_length(dest_tlist) == list_length(src_tlist));
327  forboth(ld, dest_tlist, ls, src_tlist)
328  {
329  TargetEntry *dest_tle = (TargetEntry *) lfirst(ld);
330  TargetEntry *src_tle = (TargetEntry *) lfirst(ls);
331 
332  Assert(dest_tle->resno == src_tle->resno);
333  dest_tle->resname = src_tle->resname;
334  dest_tle->ressortgroupref = src_tle->ressortgroupref;
335  dest_tle->resorigtbl = src_tle->resorigtbl;
336  dest_tle->resorigcol = src_tle->resorigcol;
337  dest_tle->resjunk = src_tle->resjunk;
338  }
339 }
340 
341 
342 /*
343  * get_sortgroupref_tle
344  * Find the targetlist entry matching the given SortGroupRef index,
345  * and return it.
346  */
347 TargetEntry *
348 get_sortgroupref_tle(Index sortref, List *targetList)
349 {
350  ListCell *l;
351 
352  foreach(l, targetList)
353  {
354  TargetEntry *tle = (TargetEntry *) lfirst(l);
355 
356  if (tle->ressortgroupref == sortref)
357  return tle;
358  }
359 
360  elog(ERROR, "ORDER/GROUP BY expression not found in targetlist");
361  return NULL; /* keep compiler quiet */
362 }
363 
364 /*
365  * get_sortgroupclause_tle
366  * Find the targetlist entry matching the given SortGroupClause
367  * by ressortgroupref, and return it.
368  */
369 TargetEntry *
371  List *targetList)
372 {
373  return get_sortgroupref_tle(sgClause->tleSortGroupRef, targetList);
374 }
375 
376 /*
377  * get_sortgroupclause_expr
378  * Find the targetlist entry matching the given SortGroupClause
379  * by ressortgroupref, and return its expression.
380  */
381 Node *
383 {
384  TargetEntry *tle = get_sortgroupclause_tle(sgClause, targetList);
385 
386  return (Node *) tle->expr;
387 }
388 
389 /*
390  * get_sortgrouplist_exprs
391  * Given a list of SortGroupClauses, build a list
392  * of the referenced targetlist expressions.
393  */
394 List *
395 get_sortgrouplist_exprs(List *sgClauses, List *targetList)
396 {
397  List *result = NIL;
398  ListCell *l;
399 
400  foreach(l, sgClauses)
401  {
402  SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
403  Node *sortexpr;
404 
405  sortexpr = get_sortgroupclause_expr(sortcl, targetList);
406  result = lappend(result, sortexpr);
407  }
408  return result;
409 }
410 
411 
412 /*****************************************************************************
413  * Functions to extract data from a list of SortGroupClauses
414  *
415  * These don't really belong in tlist.c, but they are sort of related to the
416  * functions just above, and they don't seem to deserve their own file.
417  *****************************************************************************/
418 
419 /*
420  * get_sortgroupref_clause
421  * Find the SortGroupClause matching the given SortGroupRef index,
422  * and return it.
423  */
426 {
427  ListCell *l;
428 
429  foreach(l, clauses)
430  {
432 
433  if (cl->tleSortGroupRef == sortref)
434  return cl;
435  }
436 
437  elog(ERROR, "ORDER/GROUP BY expression not found in list");
438  return NULL; /* keep compiler quiet */
439 }
440 
441 /*
442  * get_sortgroupref_clause_noerr
443  * As above, but return NULL rather than throwing an error if not found.
444  */
447 {
448  ListCell *l;
449 
450  foreach(l, clauses)
451  {
453 
454  if (cl->tleSortGroupRef == sortref)
455  return cl;
456  }
457 
458  return NULL;
459 }
460 
461 /*
462  * extract_grouping_ops - make an array of the equality operator OIDs
463  * for a SortGroupClause list
464  */
465 Oid *
467 {
468  int numCols = list_length(groupClause);
469  int colno = 0;
470  Oid *groupOperators;
471  ListCell *glitem;
472 
473  groupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
474 
475  foreach(glitem, groupClause)
476  {
477  SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
478 
479  groupOperators[colno] = groupcl->eqop;
480  Assert(OidIsValid(groupOperators[colno]));
481  colno++;
482  }
483 
484  return groupOperators;
485 }
486 
487 /*
488  * extract_grouping_cols - make an array of the grouping column resnos
489  * for a SortGroupClause list
490  */
491 AttrNumber *
492 extract_grouping_cols(List *groupClause, List *tlist)
493 {
494  AttrNumber *grpColIdx;
495  int numCols = list_length(groupClause);
496  int colno = 0;
497  ListCell *glitem;
498 
499  grpColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
500 
501  foreach(glitem, groupClause)
502  {
503  SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
504  TargetEntry *tle = get_sortgroupclause_tle(groupcl, tlist);
505 
506  grpColIdx[colno++] = tle->resno;
507  }
508 
509  return grpColIdx;
510 }
511 
512 /*
513  * grouping_is_sortable - is it possible to implement grouping list by sorting?
514  *
515  * This is easy since the parser will have included a sortop if one exists.
516  */
517 bool
519 {
520  ListCell *glitem;
521 
522  foreach(glitem, groupClause)
523  {
524  SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
525 
526  if (!OidIsValid(groupcl->sortop))
527  return false;
528  }
529  return true;
530 }
531 
532 /*
533  * grouping_is_hashable - is it possible to implement grouping list by hashing?
534  *
535  * We rely on the parser to have set the hashable flag correctly.
536  */
537 bool
539 {
540  ListCell *glitem;
541 
542  foreach(glitem, groupClause)
543  {
544  SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
545 
546  if (!groupcl->hashable)
547  return false;
548  }
549  return true;
550 }
551 
552 
553 /*****************************************************************************
554  * PathTarget manipulation functions
555  *
556  * PathTarget is a somewhat stripped-down version of a full targetlist; it
557  * omits all the TargetEntry decoration except (optionally) sortgroupref data,
558  * and it adds evaluation cost and output data width info.
559  *****************************************************************************/
560 
561 /*
562  * make_pathtarget_from_tlist
563  * Construct a PathTarget equivalent to the given targetlist.
564  *
565  * This leaves the cost and width fields as zeroes. Most callers will want
566  * to use create_pathtarget(), so as to get those set.
567  */
568 PathTarget *
570 {
571  PathTarget *target = makeNode(PathTarget);
572  int i;
573  ListCell *lc;
574 
575  target->sortgrouprefs = (Index *) palloc(list_length(tlist) * sizeof(Index));
576 
577  i = 0;
578  foreach(lc, tlist)
579  {
580  TargetEntry *tle = (TargetEntry *) lfirst(lc);
581 
582  target->exprs = lappend(target->exprs, tle->expr);
583  target->sortgrouprefs[i] = tle->ressortgroupref;
584  i++;
585  }
586 
587  return target;
588 }
589 
590 /*
591  * make_tlist_from_pathtarget
592  * Construct a targetlist from a PathTarget.
593  */
594 List *
596 {
597  List *tlist = NIL;
598  int i;
599  ListCell *lc;
600 
601  i = 0;
602  foreach(lc, target->exprs)
603  {
604  Expr *expr = (Expr *) lfirst(lc);
605  TargetEntry *tle;
606 
607  tle = makeTargetEntry(expr,
608  i + 1,
609  NULL,
610  false);
611  if (target->sortgrouprefs)
612  tle->ressortgroupref = target->sortgrouprefs[i];
613  tlist = lappend(tlist, tle);
614  i++;
615  }
616 
617  return tlist;
618 }
619 
620 /*
621  * copy_pathtarget
622  * Copy a PathTarget.
623  *
624  * The new PathTarget has its own List cells, but shares the underlying
625  * target expression trees with the old one. We duplicate the List cells
626  * so that items can be added to one target without damaging the other.
627  */
628 PathTarget *
630 {
632 
633  /* Copy scalar fields */
634  memcpy(dst, src, sizeof(PathTarget));
635  /* Shallow-copy the expression list */
636  dst->exprs = list_copy(src->exprs);
637  /* Duplicate sortgrouprefs if any (if not, the memcpy handled this) */
638  if (src->sortgrouprefs)
639  {
640  Size nbytes = list_length(src->exprs) * sizeof(Index);
641 
642  dst->sortgrouprefs = (Index *) palloc(nbytes);
643  memcpy(dst->sortgrouprefs, src->sortgrouprefs, nbytes);
644  }
645  return dst;
646 }
647 
648 /*
649  * create_empty_pathtarget
650  * Create an empty (zero columns, zero cost) PathTarget.
651  */
652 PathTarget *
654 {
655  /* This is easy, but we don't want callers to hard-wire this ... */
656  return makeNode(PathTarget);
657 }
658 
659 /*
660  * add_column_to_pathtarget
661  * Append a target column to the PathTarget.
662  *
663  * As with make_pathtarget_from_tlist, we leave it to the caller to update
664  * the cost and width fields.
665  */
666 void
667 add_column_to_pathtarget(PathTarget *target, Expr *expr, Index sortgroupref)
668 {
669  /* Updating the exprs list is easy ... */
670  target->exprs = lappend(target->exprs, expr);
671  /* ... the sortgroupref data, a bit less so */
672  if (target->sortgrouprefs)
673  {
674  int nexprs = list_length(target->exprs);
675 
676  /* This might look inefficient, but actually it's usually cheap */
677  target->sortgrouprefs = (Index *)
678  repalloc(target->sortgrouprefs, nexprs * sizeof(Index));
679  target->sortgrouprefs[nexprs - 1] = sortgroupref;
680  }
681  else if (sortgroupref)
682  {
683  /* Adding sortgroupref labeling to a previously unlabeled target */
684  int nexprs = list_length(target->exprs);
685 
686  target->sortgrouprefs = (Index *) palloc0(nexprs * sizeof(Index));
687  target->sortgrouprefs[nexprs - 1] = sortgroupref;
688  }
689 }
690 
691 /*
692  * add_new_column_to_pathtarget
693  * Append a target column to the PathTarget, but only if it's not
694  * equal() to any pre-existing target expression.
695  *
696  * The caller cannot specify a sortgroupref, since it would be unclear how
697  * to merge that with a pre-existing column.
698  *
699  * As with make_pathtarget_from_tlist, we leave it to the caller to update
700  * the cost and width fields.
701  */
702 void
704 {
705  if (!list_member(target->exprs, expr))
706  add_column_to_pathtarget(target, expr, 0);
707 }
708 
709 /*
710  * add_new_columns_to_pathtarget
711  * Apply add_new_column_to_pathtarget() for each element of the list.
712  */
713 void
715 {
716  ListCell *lc;
717 
718  foreach(lc, exprs)
719  {
720  Expr *expr = (Expr *) lfirst(lc);
721 
722  add_new_column_to_pathtarget(target, expr);
723  }
724 }
725 
726 /*
727  * apply_pathtarget_labeling_to_tlist
728  * Apply any sortgrouprefs in the PathTarget to matching tlist entries
729  *
730  * Here, we do not assume that the tlist entries are one-for-one with the
731  * PathTarget. The intended use of this function is to deal with cases
732  * where createplan.c has decided to use some other tlist and we have
733  * to identify what matches exist.
734  */
735 void
737 {
738  int i;
739  ListCell *lc;
740 
741  /* Nothing to do if PathTarget has no sortgrouprefs data */
742  if (target->sortgrouprefs == NULL)
743  return;
744 
745  i = 0;
746  foreach(lc, target->exprs)
747  {
748  Expr *expr = (Expr *) lfirst(lc);
749  TargetEntry *tle;
750 
751  if (target->sortgrouprefs[i])
752  {
753  /*
754  * For Vars, use tlist_member_match_var's weakened matching rule;
755  * this allows us to deal with some cases where a set-returning
756  * function has been inlined, so that we now have more knowledge
757  * about what it returns than we did when the original Var was
758  * created. Otherwise, use regular equal() to find the matching
759  * TLE. (In current usage, only the Var case is actually needed;
760  * but it seems best to have sane behavior here for non-Vars too.)
761  */
762  if (expr && IsA(expr, Var))
763  tle = tlist_member_match_var((Var *) expr, tlist);
764  else
765  tle = tlist_member(expr, tlist);
766 
767  /*
768  * Complain if noplace for the sortgrouprefs label, or if we'd
769  * have to label a column twice. (The case where it already has
770  * the desired label probably can't happen, but we may as well
771  * allow for it.)
772  */
773  if (!tle)
774  elog(ERROR, "ORDER/GROUP BY expression not found in targetlist");
775  if (tle->ressortgroupref != 0 &&
776  tle->ressortgroupref != target->sortgrouprefs[i])
777  elog(ERROR, "targetlist item has multiple sortgroupref labels");
778 
779  tle->ressortgroupref = target->sortgrouprefs[i];
780  }
781  i++;
782  }
783 }
784 
785 /*
786  * split_pathtarget_at_srfs
787  * Split given PathTarget into multiple levels to position SRFs safely
788  *
789  * The executor can only handle set-returning functions that appear at the
790  * top level of the targetlist of a ProjectSet plan node. If we have any SRFs
791  * that are not at top level, we need to split up the evaluation into multiple
792  * plan levels in which each level satisfies this constraint. This function
793  * creates appropriate PathTarget(s) for each level.
794  *
795  * As an example, consider the tlist expression
796  * x + srf1(srf2(y + z))
797  * This expression should appear as-is in the top PathTarget, but below that
798  * we must have a PathTarget containing
799  * x, srf1(srf2(y + z))
800  * and below that, another PathTarget containing
801  * x, srf2(y + z)
802  * and below that, another PathTarget containing
803  * x, y, z
804  * When these tlists are processed by setrefs.c, subexpressions that match
805  * output expressions of the next lower tlist will be replaced by Vars,
806  * so that what the executor gets are tlists looking like
807  * Var1 + Var2
808  * Var1, srf1(Var2)
809  * Var1, srf2(Var2 + Var3)
810  * x, y, z
811  * which satisfy the desired property.
812  *
813  * Another example is
814  * srf1(x), srf2(srf3(y))
815  * That must appear as-is in the top PathTarget, but below that we need
816  * srf1(x), srf3(y)
817  * That is, each SRF must be computed at a level corresponding to the nesting
818  * depth of SRFs within its arguments.
819  *
820  * In some cases, a SRF has already been evaluated in some previous plan level
821  * and we shouldn't expand it again (that is, what we see in the target is
822  * already meant as a reference to a lower subexpression). So, don't expand
823  * any tlist expressions that appear in input_target, if that's not NULL.
824  *
825  * The outputs of this function are two parallel lists, one a list of
826  * PathTargets and the other an integer list of bool flags indicating
827  * whether the corresponding PathTarget contains any evaluatable SRFs.
828  * The lists are given in the order they'd need to be evaluated in, with
829  * the "lowest" PathTarget first. So the last list entry is always the
830  * originally given PathTarget, and any entries before it indicate evaluation
831  * levels that must be inserted below it. The first list entry must not
832  * contain any SRFs (other than ones duplicating input_target entries), since
833  * it will typically be attached to a plan node that cannot evaluate SRFs.
834  *
835  * Note: using a list for the flags may seem like overkill, since there
836  * are only a few possible patterns for which levels contain SRFs.
837  * But this representation decouples callers from that knowledge.
838  */
839 void
841  PathTarget *target, PathTarget *input_target,
842  List **targets, List **targets_contain_srfs)
843 {
844  split_pathtarget_context context;
845  int max_depth;
846  bool need_extra_projection;
847  List *prev_level_tlist;
848  ListCell *lc,
849  *lc1,
850  *lc2,
851  *lc3;
852 
853  /*
854  * It's not unusual for planner.c to pass us two physically identical
855  * targets, in which case we can conclude without further ado that all
856  * expressions are available from the input. (The logic below would
857  * arrive at the same conclusion, but much more tediously.)
858  */
859  if (target == input_target)
860  {
861  *targets = list_make1(target);
862  *targets_contain_srfs = list_make1_int(false);
863  return;
864  }
865 
866  /* Pass any input_target exprs down to split_pathtarget_walker() */
867  context.input_target_exprs = input_target ? input_target->exprs : NIL;
868 
869  /*
870  * Initialize with empty level-zero lists, and no levels after that.
871  * (Note: we could dispense with representing level zero explicitly, since
872  * it will never receive any SRFs, but then we'd have to special-case that
873  * level when we get to building result PathTargets. Level zero describes
874  * the SRF-free PathTarget that will be given to the input plan node.)
875  */
876  context.level_srfs = list_make1(NIL);
877  context.level_input_vars = list_make1(NIL);
878  context.level_input_srfs = list_make1(NIL);
879 
880  /* Initialize data we'll accumulate across all the target expressions */
881  context.current_input_vars = NIL;
882  context.current_input_srfs = NIL;
883  max_depth = 0;
884  need_extra_projection = false;
885 
886  /* Scan each expression in the PathTarget looking for SRFs */
887  foreach(lc, target->exprs)
888  {
889  Node *node = (Node *) lfirst(lc);
890 
891  /*
892  * Find all SRFs and Vars (and Var-like nodes) in this expression, and
893  * enter them into appropriate lists within the context struct.
894  */
895  context.current_depth = 0;
896  split_pathtarget_walker(node, &context);
897 
898  /* An expression containing no SRFs is of no further interest */
899  if (context.current_depth == 0)
900  continue;
901 
902  /*
903  * Track max SRF nesting depth over the whole PathTarget. Also, if
904  * this expression establishes a new max depth, we no longer care
905  * whether previous expressions contained nested SRFs; we can handle
906  * any required projection for them in the final ProjectSet node.
907  */
908  if (max_depth < context.current_depth)
909  {
910  max_depth = context.current_depth;
911  need_extra_projection = false;
912  }
913 
914  /*
915  * If any maximum-depth SRF is not at the top level of its expression,
916  * we'll need an extra Result node to compute the top-level scalar
917  * expression.
918  */
919  if (max_depth == context.current_depth && !IS_SRF_CALL(node))
920  need_extra_projection = true;
921  }
922 
923  /*
924  * If we found no SRFs needing evaluation (maybe they were all present in
925  * input_target, or maybe they were all removed by const-simplification),
926  * then no ProjectSet is needed; fall out.
927  */
928  if (max_depth == 0)
929  {
930  *targets = list_make1(target);
931  *targets_contain_srfs = list_make1_int(false);
932  return;
933  }
934 
935  /*
936  * The Vars and SRF outputs needed at top level can be added to the last
937  * level_input lists if we don't need an extra projection step. If we do
938  * need one, add a SRF-free level to the lists.
939  */
940  if (need_extra_projection)
941  {
942  context.level_srfs = lappend(context.level_srfs, NIL);
943  context.level_input_vars = lappend(context.level_input_vars,
944  context.current_input_vars);
945  context.level_input_srfs = lappend(context.level_input_srfs,
946  context.current_input_srfs);
947  }
948  else
949  {
950  lc = list_nth_cell(context.level_input_vars, max_depth);
951  lfirst(lc) = list_concat(lfirst(lc), context.current_input_vars);
952  lc = list_nth_cell(context.level_input_srfs, max_depth);
953  lfirst(lc) = list_concat(lfirst(lc), context.current_input_srfs);
954  }
955 
956  /*
957  * Now construct the output PathTargets. The original target can be used
958  * as-is for the last one, but we need to construct a new SRF-free target
959  * representing what the preceding plan node has to emit, as well as a
960  * target for each intermediate ProjectSet node.
961  */
962  *targets = *targets_contain_srfs = NIL;
963  prev_level_tlist = NIL;
964 
965  forthree(lc1, context.level_srfs,
966  lc2, context.level_input_vars,
967  lc3, context.level_input_srfs)
968  {
969  List *level_srfs = (List *) lfirst(lc1);
970  PathTarget *ntarget;
971 
972  if (lnext(lc1) == NULL)
973  {
974  ntarget = target;
975  }
976  else
977  {
978  ntarget = create_empty_pathtarget();
979 
980  /*
981  * This target should actually evaluate any SRFs of the current
982  * level, and it needs to propagate forward any Vars needed by
983  * later levels, as well as SRFs computed earlier and needed by
984  * later levels. We rely on add_new_columns_to_pathtarget() to
985  * remove duplicate items. Also, for safety, make a separate copy
986  * of each item for each PathTarget.
987  */
988  add_new_columns_to_pathtarget(ntarget, copyObject(level_srfs));
989  for_each_cell(lc, lnext(lc2))
990  {
991  List *input_vars = (List *) lfirst(lc);
992 
993  add_new_columns_to_pathtarget(ntarget, copyObject(input_vars));
994  }
995  for_each_cell(lc, lnext(lc3))
996  {
997  List *input_srfs = (List *) lfirst(lc);
998  ListCell *lcx;
999 
1000  foreach(lcx, input_srfs)
1001  {
1002  Expr *srf = (Expr *) lfirst(lcx);
1003 
1004  if (list_member(prev_level_tlist, srf))
1006  }
1007  }
1008  set_pathtarget_cost_width(root, ntarget);
1009  }
1010 
1011  /*
1012  * Add current target and does-it-compute-SRFs flag to output lists.
1013  */
1014  *targets = lappend(*targets, ntarget);
1015  *targets_contain_srfs = lappend_int(*targets_contain_srfs,
1016  (level_srfs != NIL));
1017 
1018  /* Remember this level's output for next pass */
1019  prev_level_tlist = ntarget->exprs;
1020  }
1021 }
1022 
1023 /*
1024  * Recursively examine expressions for split_pathtarget_at_srfs.
1025  *
1026  * Note we make no effort here to prevent duplicate entries in the output
1027  * lists. Duplicates will be gotten rid of later.
1028  */
1029 static bool
1031 {
1032  if (node == NULL)
1033  return false;
1034 
1035  /*
1036  * A subexpression that matches an expression already computed in
1037  * input_target can be treated like a Var (which indeed it will be after
1038  * setrefs.c gets done with it), even if it's actually a SRF. Record it
1039  * as being needed for the current expression, and ignore any
1040  * substructure.
1041  */
1042  if (list_member(context->input_target_exprs, node))
1043  {
1044  context->current_input_vars = lappend(context->current_input_vars,
1045  node);
1046  return false;
1047  }
1048 
1049  /*
1050  * Vars and Var-like constructs are expected to be gotten from the input,
1051  * too. We assume that these constructs cannot contain any SRFs (if one
1052  * does, there will be an executor failure from a misplaced SRF).
1053  */
1054  if (IsA(node, Var) ||
1055  IsA(node, PlaceHolderVar) ||
1056  IsA(node, Aggref) ||
1057  IsA(node, GroupingFunc) ||
1058  IsA(node, WindowFunc))
1059  {
1060  context->current_input_vars = lappend(context->current_input_vars,
1061  node);
1062  return false;
1063  }
1064 
1065  /*
1066  * If it's a SRF, recursively examine its inputs, determine its level, and
1067  * make appropriate entries in the output lists.
1068  */
1069  if (IS_SRF_CALL(node))
1070  {
1071  List *save_input_vars = context->current_input_vars;
1072  List *save_input_srfs = context->current_input_srfs;
1073  int save_current_depth = context->current_depth;
1074  int srf_depth;
1075  ListCell *lc;
1076 
1077  context->current_input_vars = NIL;
1078  context->current_input_srfs = NIL;
1079  context->current_depth = 0;
1080 
1082  (void *) context);
1083 
1084  /* Depth is one more than any SRF below it */
1085  srf_depth = context->current_depth + 1;
1086 
1087  /* If new record depth, initialize another level of output lists */
1088  if (srf_depth >= list_length(context->level_srfs))
1089  {
1090  context->level_srfs = lappend(context->level_srfs, NIL);
1091  context->level_input_vars = lappend(context->level_input_vars, NIL);
1092  context->level_input_srfs = lappend(context->level_input_srfs, NIL);
1093  }
1094 
1095  /* Record this SRF as needing to be evaluated at appropriate level */
1096  lc = list_nth_cell(context->level_srfs, srf_depth);
1097  lfirst(lc) = lappend(lfirst(lc), node);
1098 
1099  /* Record its inputs as being needed at the same level */
1100  lc = list_nth_cell(context->level_input_vars, srf_depth);
1101  lfirst(lc) = list_concat(lfirst(lc), context->current_input_vars);
1102  lc = list_nth_cell(context->level_input_srfs, srf_depth);
1103  lfirst(lc) = list_concat(lfirst(lc), context->current_input_srfs);
1104 
1105  /*
1106  * Restore caller-level state and update it for presence of this SRF.
1107  * Notice we report the SRF itself as being needed for evaluation of
1108  * surrounding expression.
1109  */
1110  context->current_input_vars = save_input_vars;
1111  context->current_input_srfs = lappend(save_input_srfs, node);
1112  context->current_depth = Max(save_current_depth, srf_depth);
1113 
1114  /* We're done here */
1115  return false;
1116  }
1117 
1118  /*
1119  * Otherwise, the node is a scalar (non-set) expression, so recurse to
1120  * examine its inputs.
1121  */
1123  (void *) context);
1124 }
PathTarget * create_empty_pathtarget(void)
Definition: tlist.c:653
#define NIL
Definition: pg_list.h:69
PathTarget * copy_pathtarget(PathTarget *src)
Definition: tlist.c:629
void apply_tlist_labeling(List *dest_tlist, List *src_tlist)
Definition: tlist.c:321
List * level_input_vars
Definition: tlist.c:33
#define IsA(nodeptr, _type_)
Definition: nodes.h:560
Index varlevelsup
Definition: primnodes.h:173
TargetEntry * get_sortgroupclause_tle(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:370
bool tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK)
Definition: tlist.c:251
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:180
PathTarget * set_pathtarget_cost_width(PlannerInfo *root, PathTarget *target)
Definition: costsize.c:4990
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:2964
#define forthree(cell1, list1, cell2, list2, cell3, list3)
Definition: pg_list.h:203
void add_column_to_pathtarget(PathTarget *target, Expr *expr, Index sortgroupref)
Definition: tlist.c:667
void split_pathtarget_at_srfs(PlannerInfo *root, PathTarget *target, PathTarget *input_target, List **targets, List **targets_contain_srfs)
Definition: tlist.c:840
Index tleSortGroupRef
Definition: parsenodes.h:1190
Node * get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:382
List * list_copy(const List *oldlist)
Definition: list.c:1160
Definition: nodes.h:509
Oid resorigtbl
Definition: primnodes.h:1373
List * make_tlist_from_pathtarget(PathTarget *target)
Definition: tlist.c:595
AttrNumber varattno
Definition: primnodes.h:168
List * list_concat(List *list1, List *list2)
Definition: list.c:321
bool grouping_is_hashable(List *groupClause)
Definition: tlist.c:538
ListCell * list_nth_cell(const List *list, int n)
Definition: list.c:386
unsigned int Oid
Definition: postgres_ext.h:31
Oid * extract_grouping_ops(List *groupClause)
Definition: tlist.c:466
char * resname
Definition: primnodes.h:1370
Definition: primnodes.h:163
#define OidIsValid(objectId)
Definition: c.h:532
List * current_input_srfs
Definition: tlist.c:36
AttrNumber * extract_grouping_cols(List *groupClause, List *tlist)
Definition: tlist.c:492
TargetEntry * tlist_member_ignore_relabel(Expr *node, List *targetlist)
Definition: tlist.c:75
#define list_make1(x1)
Definition: pg_list.h:139
bool resjunk
Definition: primnodes.h:1375
#define ERROR
Definition: elog.h:43
bool list_member(const List *list, const void *datum)
Definition: list.c:444
Oid vartype
Definition: primnodes.h:170
List * level_input_srfs
Definition: tlist.c:34
AttrNumber resno
Definition: primnodes.h:1369
static ListCell * list_head(const List *l)
Definition: pg_list.h:77
Index * sortgrouprefs
Definition: relation.h:939
#define list_make1_int(x1)
Definition: pg_list.h:145
#define lnext(lc)
Definition: pg_list.h:105
TargetEntry * makeTargetEntry(Expr *expr, AttrNumber resno, char *resname, bool resjunk)
Definition: makefuncs.c:235
TargetEntry * get_sortgroupref_tle(Index sortref, List *targetList)
Definition: tlist.c:348
List * lappend_int(List *list, int datum)
Definition: list.c:146
#define IS_SRF_CALL(node)
Definition: tlist.c:24
List * lappend(List *list, void *datum)
Definition: list.c:128
Index varno
Definition: primnodes.h:166
List * exprs
Definition: relation.h:938
void apply_pathtarget_labeling_to_tlist(List *tlist, PathTarget *target)
Definition: tlist.c:736
void * palloc0(Size size)
Definition: mcxt.c:877
SortGroupClause * get_sortgroupref_clause_noerr(Index sortref, List *clauses)
Definition: tlist.c:446
List * get_tlist_exprs(List *tlist, bool includeJunk)
Definition: tlist.c:166
unsigned int Index
Definition: c.h:359
TargetEntry * tlist_member(Expr *node, List *targetlist)
Definition: tlist.c:54
List * input_target_exprs
Definition: tlist.c:31
#define Max(x, y)
Definition: c.h:789
#define makeNode(_type_)
Definition: nodes.h:557
static TargetEntry * tlist_member_match_var(Var *var, List *targetlist)
Definition: tlist.c:105
#define Assert(condition)
Definition: c.h:664
List * add_to_flat_tlist(List *tlist, List *exprs)
Definition: tlist.c:135
#define lfirst(lc)
Definition: pg_list.h:106
PathTarget * make_pathtarget_from_tlist(List *tlist)
Definition: tlist.c:569
Expr * expr
Definition: primnodes.h:1368
size_t Size
Definition: c.h:350
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:42
bool expression_tree_walker(Node *node, bool(*walker)(), void *context)
Definition: nodeFuncs.c:1843
static int list_length(const List *l)
Definition: pg_list.h:89
List * get_sortgrouplist_exprs(List *sgClauses, List *targetList)
Definition: tlist.c:395
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:720
#define for_each_cell(cell, initcell)
Definition: pg_list.h:169
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:962
bool tlist_same_exprs(List *tlist1, List *tlist2)
Definition: tlist.c:221
SortGroupClause * get_sortgroupref_clause(Index sortref, List *clauses)
Definition: tlist.c:425
AttrNumber resorigcol
Definition: primnodes.h:1374
void * palloc(Size size)
Definition: mcxt.c:848
int i
int count_nonjunk_tlist_entries(List *tlist)
Definition: tlist.c:189
Index ressortgroupref
Definition: primnodes.h:1371
bool grouping_is_sortable(List *groupClause)
Definition: tlist.c:518
void * arg
bool tlist_same_collations(List *tlist, List *colCollations, bool junkOK)
Definition: tlist.c:285
#define elog
Definition: elog.h:219
void add_new_column_to_pathtarget(PathTarget *target, Expr *expr)
Definition: tlist.c:703
#define copyObject(obj)
Definition: nodes.h:622
static bool split_pathtarget_walker(Node *node, split_pathtarget_context *context)
Definition: tlist.c:1030
Definition: pg_list.h:45
int16 AttrNumber
Definition: attnum.h:21
#define lfirst_oid(lc)
Definition: pg_list.h:108
List * current_input_vars
Definition: tlist.c:35
void add_new_columns_to_pathtarget(PathTarget *target, List *exprs)
Definition: tlist.c:714