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