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-2025, 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 * Test if an expression node represents a SRF call. Beware multiple eval!
26 *
27 * Please note that this is only meant for use in split_pathtarget_at_srfs();
28 * if you use it anywhere else, your code is almost certainly wrong for SRFs
29 * nested within expressions. Use expression_returns_set() instead.
30 */
31#define IS_SRF_CALL(node) \
32 ((IsA(node, FuncExpr) && ((FuncExpr *) (node))->funcretset) || \
33 (IsA(node, OpExpr) && ((OpExpr *) (node))->opretset))
34
35/*
36 * Data structures for split_pathtarget_at_srfs(). To preserve the identity
37 * of sortgroupref items even if they are textually equal(), what we track is
38 * not just bare expressions but expressions plus their sortgroupref indexes.
39 */
40typedef struct
41{
42 Node *expr; /* some subexpression of a PathTarget */
43 Index sortgroupref; /* its sortgroupref, or 0 if none */
45
46typedef struct
47{
48 /* This is a List of bare expressions: */
49 List *input_target_exprs; /* exprs available from input */
50 /* These are Lists of Lists of split_pathtarget_items: */
51 List *level_srfs; /* SRF exprs to evaluate at each level */
52 List *level_input_vars; /* input vars needed at each level */
53 List *level_input_srfs; /* input SRFs needed at each level */
54 /* These are Lists of split_pathtarget_items: */
55 List *current_input_vars; /* vars needed in current subexpr */
56 List *current_input_srfs; /* SRFs needed in current subexpr */
57 /* Auxiliary data for current split_pathtarget_walker traversal: */
58 int current_depth; /* max SRF depth in current subexpr */
59 Index current_sgref; /* current subexpr's sortgroupref, or 0 */
61
62static bool split_pathtarget_walker(Node *node,
64static void add_sp_item_to_pathtarget(PathTarget *target,
66static void add_sp_items_to_pathtarget(PathTarget *target, List *items);
67
68
69/*****************************************************************************
70 * Target list creation and searching utilities
71 *****************************************************************************/
72
73/*
74 * tlist_member
75 * Finds the (first) member of the given tlist whose expression is
76 * equal() to the given expression. Result is NULL if no such member.
77 */
79tlist_member(Expr *node, List *targetlist)
80{
81 ListCell *temp;
82
83 foreach(temp, targetlist)
84 {
85 TargetEntry *tlentry = (TargetEntry *) lfirst(temp);
86
87 if (equal(node, tlentry->expr))
88 return tlentry;
89 }
90 return NULL;
91}
92
93/*
94 * tlist_member_match_var
95 * Same as above, except that we match the provided Var on the basis
96 * of varno/varattno/varlevelsup/vartype only, rather than full equal().
97 *
98 * This is needed in some cases where we can't be sure of an exact typmod
99 * match. For safety, though, we insist on vartype match.
100 */
101static TargetEntry *
103{
104 ListCell *temp;
105
106 foreach(temp, targetlist)
107 {
108 TargetEntry *tlentry = (TargetEntry *) lfirst(temp);
109 Var *tlvar = (Var *) tlentry->expr;
110
111 if (!tlvar || !IsA(tlvar, Var))
112 continue;
113 if (var->varno == tlvar->varno &&
114 var->varattno == tlvar->varattno &&
115 var->varlevelsup == tlvar->varlevelsup &&
116 var->vartype == tlvar->vartype)
117 return tlentry;
118 }
119 return NULL;
120}
121
122/*
123 * add_to_flat_tlist
124 * Add more items to a flattened tlist (if they're not already in it)
125 *
126 * 'tlist' is the flattened tlist
127 * 'exprs' is a list of expressions (usually, but not necessarily, Vars)
128 *
129 * Returns the extended tlist.
130 */
131List *
133{
134 int next_resno = list_length(tlist) + 1;
135 ListCell *lc;
136
137 foreach(lc, exprs)
138 {
139 Expr *expr = (Expr *) lfirst(lc);
140
141 if (!tlist_member(expr, tlist))
142 {
143 TargetEntry *tle;
144
145 tle = makeTargetEntry(copyObject(expr), /* copy needed?? */
146 next_resno++,
147 NULL,
148 false);
149 tlist = lappend(tlist, tle);
150 }
151 }
152 return tlist;
153}
154
155
156/*
157 * get_tlist_exprs
158 * Get just the expression subtrees of a tlist
159 *
160 * Resjunk columns are ignored unless includeJunk is true
161 */
162List *
163get_tlist_exprs(List *tlist, bool includeJunk)
164{
165 List *result = NIL;
166 ListCell *l;
167
168 foreach(l, tlist)
169 {
170 TargetEntry *tle = (TargetEntry *) lfirst(l);
171
172 if (tle->resjunk && !includeJunk)
173 continue;
174
175 result = lappend(result, tle->expr);
176 }
177 return result;
178}
179
180
181/*
182 * count_nonjunk_tlist_entries
183 * What it says ...
184 */
185int
187{
188 int len = 0;
189 ListCell *l;
190
191 foreach(l, tlist)
192 {
193 TargetEntry *tle = (TargetEntry *) lfirst(l);
194
195 if (!tle->resjunk)
196 len++;
197 }
198 return len;
199}
200
201
202/*
203 * tlist_same_exprs
204 * Check whether two target lists contain the same expressions
205 *
206 * Note: this function is used to decide whether it's safe to jam a new tlist
207 * into a non-projection-capable plan node. Obviously we can't do that unless
208 * the node's tlist shows it already returns the column values we want.
209 * However, we can ignore the TargetEntry attributes resname, ressortgroupref,
210 * resorigtbl, resorigcol, and resjunk, because those are only labelings that
211 * don't affect the row values computed by the node. (Moreover, if we didn't
212 * ignore them, we'd frequently fail to make the desired optimization, since
213 * the planner tends to not bother to make resname etc. valid in intermediate
214 * plan nodes.) Note that on success, the caller must still jam the desired
215 * tlist into the plan node, else it won't have the desired labeling fields.
216 */
217bool
218tlist_same_exprs(List *tlist1, List *tlist2)
219{
220 ListCell *lc1,
221 *lc2;
222
223 if (list_length(tlist1) != list_length(tlist2))
224 return false; /* not same length, so can't match */
225
226 forboth(lc1, tlist1, lc2, tlist2)
227 {
228 TargetEntry *tle1 = (TargetEntry *) lfirst(lc1);
229 TargetEntry *tle2 = (TargetEntry *) lfirst(lc2);
230
231 if (!equal(tle1->expr, tle2->expr))
232 return false;
233 }
234
235 return true;
236}
237
238
239/*
240 * Does tlist have same output datatypes as listed in colTypes?
241 *
242 * Resjunk columns are ignored if junkOK is true; otherwise presence of
243 * a resjunk column will always cause a 'false' result.
244 *
245 * Note: currently no callers care about comparing typmods.
246 */
247bool
248tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK)
249{
250 ListCell *l;
251 ListCell *curColType = list_head(colTypes);
252
253 foreach(l, tlist)
254 {
255 TargetEntry *tle = (TargetEntry *) lfirst(l);
256
257 if (tle->resjunk)
258 {
259 if (!junkOK)
260 return false;
261 }
262 else
263 {
264 if (curColType == NULL)
265 return false; /* tlist longer than colTypes */
266 if (exprType((Node *) tle->expr) != lfirst_oid(curColType))
267 return false;
268 curColType = lnext(colTypes, curColType);
269 }
270 }
271 if (curColType != NULL)
272 return false; /* tlist shorter than colTypes */
273 return true;
274}
275
276/*
277 * Does tlist have same exposed collations as listed in colCollations?
278 *
279 * Identical logic to the above, but for collations.
280 */
281bool
282tlist_same_collations(List *tlist, List *colCollations, bool junkOK)
283{
284 ListCell *l;
285 ListCell *curColColl = list_head(colCollations);
286
287 foreach(l, tlist)
288 {
289 TargetEntry *tle = (TargetEntry *) lfirst(l);
290
291 if (tle->resjunk)
292 {
293 if (!junkOK)
294 return false;
295 }
296 else
297 {
298 if (curColColl == NULL)
299 return false; /* tlist longer than colCollations */
300 if (exprCollation((Node *) tle->expr) != lfirst_oid(curColColl))
301 return false;
302 curColColl = lnext(colCollations, curColColl);
303 }
304 }
305 if (curColColl != NULL)
306 return false; /* tlist shorter than colCollations */
307 return true;
308}
309
310/*
311 * apply_tlist_labeling
312 * Apply the TargetEntry labeling attributes of src_tlist to dest_tlist
313 *
314 * This is useful for reattaching column names etc to a plan's final output
315 * targetlist.
316 */
317void
318apply_tlist_labeling(List *dest_tlist, List *src_tlist)
319{
320 ListCell *ld,
321 *ls;
322
323 Assert(list_length(dest_tlist) == list_length(src_tlist));
324 forboth(ld, dest_tlist, ls, src_tlist)
325 {
326 TargetEntry *dest_tle = (TargetEntry *) lfirst(ld);
327 TargetEntry *src_tle = (TargetEntry *) lfirst(ls);
328
329 Assert(dest_tle->resno == src_tle->resno);
330 dest_tle->resname = src_tle->resname;
331 dest_tle->ressortgroupref = src_tle->ressortgroupref;
332 dest_tle->resorigtbl = src_tle->resorigtbl;
333 dest_tle->resorigcol = src_tle->resorigcol;
334 dest_tle->resjunk = src_tle->resjunk;
335 }
336}
337
338
339/*
340 * get_sortgroupref_tle
341 * Find the targetlist entry matching the given SortGroupRef index,
342 * and return it.
343 */
345get_sortgroupref_tle(Index sortref, List *targetList)
346{
347 ListCell *l;
348
349 foreach(l, targetList)
350 {
351 TargetEntry *tle = (TargetEntry *) lfirst(l);
352
353 if (tle->ressortgroupref == sortref)
354 return tle;
355 }
356
357 elog(ERROR, "ORDER/GROUP BY expression not found in targetlist");
358 return NULL; /* keep compiler quiet */
359}
360
361/*
362 * get_sortgroupclause_tle
363 * Find the targetlist entry matching the given SortGroupClause
364 * by ressortgroupref, and return it.
365 */
368 List *targetList)
369{
370 return get_sortgroupref_tle(sgClause->tleSortGroupRef, targetList);
371}
372
373/*
374 * get_sortgroupclause_expr
375 * Find the targetlist entry matching the given SortGroupClause
376 * by ressortgroupref, and return its expression.
377 */
378Node *
380{
381 TargetEntry *tle = get_sortgroupclause_tle(sgClause, targetList);
382
383 return (Node *) tle->expr;
384}
385
386/*
387 * get_sortgrouplist_exprs
388 * Given a list of SortGroupClauses, build a list
389 * of the referenced targetlist expressions.
390 */
391List *
392get_sortgrouplist_exprs(List *sgClauses, List *targetList)
393{
394 List *result = NIL;
395 ListCell *l;
396
397 foreach(l, sgClauses)
398 {
399 SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
400 Node *sortexpr;
401
402 sortexpr = get_sortgroupclause_expr(sortcl, targetList);
403 result = lappend(result, sortexpr);
404 }
405 return result;
406}
407
408
409/*****************************************************************************
410 * Functions to extract data from a list of SortGroupClauses
411 *
412 * These don't really belong in tlist.c, but they are sort of related to the
413 * functions just above, and they don't seem to deserve their own file.
414 *****************************************************************************/
415
416/*
417 * get_sortgroupref_clause
418 * Find the SortGroupClause matching the given SortGroupRef index,
419 * and return it.
420 */
423{
424 ListCell *l;
425
426 foreach(l, clauses)
427 {
429
430 if (cl->tleSortGroupRef == sortref)
431 return cl;
432 }
433
434 elog(ERROR, "ORDER/GROUP BY expression not found in list");
435 return NULL; /* keep compiler quiet */
436}
437
438/*
439 * get_sortgroupref_clause_noerr
440 * As above, but return NULL rather than throwing an error if not found.
441 */
444{
445 ListCell *l;
446
447 foreach(l, clauses)
448 {
450
451 if (cl->tleSortGroupRef == sortref)
452 return cl;
453 }
454
455 return NULL;
456}
457
458/*
459 * extract_grouping_ops - make an array of the equality operator OIDs
460 * for a SortGroupClause list
461 */
462Oid *
464{
465 int numCols = list_length(groupClause);
466 int colno = 0;
467 Oid *groupOperators;
468 ListCell *glitem;
469
470 groupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
471
472 foreach(glitem, groupClause)
473 {
474 SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
475
476 groupOperators[colno] = groupcl->eqop;
477 Assert(OidIsValid(groupOperators[colno]));
478 colno++;
479 }
480
481 return groupOperators;
482}
483
484/*
485 * extract_grouping_collations - make an array of the grouping column collations
486 * for a SortGroupClause list
487 */
488Oid *
490{
491 int numCols = list_length(groupClause);
492 int colno = 0;
493 Oid *grpCollations;
494 ListCell *glitem;
495
496 grpCollations = (Oid *) palloc(sizeof(Oid) * numCols);
497
498 foreach(glitem, groupClause)
499 {
500 SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
501 TargetEntry *tle = get_sortgroupclause_tle(groupcl, tlist);
502
503 grpCollations[colno++] = exprCollation((Node *) tle->expr);
504 }
505
506 return grpCollations;
507}
508
509/*
510 * extract_grouping_cols - make an array of the grouping column resnos
511 * for a SortGroupClause list
512 */
514extract_grouping_cols(List *groupClause, List *tlist)
515{
516 AttrNumber *grpColIdx;
517 int numCols = list_length(groupClause);
518 int colno = 0;
519 ListCell *glitem;
520
521 grpColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
522
523 foreach(glitem, groupClause)
524 {
525 SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
526 TargetEntry *tle = get_sortgroupclause_tle(groupcl, tlist);
527
528 grpColIdx[colno++] = tle->resno;
529 }
530
531 return grpColIdx;
532}
533
534/*
535 * grouping_is_sortable - is it possible to implement grouping list by sorting?
536 *
537 * This is easy since the parser will have included a sortop if one exists.
538 */
539bool
541{
542 ListCell *glitem;
543
544 foreach(glitem, groupClause)
545 {
546 SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
547
548 if (!OidIsValid(groupcl->sortop))
549 return false;
550 }
551 return true;
552}
553
554/*
555 * grouping_is_hashable - is it possible to implement grouping list by hashing?
556 *
557 * We rely on the parser to have set the hashable flag correctly.
558 */
559bool
561{
562 ListCell *glitem;
563
564 foreach(glitem, groupClause)
565 {
566 SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
567
568 if (!groupcl->hashable)
569 return false;
570 }
571 return true;
572}
573
574
575/*****************************************************************************
576 * PathTarget manipulation functions
577 *
578 * PathTarget is a somewhat stripped-down version of a full targetlist; it
579 * omits all the TargetEntry decoration except (optionally) sortgroupref data,
580 * and it adds evaluation cost and output data width info.
581 *****************************************************************************/
582
583/*
584 * make_pathtarget_from_tlist
585 * Construct a PathTarget equivalent to the given targetlist.
586 *
587 * This leaves the cost and width fields as zeroes. Most callers will want
588 * to use create_pathtarget(), so as to get those set.
589 */
592{
593 PathTarget *target = makeNode(PathTarget);
594 int i;
595 ListCell *lc;
596
597 target->sortgrouprefs = (Index *) palloc(list_length(tlist) * sizeof(Index));
598
599 i = 0;
600 foreach(lc, tlist)
601 {
602 TargetEntry *tle = (TargetEntry *) lfirst(lc);
603
604 target->exprs = lappend(target->exprs, tle->expr);
605 target->sortgrouprefs[i] = tle->ressortgroupref;
606 i++;
607 }
608
609 /*
610 * Mark volatility as unknown. The contain_volatile_functions function
611 * will determine if there are any volatile functions when called for the
612 * first time with this PathTarget.
613 */
615
616 return target;
617}
618
619/*
620 * make_tlist_from_pathtarget
621 * Construct a targetlist from a PathTarget.
622 */
623List *
625{
626 List *tlist = NIL;
627 int i;
628 ListCell *lc;
629
630 i = 0;
631 foreach(lc, target->exprs)
632 {
633 Expr *expr = (Expr *) lfirst(lc);
634 TargetEntry *tle;
635
636 tle = makeTargetEntry(expr,
637 i + 1,
638 NULL,
639 false);
640 if (target->sortgrouprefs)
641 tle->ressortgroupref = target->sortgrouprefs[i];
642 tlist = lappend(tlist, tle);
643 i++;
644 }
645
646 return tlist;
647}
648
649/*
650 * copy_pathtarget
651 * Copy a PathTarget.
652 *
653 * The new PathTarget has its own exprs List, but shares the underlying
654 * target expression trees with the old one.
655 */
658{
660
661 /* Copy scalar fields */
662 memcpy(dst, src, sizeof(PathTarget));
663 /* Shallow-copy the expression list */
664 dst->exprs = list_copy(src->exprs);
665 /* Duplicate sortgrouprefs if any (if not, the memcpy handled this) */
666 if (src->sortgrouprefs)
667 {
668 Size nbytes = list_length(src->exprs) * sizeof(Index);
669
670 dst->sortgrouprefs = (Index *) palloc(nbytes);
671 memcpy(dst->sortgrouprefs, src->sortgrouprefs, nbytes);
672 }
673 return dst;
674}
675
676/*
677 * create_empty_pathtarget
678 * Create an empty (zero columns, zero cost) PathTarget.
679 */
682{
683 /* This is easy, but we don't want callers to hard-wire this ... */
684 return makeNode(PathTarget);
685}
686
687/*
688 * add_column_to_pathtarget
689 * Append a target column to the PathTarget.
690 *
691 * As with make_pathtarget_from_tlist, we leave it to the caller to update
692 * the cost and width fields.
693 */
694void
695add_column_to_pathtarget(PathTarget *target, Expr *expr, Index sortgroupref)
696{
697 /* Updating the exprs list is easy ... */
698 target->exprs = lappend(target->exprs, expr);
699 /* ... the sortgroupref data, a bit less so */
700 if (target->sortgrouprefs)
701 {
702 int nexprs = list_length(target->exprs);
703
704 /* This might look inefficient, but actually it's usually cheap */
705 target->sortgrouprefs = (Index *)
706 repalloc(target->sortgrouprefs, nexprs * sizeof(Index));
707 target->sortgrouprefs[nexprs - 1] = sortgroupref;
708 }
709 else if (sortgroupref)
710 {
711 /* Adding sortgroupref labeling to a previously unlabeled target */
712 int nexprs = list_length(target->exprs);
713
714 target->sortgrouprefs = (Index *) palloc0(nexprs * sizeof(Index));
715 target->sortgrouprefs[nexprs - 1] = sortgroupref;
716 }
717
718 /*
719 * Reset has_volatile_expr to UNKNOWN. We just leave it up to
720 * contain_volatile_functions to set this properly again. Technically we
721 * could save some effort here and just check the new Expr, but it seems
722 * better to keep the logic for setting this flag in one location rather
723 * than duplicating the logic here.
724 */
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 */
740void
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 */
751void
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 */
773void
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 evaluable 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 */
880void
882 PathTarget *target, PathTarget *input_target,
883 List **targets, List **targets_contain_srfs)
884{
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);
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 }
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 */
1076static 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
1142 (void) expression_tree_walker(node, split_pathtarget_walker, context);
1143
1144 /* Depth is one more than any SRF below it */
1145 srf_depth = context->current_depth + 1;
1146
1147 /* If new record depth, initialize another level of output lists */
1148 if (srf_depth >= list_length(context->level_srfs))
1149 {
1150 context->level_srfs = lappend(context->level_srfs, NIL);
1151 context->level_input_vars = lappend(context->level_input_vars, NIL);
1152 context->level_input_srfs = lappend(context->level_input_srfs, NIL);
1153 }
1154
1155 /* Record this SRF as needing to be evaluated at appropriate level */
1156 lc = list_nth_cell(context->level_srfs, srf_depth);
1157 lfirst(lc) = lappend(lfirst(lc), item);
1158
1159 /* Record its inputs as being needed at the same level */
1160 lc = list_nth_cell(context->level_input_vars, srf_depth);
1161 lfirst(lc) = list_concat(lfirst(lc), context->current_input_vars);
1162 lc = list_nth_cell(context->level_input_srfs, srf_depth);
1163 lfirst(lc) = list_concat(lfirst(lc), context->current_input_srfs);
1164
1165 /*
1166 * Restore caller-level state and update it for presence of this SRF.
1167 * Notice we report the SRF itself as being needed for evaluation of
1168 * surrounding expression.
1169 */
1170 context->current_input_vars = save_input_vars;
1171 context->current_input_srfs = lappend(save_input_srfs, item);
1172 context->current_depth = Max(save_current_depth, srf_depth);
1173
1174 /* We're done here */
1175 return false;
1176 }
1177
1178 /*
1179 * Otherwise, the node is a scalar (non-set) expression, so recurse to
1180 * examine its inputs.
1181 */
1182 context->current_sgref = 0; /* subexpressions are not sortgroup items */
1183 return expression_tree_walker(node, split_pathtarget_walker, context);
1184}
1185
1186/*
1187 * Add a split_pathtarget_item to the PathTarget, unless a matching item is
1188 * already present. This is like add_new_column_to_pathtarget, but allows
1189 * for sortgrouprefs to be handled. An item having zero sortgroupref can
1190 * be merged with one that has a sortgroupref, acquiring the latter's
1191 * sortgroupref.
1192 *
1193 * Note that we don't worry about possibly adding duplicate sortgrouprefs
1194 * to the PathTarget. That would be bad, but it should be impossible unless
1195 * the target passed to split_pathtarget_at_srfs already had duplicates.
1196 * As long as it didn't, we can have at most one split_pathtarget_item with
1197 * any particular nonzero sortgroupref.
1198 */
1199static void
1201{
1202 int lci;
1203 ListCell *lc;
1204
1205 /*
1206 * Look for a pre-existing entry that is equal() and does not have a
1207 * conflicting sortgroupref already.
1208 */
1209 lci = 0;
1210 foreach(lc, target->exprs)
1211 {
1212 Node *node = (Node *) lfirst(lc);
1213 Index sgref = get_pathtarget_sortgroupref(target, lci);
1214
1215 if ((item->sortgroupref == sgref ||
1216 item->sortgroupref == 0 ||
1217 sgref == 0) &&
1218 equal(item->expr, node))
1219 {
1220 /* Found a match. Assign item's sortgroupref if it has one. */
1221 if (item->sortgroupref)
1222 {
1223 if (target->sortgrouprefs == NULL)
1224 {
1225 target->sortgrouprefs = (Index *)
1226 palloc0(list_length(target->exprs) * sizeof(Index));
1227 }
1228 target->sortgrouprefs[lci] = item->sortgroupref;
1229 }
1230 return;
1231 }
1232 lci++;
1233 }
1234
1235 /*
1236 * No match, so add item to PathTarget. Copy the expr for safety.
1237 */
1238 add_column_to_pathtarget(target, (Expr *) copyObject(item->expr),
1239 item->sortgroupref);
1240}
1241
1242/*
1243 * Apply add_sp_item_to_pathtarget to each element of list.
1244 */
1245static void
1247{
1248 ListCell *lc;
1249
1250 foreach(lc, items)
1251 {
1252 split_pathtarget_item *item = lfirst(lc);
1253
1254 add_sp_item_to_pathtarget(target, item);
1255 }
1256}
int16 AttrNumber
Definition: attnum.h:21
#define Max(x, y)
Definition: c.h:955
#define Assert(condition)
Definition: c.h:815
unsigned int Index
Definition: c.h:571
#define OidIsValid(objectId)
Definition: c.h:732
size_t Size
Definition: c.h:562
PathTarget * set_pathtarget_cost_width(PlannerInfo *root, PathTarget *target)
Definition: costsize.c:6342
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:225
bool equal(const void *a, const void *b)
Definition: equalfuncs.c:223
int i
Definition: isn.c:72
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:76
List * lappend(List *list, void *datum)
Definition: list.c:339
List * list_concat(List *list1, const List *list2)
Definition: list.c:561
List * list_copy(const List *oldlist)
Definition: list.c:1573
List * lappend_int(List *list, int datum)
Definition: list.c:357
bool list_member(const List *list, const void *datum)
Definition: list.c:661
TargetEntry * makeTargetEntry(Expr *expr, AttrNumber resno, char *resname, bool resjunk)
Definition: makefuncs.c:242
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1541
void * palloc0(Size size)
Definition: mcxt.c:1347
void * palloc(Size size)
Definition: mcxt.c:1317
Oid exprType(const Node *expr)
Definition: nodeFuncs.c:42
Oid exprCollation(const Node *expr)
Definition: nodeFuncs.c:821
#define expression_tree_walker(n, w, c)
Definition: nodeFuncs.h:153
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
#define copyObject(obj)
Definition: nodes.h:224
#define makeNode(_type_)
Definition: nodes.h:155
#define get_pathtarget_sortgroupref(target, colno)
Definition: pathnodes.h:1579
@ VOLATILITY_NOVOLATILE
Definition: pathnodes.h:1530
@ VOLATILITY_UNKNOWN
Definition: pathnodes.h:1528
const void size_t len
#define lfirst(lc)
Definition: pg_list.h:172
static int list_length(const List *l)
Definition: pg_list.h:152
#define NIL
Definition: pg_list.h:68
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:518
#define list_make1(x1)
Definition: pg_list.h:212
#define forthree(cell1, list1, cell2, list2, cell3, list3)
Definition: pg_list.h:563
#define for_each_cell(cell, lst, initcell)
Definition: pg_list.h:438
static ListCell * list_nth_cell(const List *list, int n)
Definition: pg_list.h:277
static ListCell * list_head(const List *l)
Definition: pg_list.h:128
static ListCell * lnext(const List *l, const ListCell *c)
Definition: pg_list.h:343
#define list_make1_int(x1)
Definition: pg_list.h:227
#define lfirst_oid(lc)
Definition: pg_list.h:174
unsigned int Oid
Definition: postgres_ext.h:32
tree ctl root
Definition: radixtree.h:1857
Definition: pg_list.h:54
Definition: nodes.h:129
VolatileFunctionStatus has_volatile_expr
Definition: pathnodes.h:1575
List * exprs
Definition: pathnodes.h:1563
Index tleSortGroupRef
Definition: parsenodes.h:1447
Expr * expr
Definition: primnodes.h:2219
AttrNumber resno
Definition: primnodes.h:2221
Index ressortgroupref
Definition: primnodes.h:2225
Definition: primnodes.h:262
AttrNumber varattno
Definition: primnodes.h:274
int varno
Definition: primnodes.h:269
Index varlevelsup
Definition: primnodes.h:294
List * level_input_srfs
Definition: tlist.c:53
List * current_input_srfs
Definition: tlist.c:56
List * input_target_exprs
Definition: tlist.c:49
List * current_input_vars
Definition: tlist.c:55
List * level_input_vars
Definition: tlist.c:52
Index sortgroupref
Definition: tlist.c:43
static ItemArray items
Definition: test_tidstore.c:48
bool tlist_same_collations(List *tlist, List *colCollations, bool junkOK)
Definition: tlist.c:282
Oid * extract_grouping_ops(List *groupClause)
Definition: tlist.c:463
TargetEntry * tlist_member(Expr *node, List *targetlist)
Definition: tlist.c:79
bool tlist_same_exprs(List *tlist1, List *tlist2)
Definition: tlist.c:218
void apply_tlist_labeling(List *dest_tlist, List *src_tlist)
Definition: tlist.c:318
SortGroupClause * get_sortgroupref_clause_noerr(Index sortref, List *clauses)
Definition: tlist.c:443
SortGroupClause * get_sortgroupref_clause(Index sortref, List *clauses)
Definition: tlist.c:422
void apply_pathtarget_labeling_to_tlist(List *tlist, PathTarget *target)
Definition: tlist.c:774
#define IS_SRF_CALL(node)
Definition: tlist.c:31
bool grouping_is_sortable(List *groupClause)
Definition: tlist.c:540
PathTarget * make_pathtarget_from_tlist(List *tlist)
Definition: tlist.c:591
List * make_tlist_from_pathtarget(PathTarget *target)
Definition: tlist.c:624
PathTarget * copy_pathtarget(PathTarget *src)
Definition: tlist.c:657
static void add_sp_item_to_pathtarget(PathTarget *target, split_pathtarget_item *item)
Definition: tlist.c:1200
static bool split_pathtarget_walker(Node *node, split_pathtarget_context *context)
Definition: tlist.c:1077
AttrNumber * extract_grouping_cols(List *groupClause, List *tlist)
Definition: tlist.c:514
TargetEntry * get_sortgroupclause_tle(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:367
void add_new_columns_to_pathtarget(PathTarget *target, List *exprs)
Definition: tlist.c:752
static void add_sp_items_to_pathtarget(PathTarget *target, List *items)
Definition: tlist.c:1246
PathTarget * create_empty_pathtarget(void)
Definition: tlist.c:681
List * get_sortgrouplist_exprs(List *sgClauses, List *targetList)
Definition: tlist.c:392
TargetEntry * get_sortgroupref_tle(Index sortref, List *targetList)
Definition: tlist.c:345
List * add_to_flat_tlist(List *tlist, List *exprs)
Definition: tlist.c:132
int count_nonjunk_tlist_entries(List *tlist)
Definition: tlist.c:186
List * get_tlist_exprs(List *tlist, bool includeJunk)
Definition: tlist.c:163
void add_new_column_to_pathtarget(PathTarget *target, Expr *expr)
Definition: tlist.c:741
void split_pathtarget_at_srfs(PlannerInfo *root, PathTarget *target, PathTarget *input_target, List **targets, List **targets_contain_srfs)
Definition: tlist.c:881
bool grouping_is_hashable(List *groupClause)
Definition: tlist.c:560
Oid * extract_grouping_collations(List *groupClause, List *tlist)
Definition: tlist.c:489
static TargetEntry * tlist_member_match_var(Var *var, List *targetlist)
Definition: tlist.c:102
void add_column_to_pathtarget(PathTarget *target, Expr *expr, Index sortgroupref)
Definition: tlist.c:695
Node * get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
Definition: tlist.c:379
bool tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK)
Definition: tlist.c:248