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