1/*-------------------------------------------------------------------------
4 * Target list manipulation routines
6 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * src/backend/optimizer/util/tlist.c
13 *-------------------------------------------------------------------------
25 * Test if an expression node represents a SRF call. Beware multiple eval!
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.
31 #define IS_SRF_CALL(node) \
32 ((IsA(node, FuncExpr) && ((FuncExpr *) (node))->funcretset) || \
33 (IsA(node, OpExpr) && ((OpExpr *) (node))->opretset))
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.
42 Node *
expr;
/* some subexpression of a PathTarget */
48 /* This is a List of bare expressions: */
50 /* These are Lists of Lists of split_pathtarget_items: */
54 /* These are Lists of split_pathtarget_items: */
57 /* Auxiliary data for current split_pathtarget_walker traversal: */
69/*****************************************************************************
70 * Target list creation and searching utilities
71 *****************************************************************************/
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.
83 foreach(temp, targetlist)
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().
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.
106 foreach(temp, targetlist)
116 var->vartype == tlvar->vartype)
124 * Add more items to a flattened tlist (if they're not already in it)
126 * 'tlist' is the flattened tlist
127 * 'exprs' is a list of expressions (usually, but not necessarily, Vars)
129 * Returns the extended tlist.
158 * Get just the expression subtrees of a tlist
160 * Resjunk columns are ignored unless includeJunk is true
172 if (tle->resjunk && !includeJunk)
182 * count_nonjunk_tlist_entries
204 * Check whether two target lists contain the same expressions
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.
224 return false;
/* not same length, so can't match */
226 forboth(lc1, tlist1, lc2, tlist2)
240 * Does tlist have same output datatypes as listed in colTypes?
242 * Resjunk columns are ignored if junkOK is true; otherwise presence of
243 * a resjunk column will always cause a 'false' result.
245 * Note: currently no callers care about comparing typmods.
264 if (curColType == NULL)
265 return false;
/* tlist longer than colTypes */
268 curColType =
lnext(colTypes, curColType);
271 if (curColType != NULL)
272 return false;
/* tlist shorter than colTypes */
277 * Does tlist have same exposed collations as listed in colCollations?
279 * Identical logic to the above, but for collations.
298 if (curColColl == NULL)
299 return false;
/* tlist longer than colCollations */
302 curColColl =
lnext(colCollations, curColColl);
305 if (curColColl != NULL)
306 return false;
/* tlist shorter than colCollations */
311 * apply_tlist_labeling
312 * Apply the TargetEntry labeling attributes of src_tlist to dest_tlist
314 * This is useful for reattaching column names etc to a plan's final output
324 forboth(ld, dest_tlist, ls, src_tlist)
330 dest_tle->resname = src_tle->resname;
332 dest_tle->resorigtbl = src_tle->resorigtbl;
333 dest_tle->resorigcol = src_tle->resorigcol;
334 dest_tle->resjunk = src_tle->resjunk;
340 * get_sortgroupref_tle
341 * Find the targetlist entry matching the given SortGroupRef index,
349 foreach(l, targetList)
357 elog(
ERROR,
"ORDER/GROUP BY expression not found in targetlist");
358 return NULL;
/* keep compiler quiet */
362 * get_sortgroupclause_tle
363 * Find the targetlist entry matching the given SortGroupClause
364 * by ressortgroupref, and return it.
374 * get_sortgroupclause_expr
375 * Find the targetlist entry matching the given SortGroupClause
376 * by ressortgroupref, and return its expression.
387 * get_sortgrouplist_exprs
388 * Given a list of SortGroupClauses, build a list
389 * of the referenced targetlist expressions.
397 foreach(l, sgClauses)
403 result =
lappend(result, sortexpr);
409/*****************************************************************************
410 * Functions to extract data from a list of SortGroupClauses
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 *****************************************************************************/
417 * get_sortgroupref_clause
418 * Find the SortGroupClause matching the given SortGroupRef index,
434 elog(
ERROR,
"ORDER/GROUP BY expression not found in list");
435 return NULL;
/* keep compiler quiet */
439 * get_sortgroupref_clause_noerr
440 * As above, but return NULL rather than throwing an error if not found.
459 * extract_grouping_ops - make an array of the equality operator OIDs
460 * for a SortGroupClause list
472 foreach(glitem, groupClause)
476 groupOperators[colno] = groupcl->
eqop;
481 return groupOperators;
485 * extract_grouping_collations - make an array of the grouping column collations
486 * for a SortGroupClause list
498 foreach(glitem, groupClause)
506 return grpCollations;
510 * extract_grouping_cols - make an array of the grouping column resnos
511 * for a SortGroupClause list
523 foreach(glitem, groupClause)
528 grpColIdx[colno++] = tle->
resno;
535 * grouping_is_sortable - is it possible to implement grouping list by sorting?
537 * This is easy since the parser will have included a sortop if one exists.
544 foreach(glitem, groupClause)
555 * grouping_is_hashable - is it possible to implement grouping list by hashing?
557 * We rely on the parser to have set the hashable flag correctly.
564 foreach(glitem, groupClause)
568 if (!groupcl->hashable)
575/*****************************************************************************
576 * PathTarget manipulation functions
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 *****************************************************************************/
584 * make_pathtarget_from_tlist
585 * Construct a PathTarget equivalent to the given targetlist.
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.
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.
620 * make_tlist_from_pathtarget
621 * Construct a targetlist from a PathTarget.
631 foreach(lc, target->
exprs)
640 if (target->sortgrouprefs)
653 * The new PathTarget has its own exprs List, but shares the underlying
654 * target expression trees with the old one.
661 /* Copy scalar fields */
663 /* Shallow-copy the expression list */
665 /* Duplicate sortgrouprefs if any (if not, the memcpy handled this) */
666 if (src->sortgrouprefs)
671 memcpy(dst->sortgrouprefs, src->sortgrouprefs, nbytes);
677 * create_empty_pathtarget
678 * Create an empty (zero columns, zero cost) PathTarget.
683 /* This is easy, but we don't want callers to hard-wire this ... */
688 * add_column_to_pathtarget
689 * Append a target column to the PathTarget.
691 * As with make_pathtarget_from_tlist, we leave it to the caller to update
692 * the cost and width fields.
697 /* Updating the exprs list is easy ... */
699 /* ... the sortgroupref data, a bit less so */
700 if (target->sortgrouprefs)
704 /* This might look inefficient, but actually it's usually cheap */
705 target->sortgrouprefs = (
Index *)
707 target->sortgrouprefs[nexprs - 1] = sortgroupref;
709 else if (sortgroupref)
711 /* Adding sortgroupref labeling to a previously unlabeled target */
715 target->sortgrouprefs[nexprs - 1] = sortgroupref;
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.
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.
734 * The caller cannot specify a sortgroupref, since it would be unclear how
735 * to merge that with a pre-existing column.
737 * As with make_pathtarget_from_tlist, we leave it to the caller to update
738 * the cost and width fields.
748 * add_new_columns_to_pathtarget
749 * Apply add_new_column_to_pathtarget() for each element of the list.
765 * apply_pathtarget_labeling_to_tlist
766 * Apply any sortgrouprefs in the PathTarget to matching tlist entries
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.
779 /* Nothing to do if PathTarget has no sortgrouprefs data */
780 if (target->sortgrouprefs == NULL)
784 foreach(lc, target->
exprs)
789 if (target->sortgrouprefs[
i])
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.)
800 if (expr &&
IsA(expr,
Var))
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
812 elog(
ERROR,
"ORDER/GROUP BY expression not found in targetlist");
815 elog(
ERROR,
"targetlist item has multiple sortgroupref labels");
824 * split_pathtarget_at_srfs
825 * Split given PathTarget into multiple levels to position SRFs safely
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.
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
840 * and below that, another PathTarget containing
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
847 * Var1, srf2(Var2 + Var3)
849 * which satisfy the desired property.
852 * srf1(x), srf2(srf3(y))
853 * That must appear as-is in the top PathTarget, but below that we need
855 * That is, each SRF must be computed at a level corresponding to the nesting
856 * depth of SRFs within its arguments.
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.
863 * It's also important that we preserve any sortgroupref annotation appearing
864 * in the given target, especially on expressions matching input_target items.
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.
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.
883 List **targets,
List **targets_contain_srfs)
887 bool need_extra_projection;
888 List *prev_level_tlist;
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.)
901 if (target == input_target)
908 /* Pass any input_target exprs down to split_pathtarget_walker() */
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.)
922 /* Initialize data we'll accumulate across all the target expressions */
926 need_extra_projection =
false;
928 /* Scan each expression in the PathTarget looking for SRFs */
930 foreach(lc, target->
exprs)
934 /* Tell split_pathtarget_walker about this expr's sortgroupref */
939 * Find all SRFs and Vars (and Var-like nodes) in this expression, and
940 * enter them into appropriate lists within the context struct.
945 /* An expression containing no SRFs is of no further interest */
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.
958 need_extra_projection =
false;
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
967 need_extra_projection =
true;
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.
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.
987 if (need_extra_projection)
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.
1009 *targets = *targets_contain_srfs =
NIL;
1010 prev_level_tlist =
NIL;
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
1047 foreach(lcx, input_srfs)
1059 * Add current target and does-it-compute-SRFs flag to output lists.
1061 *targets =
lappend(*targets, ntarget);
1062 *targets_contain_srfs =
lappend_int(*targets_contain_srfs,
1063 (level_srfs !=
NIL));
1065 /* Remember this level's output for next pass */
1066 prev_level_tlist = ntarget->
exprs;
1071 * Recursively examine expressions for split_pathtarget_at_srfs.
1073 * Note we make no effort here to prevent duplicate entries in the output
1074 * lists. Duplicates will be gotten rid of later.
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.)
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).
1122 * If it's a SRF, recursively examine its inputs, determine its level, and
1123 * make appropriate entries in the output lists.
1140 context->
current_sgref = 0;
/* subexpressions are not sortgroup items */
1144 /* Depth is one more than any SRF below it */
1147 /* If new record depth, initialize another level of output lists */
1155 /* Record this SRF as needing to be evaluated at appropriate level */
1159 /* Record its inputs as being needed at the same level */
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.
1174 /* We're done here */
1179 * Otherwise, the node is a scalar (non-set) expression, so recurse to
1180 * examine its inputs.
1182 context->
current_sgref = 0;
/* subexpressions are not sortgroup items */
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
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.
1206 * Look for a pre-existing entry that is equal() and does not have a
1207 * conflicting sortgroupref already.
1210 foreach(lc, target->
exprs)
1220 /* Found a match. Assign item's sortgroupref if it has one. */
1223 if (target->sortgrouprefs == NULL)
1225 target->sortgrouprefs = (
Index *)
1236 * No match, so add item to PathTarget. Copy the expr for safety.
1243 * Apply add_sp_item_to_pathtarget to each element of list.
#define OidIsValid(objectId)
PathTarget * set_pathtarget_cost_width(PlannerInfo *root, PathTarget *target)
bool equal(const void *a, const void *b)
Assert(PointerIsAligned(start, uint64))
if(TABLE==NULL||TABLE_index==NULL)
List * lappend(List *list, void *datum)
List * list_concat(List *list1, const List *list2)
List * list_copy(const List *oldlist)
List * lappend_int(List *list, int datum)
bool list_member(const List *list, const void *datum)
TargetEntry * makeTargetEntry(Expr *expr, AttrNumber resno, char *resname, bool resjunk)
void * repalloc(void *pointer, Size size)
void * palloc0(Size size)
Oid exprType(const Node *expr)
Oid exprCollation(const Node *expr)
#define expression_tree_walker(n, w, c)
#define IsA(nodeptr, _type_)
#define get_pathtarget_sortgroupref(target, colno)
static int list_length(const List *l)
#define forboth(cell1, list1, cell2, list2)
#define forthree(cell1, list1, cell2, list2, cell3, list3)
#define for_each_cell(cell, lst, initcell)
static ListCell * list_nth_cell(const List *list, int n)
static ListCell * list_head(const List *l)
static ListCell * lnext(const List *l, const ListCell *c)
#define list_make1_int(x1)
VolatileFunctionStatus has_volatile_expr
List * current_input_srfs
List * input_target_exprs
List * current_input_vars
bool tlist_same_collations(List *tlist, List *colCollations, bool junkOK)
Oid * extract_grouping_ops(List *groupClause)
TargetEntry * tlist_member(Expr *node, List *targetlist)
bool tlist_same_exprs(List *tlist1, List *tlist2)
void apply_tlist_labeling(List *dest_tlist, List *src_tlist)
SortGroupClause * get_sortgroupref_clause_noerr(Index sortref, List *clauses)
SortGroupClause * get_sortgroupref_clause(Index sortref, List *clauses)
void apply_pathtarget_labeling_to_tlist(List *tlist, PathTarget *target)
#define IS_SRF_CALL(node)
bool grouping_is_sortable(List *groupClause)
PathTarget * make_pathtarget_from_tlist(List *tlist)
List * make_tlist_from_pathtarget(PathTarget *target)
PathTarget * copy_pathtarget(PathTarget *src)
static void add_sp_item_to_pathtarget(PathTarget *target, split_pathtarget_item *item)
static bool split_pathtarget_walker(Node *node, split_pathtarget_context *context)
AttrNumber * extract_grouping_cols(List *groupClause, List *tlist)
TargetEntry * get_sortgroupclause_tle(SortGroupClause *sgClause, List *targetList)
void add_new_columns_to_pathtarget(PathTarget *target, List *exprs)
static void add_sp_items_to_pathtarget(PathTarget *target, List *items)
PathTarget * create_empty_pathtarget(void)
List * get_sortgrouplist_exprs(List *sgClauses, List *targetList)
TargetEntry * get_sortgroupref_tle(Index sortref, List *targetList)
List * add_to_flat_tlist(List *tlist, List *exprs)
int count_nonjunk_tlist_entries(List *tlist)
List * get_tlist_exprs(List *tlist, bool includeJunk)
void add_new_column_to_pathtarget(PathTarget *target, Expr *expr)
void split_pathtarget_at_srfs(PlannerInfo *root, PathTarget *target, PathTarget *input_target, List **targets, List **targets_contain_srfs)
bool grouping_is_hashable(List *groupClause)
Oid * extract_grouping_collations(List *groupClause, List *tlist)
static TargetEntry * tlist_member_match_var(Var *var, List *targetlist)
void add_column_to_pathtarget(PathTarget *target, Expr *expr, Index sortgroupref)
Node * get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
bool tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK)