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