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