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 */
34typedef struct
35{
36 Node *expr; /* some subexpression of a PathTarget */
37 Index sortgroupref; /* its sortgroupref, or 0 if none */
38} split_pathtarget_item;
39
40typedef 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 */
54} split_pathtarget_context;
55
56static bool split_pathtarget_walker(Node *node,
57 split_pathtarget_context *context);
58static void add_sp_item_to_pathtarget(PathTarget *target,
59 split_pathtarget_item *item);
60static 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 */
72TargetEntry *
73tlist_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 */
93TargetEntry *
94tlist_member_ignore_relabel(Expr *node, List *targetlist)
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 */
123static TargetEntry *
124tlist_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 */
153List *
154add_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 */
184List *
185get_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 */
207int
208count_nonjunk_tlist_entries(List *tlist)
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 */
239bool
240tlist_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 */
269bool
270tlist_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(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 */
303bool
304tlist_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(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 */
339void
340apply_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 */
366TargetEntry *
367get_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 */
388TargetEntry *
389get_sortgroupclause_tle(SortGroupClause *sgClause,
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 */
400Node *
401get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
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 */
413List *
414get_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 */
443SortGroupClause *
444get_sortgroupref_clause(Index sortref, List *clauses)
445{
446 ListCell *l;
447
448 foreach(l, clauses)
449 {
450 SortGroupClause *cl = (SortGroupClause *) lfirst(l);
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 */
464SortGroupClause *
465get_sortgroupref_clause_noerr(Index sortref, List *clauses)
466{
467 ListCell *l;
468
469 foreach(l, clauses)
470 {
471 SortGroupClause *cl = (SortGroupClause *) lfirst(l);
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 */
484Oid *
485extract_grouping_ops(List *groupClause)
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 */
510Oid *
511extract_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 */
535AttrNumber *
536extract_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 */
561bool
562grouping_is_sortable(List *groupClause)
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 */
581bool
582grouping_is_hashable(List *groupClause)
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 */
612PathTarget *
613make_pathtarget_from_tlist(List *tlist)
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 */
638List *
639make_tlist_from_pathtarget(PathTarget *target)
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 List cells, but shares the underlying
669 * target expression trees with the old one. We duplicate the List cells
670 * so that items can be added to one target without damaging the other.
671 */
672PathTarget *
673copy_pathtarget(PathTarget *src)
674{
675 PathTarget *dst = makeNode(PathTarget);
676
677 /* Copy scalar fields */
678 memcpy(dst, src, sizeof(PathTarget));
679 /* Shallow-copy the expression list */
680 dst->exprs = list_copy(src->exprs);
681 /* Duplicate sortgrouprefs if any (if not, the memcpy handled this) */
682 if (src->sortgrouprefs)
683 {
684 Size nbytes = list_length(src->exprs) * sizeof(Index);
685
686 dst->sortgrouprefs = (Index *) palloc(nbytes);
687 memcpy(dst->sortgrouprefs, src->sortgrouprefs, nbytes);
688 }
689 return dst;
690}
691
692/*
693 * create_empty_pathtarget
694 * Create an empty (zero columns, zero cost) PathTarget.
695 */
696PathTarget *
697create_empty_pathtarget(void)
698{
699 /* This is easy, but we don't want callers to hard-wire this ... */
700 return makeNode(PathTarget);
701}
702
703/*
704 * add_column_to_pathtarget
705 * Append a target column to the PathTarget.
706 *
707 * As with make_pathtarget_from_tlist, we leave it to the caller to update
708 * the cost and width fields.
709 */
710void
711add_column_to_pathtarget(PathTarget *target, Expr *expr, Index sortgroupref)
712{
713 /* Updating the exprs list is easy ... */
714 target->exprs = lappend(target->exprs, expr);
715 /* ... the sortgroupref data, a bit less so */
716 if (target->sortgrouprefs)
717 {
718 int nexprs = list_length(target->exprs);
719
720 /* This might look inefficient, but actually it's usually cheap */
721 target->sortgrouprefs = (Index *)
722 repalloc(target->sortgrouprefs, nexprs * sizeof(Index));
723 target->sortgrouprefs[nexprs - 1] = sortgroupref;
724 }
725 else if (sortgroupref)
726 {
727 /* Adding sortgroupref labeling to a previously unlabeled target */
728 int nexprs = list_length(target->exprs);
729
730 target->sortgrouprefs = (Index *) palloc0(nexprs * sizeof(Index));
731 target->sortgrouprefs[nexprs - 1] = sortgroupref;
732 }
733}
734
735/*
736 * add_new_column_to_pathtarget
737 * Append a target column to the PathTarget, but only if it's not
738 * equal() to any pre-existing target expression.
739 *
740 * The caller cannot specify a sortgroupref, since it would be unclear how
741 * to merge that with a pre-existing column.
742 *
743 * As with make_pathtarget_from_tlist, we leave it to the caller to update
744 * the cost and width fields.
745 */
746void
747add_new_column_to_pathtarget(PathTarget *target, Expr *expr)
748{
749 if (!list_member(target->exprs, expr))
750 add_column_to_pathtarget(target, expr, 0);
751}
752
753/*
754 * add_new_columns_to_pathtarget
755 * Apply add_new_column_to_pathtarget() for each element of the list.
756 */
757void
758add_new_columns_to_pathtarget(PathTarget *target, List *exprs)
759{
760 ListCell *lc;
761
762 foreach(lc, exprs)
763 {
764 Expr *expr = (Expr *) lfirst(lc);
765
766 add_new_column_to_pathtarget(target, expr);
767 }
768}
769
770/*
771 * apply_pathtarget_labeling_to_tlist
772 * Apply any sortgrouprefs in the PathTarget to matching tlist entries
773 *
774 * Here, we do not assume that the tlist entries are one-for-one with the
775 * PathTarget. The intended use of this function is to deal with cases
776 * where createplan.c has decided to use some other tlist and we have
777 * to identify what matches exist.
778 */
779void
780apply_pathtarget_labeling_to_tlist(List *tlist, PathTarget *target)
781{
782 int i;
783 ListCell *lc;
784
785 /* Nothing to do if PathTarget has no sortgrouprefs data */
786 if (target->sortgrouprefs == NULL)
787 return;
788
789 i = 0;
790 foreach(lc, target->exprs)
791 {
792 Expr *expr = (Expr *) lfirst(lc);
793 TargetEntry *tle;
794
795 if (target->sortgrouprefs[i])
796 {
797 /*
798 * For Vars, use tlist_member_match_var's weakened matching rule;
799 * this allows us to deal with some cases where a set-returning
800 * function has been inlined, so that we now have more knowledge
801 * about what it returns than we did when the original Var was
802 * created. Otherwise, use regular equal() to find the matching
803 * TLE. (In current usage, only the Var case is actually needed;
804 * but it seems best to have sane behavior here for non-Vars too.)
805 */
806 if (expr && IsA(expr, Var))
807 tle = tlist_member_match_var((Var *) expr, tlist);
808 else
809 tle = tlist_member(expr, tlist);
810
811 /*
812 * Complain if noplace for the sortgrouprefs label, or if we'd
813 * have to label a column twice. (The case where it already has
814 * the desired label probably can't happen, but we may as well
815 * allow for it.)
816 */
817 if (!tle)
818 elog(ERROR, "ORDER/GROUP BY expression not found in targetlist");
819 if (tle->ressortgroupref != 0 &&
820 tle->ressortgroupref != target->sortgrouprefs[i])
821 elog(ERROR, "targetlist item has multiple sortgroupref labels");
822
823 tle->ressortgroupref = target->sortgrouprefs[i];
824 }
825 i++;
826 }
827}
828
829/*
830 * split_pathtarget_at_srfs
831 * Split given PathTarget into multiple levels to position SRFs safely
832 *
833 * The executor can only handle set-returning functions that appear at the
834 * top level of the targetlist of a ProjectSet plan node. If we have any SRFs
835 * that are not at top level, we need to split up the evaluation into multiple
836 * plan levels in which each level satisfies this constraint. This function
837 * creates appropriate PathTarget(s) for each level.
838 *
839 * As an example, consider the tlist expression
840 * x + srf1(srf2(y + z))
841 * This expression should appear as-is in the top PathTarget, but below that
842 * we must have a PathTarget containing
843 * x, srf1(srf2(y + z))
844 * and below that, another PathTarget containing
845 * x, srf2(y + z)
846 * and below that, another PathTarget containing
847 * x, y, z
848 * When these tlists are processed by setrefs.c, subexpressions that match
849 * output expressions of the next lower tlist will be replaced by Vars,
850 * so that what the executor gets are tlists looking like
851 * Var1 + Var2
852 * Var1, srf1(Var2)
853 * Var1, srf2(Var2 + Var3)
854 * x, y, z
855 * which satisfy the desired property.
856 *
857 * Another example is
858 * srf1(x), srf2(srf3(y))
859 * That must appear as-is in the top PathTarget, but below that we need
860 * srf1(x), srf3(y)
861 * That is, each SRF must be computed at a level corresponding to the nesting
862 * depth of SRFs within its arguments.
863 *
864 * In some cases, a SRF has already been evaluated in some previous plan level
865 * and we shouldn't expand it again (that is, what we see in the target is
866 * already meant as a reference to a lower subexpression). So, don't expand
867 * any tlist expressions that appear in input_target, if that's not NULL.
868 *
869 * It's also important that we preserve any sortgroupref annotation appearing
870 * in the given target, especially on expressions matching input_target items.
871 *
872 * The outputs of this function are two parallel lists, one a list of
873 * PathTargets and the other an integer list of bool flags indicating
874 * whether the corresponding PathTarget contains any evaluatable SRFs.
875 * The lists are given in the order they'd need to be evaluated in, with
876 * the "lowest" PathTarget first. So the last list entry is always the
877 * originally given PathTarget, and any entries before it indicate evaluation
878 * levels that must be inserted below it. The first list entry must not
879 * contain any SRFs (other than ones duplicating input_target entries), since
880 * it will typically be attached to a plan node that cannot evaluate SRFs.
881 *
882 * Note: using a list for the flags may seem like overkill, since there
883 * are only a few possible patterns for which levels contain SRFs.
884 * But this representation decouples callers from that knowledge.
885 */
886void
887split_pathtarget_at_srfs(PlannerInfo *root,
888 PathTarget *target, PathTarget *input_target,
889 List **targets, List **targets_contain_srfs)
890{
891 split_pathtarget_context context;
892 int max_depth;
893 bool need_extra_projection;
894 List *prev_level_tlist;
895 int lci;
896 ListCell *lc,
897 *lc1,
898 *lc2,
899 *lc3;
900
901 /*
902 * It's not unusual for planner.c to pass us two physically identical
903 * targets, in which case we can conclude without further ado that all
904 * expressions are available from the input. (The logic below would
905 * arrive at the same conclusion, but much more tediously.)
906 */
907 if (target == input_target)
908 {
909 *targets = list_make1(target);
910 *targets_contain_srfs = list_make1_int(false);
911 return;
912 }
913
914 /* Pass any input_target exprs down to split_pathtarget_walker() */
915 context.input_target_exprs = input_target ? input_target->exprs : NIL;
916
917 /*
918 * Initialize with empty level-zero lists, and no levels after that.
919 * (Note: we could dispense with representing level zero explicitly, since
920 * it will never receive any SRFs, but then we'd have to special-case that
921 * level when we get to building result PathTargets. Level zero describes
922 * the SRF-free PathTarget that will be given to the input plan node.)
923 */
924 context.level_srfs = list_make1(NIL);
925 context.level_input_vars = list_make1(NIL);
926 context.level_input_srfs = list_make1(NIL);
927
928 /* Initialize data we'll accumulate across all the target expressions */
929 context.current_input_vars = NIL;
930 context.current_input_srfs = NIL;
931 max_depth = 0;
932 need_extra_projection = false;
933
934 /* Scan each expression in the PathTarget looking for SRFs */
935 lci = 0;
936 foreach(lc, target->exprs)
937 {
938 Node *node = (Node *) lfirst(lc);
939
940 /* Tell split_pathtarget_walker about this expr's sortgroupref */
941 context.current_sgref = get_pathtarget_sortgroupref(target, lci);
942 lci++;
943
944 /*
945 * Find all SRFs and Vars (and Var-like nodes) in this expression, and
946 * enter them into appropriate lists within the context struct.
947 */
948 context.current_depth = 0;
949 split_pathtarget_walker(node, &context);
950
951 /* An expression containing no SRFs is of no further interest */
952 if (context.current_depth == 0)
953 continue;
954
955 /*
956 * Track max SRF nesting depth over the whole PathTarget. Also, if
957 * this expression establishes a new max depth, we no longer care
958 * whether previous expressions contained nested SRFs; we can handle
959 * any required projection for them in the final ProjectSet node.
960 */
961 if (max_depth < context.current_depth)
962 {
963 max_depth = context.current_depth;
964 need_extra_projection = false;
965 }
966
967 /*
968 * If any maximum-depth SRF is not at the top level of its expression,
969 * we'll need an extra Result node to compute the top-level scalar
970 * expression.
971 */
972 if (max_depth == context.current_depth && !IS_SRF_CALL(node))
973 need_extra_projection = true;
974 }
975
976 /*
977 * If we found no SRFs needing evaluation (maybe they were all present in
978 * input_target, or maybe they were all removed by const-simplification),
979 * then no ProjectSet is needed; fall out.
980 */
981 if (max_depth == 0)
982 {
983 *targets = list_make1(target);
984 *targets_contain_srfs = list_make1_int(false);
985 return;
986 }
987
988 /*
989 * The Vars and SRF outputs needed at top level can be added to the last
990 * level_input lists if we don't need an extra projection step. If we do
991 * need one, add a SRF-free level to the lists.
992 */
993 if (need_extra_projection)
994 {
995 context.level_srfs = lappend(context.level_srfs, NIL);
996 context.level_input_vars = lappend(context.level_input_vars,
997 context.current_input_vars);
998 context.level_input_srfs = lappend(context.level_input_srfs,
999 context.current_input_srfs);
1000 }
1001 else
1002 {
1003 lc = list_nth_cell(context.level_input_vars, max_depth);
1004 lfirst(lc) = list_concat(lfirst(lc), context.current_input_vars);
1005 lc = list_nth_cell(context.level_input_srfs, max_depth);
1006 lfirst(lc) = list_concat(lfirst(lc), context.current_input_srfs);
1007 }
1008
1009 /*
1010 * Now construct the output PathTargets. The original target can be used
1011 * as-is for the last one, but we need to construct a new SRF-free target
1012 * representing what the preceding plan node has to emit, as well as a
1013 * target for each intermediate ProjectSet node.
1014 */
1015 *targets = *targets_contain_srfs = NIL;
1016 prev_level_tlist = NIL;
1017
1018 forthree(lc1, context.level_srfs,
1019 lc2, context.level_input_vars,
1020 lc3, context.level_input_srfs)
1021 {
1022 List *level_srfs = (List *) lfirst(lc1);
1023 PathTarget *ntarget;
1024
1025 if (lnext(lc1) == NULL)
1026 {
1027 ntarget = target;
1028 }
1029 else
1030 {
1031 ntarget = create_empty_pathtarget();
1032
1033 /*
1034 * This target should actually evaluate any SRFs of the current
1035 * level, and it needs to propagate forward any Vars needed by
1036 * later levels, as well as SRFs computed earlier and needed by
1037 * later levels.
1038 */
1039 add_sp_items_to_pathtarget(ntarget, level_srfs);
1040 for_each_cell(lc, lnext(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, lnext(lc3))
1047 {
1048 List *input_srfs = (List *) lfirst(lc);
1049 ListCell *lcx;
1050
1051 foreach(lcx, input_srfs)
1052 {
1053 split_pathtarget_item *item = lfirst(lcx);
1054
1055 if (list_member(prev_level_tlist, item->expr))
1056 add_sp_item_to_pathtarget(ntarget, item);
1057 }
1058 }
1059 set_pathtarget_cost_width(root, ntarget);
1060 }
1061
1062 /*
1063 * Add current target and does-it-compute-SRFs flag to output lists.
1064 */
1065 *targets = lappend(*targets, ntarget);
1066 *targets_contain_srfs = lappend_int(*targets_contain_srfs,
1067 (level_srfs != NIL));
1068
1069 /* Remember this level's output for next pass */
1070 prev_level_tlist = ntarget->exprs;
1071 }
1072}
1073
1074/*
1075 * Recursively examine expressions for split_pathtarget_at_srfs.
1076 *
1077 * Note we make no effort here to prevent duplicate entries in the output
1078 * lists. Duplicates will be gotten rid of later.
1079 */
1080static bool
1081split_pathtarget_walker(Node *node, split_pathtarget_context *context)
1082{
1083 if (node == NULL)
1084 return false;
1085
1086 /*
1087 * A subexpression that matches an expression already computed in
1088 * input_target can be treated like a Var (which indeed it will be after
1089 * setrefs.c gets done with it), even if it's actually a SRF. Record it
1090 * as being needed for the current expression, and ignore any
1091 * substructure. (Note in particular that this preserves the identity of
1092 * any expressions that appear as sortgrouprefs in input_target.)
1093 */
1094 if (list_member(context->input_target_exprs, node))
1095 {
1096 split_pathtarget_item *item = palloc(sizeof(split_pathtarget_item));
1097
1098 item->expr = node;
1099 item->sortgroupref = context->current_sgref;
1100 context->current_input_vars = lappend(context->current_input_vars,
1101 item);
1102 return false;
1103 }
1104
1105 /*
1106 * Vars and Var-like constructs are expected to be gotten from the input,
1107 * too. We assume that these constructs cannot contain any SRFs (if one
1108 * does, there will be an executor failure from a misplaced SRF).
1109 */
1110 if (IsA(node, Var) ||
1111 IsA(node, PlaceHolderVar) ||
1112 IsA(node, Aggref) ||
1113 IsA(node, GroupingFunc) ||
1114 IsA(node, WindowFunc))
1115 {
1116 split_pathtarget_item *item = palloc(sizeof(split_pathtarget_item));
1117
1118 item->expr = node;
1119 item->sortgroupref = context->current_sgref;
1120 context->current_input_vars = lappend(context->current_input_vars,
1121 item);
1122 return false;
1123 }
1124
1125 /*
1126 * If it's a SRF, recursively examine its inputs, determine its level, and
1127 * make appropriate entries in the output lists.
1128 */
1129 if (IS_SRF_CALL(node))
1130 {
1131 split_pathtarget_item *item = palloc(sizeof(split_pathtarget_item));
1132 List *save_input_vars = context->current_input_vars;
1133 List *save_input_srfs = context->current_input_srfs;
1134 int save_current_depth = context->current_depth;
1135 int srf_depth;
1136 ListCell *lc;
1137
1138 item->expr = node;
1139 item->sortgroupref = context->current_sgref;
1140
1141 context->current_input_vars = NIL;
1142 context->current_input_srfs = NIL;
1143 context->current_depth = 0;
1144 context->current_sgref = 0; /* subexpressions are not sortgroup items */
1145
1146 (void) expression_tree_walker(node, split_pathtarget_walker,
1147 (void *) context);
1148
1149 /* Depth is one more than any SRF below it */
1150 srf_depth = context->current_depth + 1;
1151
1152 /* If new record depth, initialize another level of output lists */
1153 if (srf_depth >= list_length(context->level_srfs))
1154 {
1155 context->level_srfs = lappend(context->level_srfs, NIL);
1156 context->level_input_vars = lappend(context->level_input_vars, NIL);
1157 context->level_input_srfs = lappend(context->level_input_srfs, NIL);
1158 }
1159
1160 /* Record this SRF as needing to be evaluated at appropriate level */
1161 lc = list_nth_cell(context->level_srfs, srf_depth);
1162 lfirst(lc) = lappend(lfirst(lc), item);
1163
1164 /* Record its inputs as being needed at the same level */
1165 lc = list_nth_cell(context->level_input_vars, srf_depth);
1166 lfirst(lc) = list_concat(lfirst(lc), context->current_input_vars);
1167 lc = list_nth_cell(context->level_input_srfs, srf_depth);
1168 lfirst(lc) = list_concat(lfirst(lc), context->current_input_srfs);
1169
1170 /*
1171 * Restore caller-level state and update it for presence of this SRF.
1172 * Notice we report the SRF itself as being needed for evaluation of
1173 * surrounding expression.
1174 */
1175 context->current_input_vars = save_input_vars;
1176 context->current_input_srfs = lappend(save_input_srfs, item);
1177 context->current_depth = Max(save_current_depth, srf_depth);
1178
1179 /* We're done here */
1180 return false;
1181 }
1182
1183 /*
1184 * Otherwise, the node is a scalar (non-set) expression, so recurse to
1185 * examine its inputs.
1186 */
1187 context->current_sgref = 0; /* subexpressions are not sortgroup items */
1188 return expression_tree_walker(node, split_pathtarget_walker,
1189 (void *) context);
1190}
1191
1192/*
1193 * Add a split_pathtarget_item to the PathTarget, unless a matching item is
1194 * already present. This is like add_new_column_to_pathtarget, but allows
1195 * for sortgrouprefs to be handled. An item having zero sortgroupref can
1196 * be merged with one that has a sortgroupref, acquiring the latter's
1197 * sortgroupref.
1198 *
1199 * Note that we don't worry about possibly adding duplicate sortgrouprefs
1200 * to the PathTarget. That would be bad, but it should be impossible unless
1201 * the target passed to split_pathtarget_at_srfs already had duplicates.
1202 * As long as it didn't, we can have at most one split_pathtarget_item with
1203 * any particular nonzero sortgroupref.
1204 */
1205static void
1206add_sp_item_to_pathtarget(PathTarget *target, split_pathtarget_item *item)
1207{
1208 int lci;
1209 ListCell *lc;
1210
1211 /*
1212 * Look for a pre-existing entry that is equal() and does not have a
1213 * conflicting sortgroupref already.
1214 */
1215 lci = 0;
1216 foreach(lc, target->exprs)
1217 {
1218 Node *node = (Node *) lfirst(lc);
1219 Index sgref = get_pathtarget_sortgroupref(target, lci);
1220
1221 if ((item->sortgroupref == sgref ||
1222 item->sortgroupref == 0 ||
1223 sgref == 0) &&
1224 equal(item->expr, node))
1225 {
1226 /* Found a match. Assign item's sortgroupref if it has one. */
1227 if (item->sortgroupref)
1228 {
1229 if (target->sortgrouprefs == NULL)
1230 {
1231 target->sortgrouprefs = (Index *)
1232 palloc0(list_length(target->exprs) * sizeof(Index));
1233 }
1234 target->sortgrouprefs[lci] = item->sortgroupref;
1235 }
1236 return;
1237 }
1238 lci++;
1239 }
1240
1241 /*
1242 * No match, so add item to PathTarget. Copy the expr for safety.
1243 */
1244 add_column_to_pathtarget(target, (Expr *) copyObject(item->expr),
1245 item->sortgroupref);
1246}
1247
1248/*
1249 * Apply add_sp_item_to_pathtarget to each element of list.
1250 */
1251static void
1252add_sp_items_to_pathtarget(PathTarget *target, List *items)
1253{
1254 ListCell *lc;
1255
1256 foreach(lc, items)
1257 {
1258 split_pathtarget_item *item = lfirst(lc);
1259
1260 add_sp_item_to_pathtarget(target, item);
1261 }
1262}
1263