← Back to branch summary

~ubuntu-branches/ubuntu/natty/postgresql-8.4/natty-updates

« back to all changes in this revision

Viewing changes to src/backend/optimizer/util/tlist.c

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2009-03-20 12:00:13 UTC
  • Revision ID: james.westby@ubuntu.com-20090320120013-hogj7egc5mjncc5g
Tags: upstream-8.4~0cvs20090328
Import upstream version 8.4~0cvs20090328

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/optimizer/util/tlist.c
 
1
/*-------------------------------------------------------------------------
 
2
 *
 
3
 * tlist.c
 
4
 *        Target list manipulation routines
 
5
 *
 
6
 * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
 
7
 * Portions Copyright (c) 1994, Regents of the University of California
 
8
 *
 
9
 *
 
10
 * IDENTIFICATION
 
11
 *        $PostgreSQL$
 
12
 *
 
13
 *-------------------------------------------------------------------------
 
14
 */
 
15
#include "postgres.h"
 
16
 
 
17
#include "nodes/makefuncs.h"
 
18
#include "nodes/nodeFuncs.h"
 
19
#include "optimizer/tlist.h"
 
20
#include "optimizer/var.h"
 
21
#include "utils/lsyscache.h"
 
22
 
 
23
 
 
24
/*****************************************************************************
 
25
 *              Target list creation and searching utilities
 
26
 *****************************************************************************/
 
27
 
 
28
/*
 
29
 * tlist_member
 
30
 *        Finds the (first) member of the given tlist whose expression is
 
31
 *        equal() to the given expression.      Result is NULL if no such member.
 
32
 */
 
33
TargetEntry *
 
34
tlist_member(Node *node, List *targetlist)
 
35
{
 
36
        ListCell   *temp;
 
37
 
 
38
        foreach(temp, targetlist)
 
39
        {
 
40
                TargetEntry *tlentry = (TargetEntry *) lfirst(temp);
 
41
 
 
42
                if (equal(node, tlentry->expr))
 
43
                        return tlentry;
 
44
        }
 
45
        return NULL;
 
46
}
 
47
 
 
48
/*
 
49
 * tlist_member_ignore_relabel
 
50
 *        Same as above, except that we ignore top-level RelabelType nodes
 
51
 *        while checking for a match.  This is needed for some scenarios
 
52
 *        involving binary-compatible sort operations.
 
53
 */
 
54
TargetEntry *
 
55
tlist_member_ignore_relabel(Node *node, List *targetlist)
 
56
{
 
57
        ListCell   *temp;
 
58
 
 
59
        while (node && IsA(node, RelabelType))
 
60
                node = (Node *) ((RelabelType *) node)->arg;
 
61
 
 
62
        foreach(temp, targetlist)
 
63
        {
 
64
                TargetEntry *tlentry = (TargetEntry *) lfirst(temp);
 
65
                Expr       *tlexpr = tlentry->expr;
 
66
 
 
67
                while (tlexpr && IsA(tlexpr, RelabelType))
 
68
                        tlexpr = ((RelabelType *) tlexpr)->arg;
 
69
 
 
70
                if (equal(node, tlexpr))
 
71
                        return tlentry;
 
72
        }
 
73
        return NULL;
 
74
}
 
75
 
 
76
/*
 
77
 * flatten_tlist
 
78
 *        Create a target list that only contains unique variables.
 
79
 *
 
80
 * Note that Vars with varlevelsup > 0 are not included in the output
 
81
 * tlist.  We expect that those will eventually be replaced with Params,
 
82
 * but that probably has not happened at the time this routine is called.
 
83
 *
 
84
 * 'tlist' is the current target list
 
85
 *
 
86
 * Returns the "flattened" new target list.
 
87
 *
 
88
 * The result is entirely new structure sharing no nodes with the original.
 
89
 * Copying the Var nodes is probably overkill, but be safe for now.
 
90
 */
 
91
List *
 
92
flatten_tlist(List *tlist)
 
93
{
 
94
        List       *vlist = pull_var_clause((Node *) tlist, true);
 
95
        List       *new_tlist;
 
96
 
 
97
        new_tlist = add_to_flat_tlist(NIL, vlist);
 
98
        list_free(vlist);
 
99
        return new_tlist;
 
100
}
 
101
 
 
102
/*
 
103
 * add_to_flat_tlist
 
104
 *              Add more items to a flattened tlist (if they're not already in it)
 
105
 *
 
106
 * 'tlist' is the flattened tlist
 
107
 * 'exprs' is a list of expressions (usually, but not necessarily, Vars)
 
108
 *
 
109
 * Returns the extended tlist.
 
110
 */
 
111
List *
 
112
add_to_flat_tlist(List *tlist, List *exprs)
 
113
{
 
114
        int                     next_resno = list_length(tlist) + 1;
 
115
        ListCell   *lc;
 
116
 
 
117
        foreach(lc, exprs)
 
118
        {
 
119
                Node       *expr = (Node *) lfirst(lc);
 
120
 
 
121
                if (!tlist_member(expr, tlist))
 
122
                {
 
123
                        TargetEntry *tle;
 
124
 
 
125
                        tle = makeTargetEntry(copyObject(expr),         /* copy needed?? */
 
126
                                                                  next_resno++,
 
127
                                                                  NULL,
 
128
                                                                  false);
 
129
                        tlist = lappend(tlist, tle);
 
130
                }
 
131
        }
 
132
        return tlist;
 
133
}
 
134
 
 
135
 
 
136
/*
 
137
 * get_tlist_exprs
 
138
 *              Get just the expression subtrees of a tlist
 
139
 *
 
140
 * Resjunk columns are ignored unless includeJunk is true
 
141
 */
 
142
List *
 
143
get_tlist_exprs(List *tlist, bool includeJunk)
 
144
{
 
145
        List       *result = NIL;
 
146
        ListCell   *l;
 
147
 
 
148
        foreach(l, tlist)
 
149
        {
 
150
                TargetEntry *tle = (TargetEntry *) lfirst(l);
 
151
 
 
152
                if (tle->resjunk && !includeJunk)
 
153
                        continue;
 
154
 
 
155
                result = lappend(result, tle->expr);
 
156
        }
 
157
        return result;
 
158
}
 
159
 
 
160
 
 
161
/*
 
162
 * Does tlist have same output datatypes as listed in colTypes?
 
163
 *
 
164
 * Resjunk columns are ignored if junkOK is true; otherwise presence of
 
165
 * a resjunk column will always cause a 'false' result.
 
166
 *
 
167
 * Note: currently no callers care about comparing typmods.
 
168
 */
 
169
bool
 
170
tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK)
 
171
{
 
172
        ListCell   *l;
 
173
        ListCell   *curColType = list_head(colTypes);
 
174
 
 
175
        foreach(l, tlist)
 
176
        {
 
177
                TargetEntry *tle = (TargetEntry *) lfirst(l);
 
178
 
 
179
                if (tle->resjunk)
 
180
                {
 
181
                        if (!junkOK)
 
182
                                return false;
 
183
                }
 
184
                else
 
185
                {
 
186
                        if (curColType == NULL)
 
187
                                return false;   /* tlist longer than colTypes */
 
188
                        if (exprType((Node *) tle->expr) != lfirst_oid(curColType))
 
189
                                return false;
 
190
                        curColType = lnext(curColType);
 
191
                }
 
192
        }
 
193
        if (curColType != NULL)
 
194
                return false;                   /* tlist shorter than colTypes */
 
195
        return true;
 
196
}
 
197
 
 
198
 
 
199
/*
 
200
 * get_sortgroupref_tle
 
201
 *              Find the targetlist entry matching the given SortGroupRef index,
 
202
 *              and return it.
 
203
 */
 
204
TargetEntry *
 
205
get_sortgroupref_tle(Index sortref, List *targetList)
 
206
{
 
207
        ListCell   *l;
 
208
 
 
209
        foreach(l, targetList)
 
210
        {
 
211
                TargetEntry *tle = (TargetEntry *) lfirst(l);
 
212
 
 
213
                if (tle->ressortgroupref == sortref)
 
214
                        return tle;
 
215
        }
 
216
 
 
217
        elog(ERROR, "ORDER/GROUP BY expression not found in targetlist");
 
218
        return NULL;                            /* keep compiler quiet */
 
219
}
 
220
 
 
221
/*
 
222
 * get_sortgroupclause_tle
 
223
 *              Find the targetlist entry matching the given SortGroupClause
 
224
 *              by ressortgroupref, and return it.
 
225
 */
 
226
TargetEntry *
 
227
get_sortgroupclause_tle(SortGroupClause *sgClause,
 
228
                                                List *targetList)
 
229
{
 
230
        return get_sortgroupref_tle(sgClause->tleSortGroupRef, targetList);
 
231
}
 
232
 
 
233
/*
 
234
 * get_sortgroupclause_expr
 
235
 *              Find the targetlist entry matching the given SortGroupClause
 
236
 *              by ressortgroupref, and return its expression.
 
237
 */
 
238
Node *
 
239
get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList)
 
240
{
 
241
        TargetEntry *tle = get_sortgroupclause_tle(sgClause, targetList);
 
242
 
 
243
        return (Node *) tle->expr;
 
244
}
 
245
 
 
246
/*
 
247
 * get_sortgrouplist_exprs
 
248
 *              Given a list of SortGroupClauses, build a list
 
249
 *              of the referenced targetlist expressions.
 
250
 */
 
251
List *
 
252
get_sortgrouplist_exprs(List *sgClauses, List *targetList)
 
253
{
 
254
        List       *result = NIL;
 
255
        ListCell   *l;
 
256
 
 
257
        foreach(l, sgClauses)
 
258
        {
 
259
                SortGroupClause *sortcl = (SortGroupClause *) lfirst(l);
 
260
                Node       *sortexpr;
 
261
 
 
262
                sortexpr = get_sortgroupclause_expr(sortcl, targetList);
 
263
                result = lappend(result, sortexpr);
 
264
        }
 
265
        return result;
 
266
}
 
267
 
 
268
 
 
269
/*****************************************************************************
 
270
 *              Functions to extract data from a list of SortGroupClauses
 
271
 *
 
272
 * These don't really belong in tlist.c, but they are sort of related to the
 
273
 * functions just above, and they don't seem to deserve their own file.
 
274
 *****************************************************************************/
 
275
 
 
276
/*
 
277
 * extract_grouping_ops - make an array of the equality operator OIDs
 
278
 *              for a SortGroupClause list
 
279
 */
 
280
Oid *
 
281
extract_grouping_ops(List *groupClause)
 
282
{
 
283
        int                     numCols = list_length(groupClause);
 
284
        int                     colno = 0;
 
285
        Oid                *groupOperators;
 
286
        ListCell   *glitem;
 
287
 
 
288
        groupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
 
289
 
 
290
        foreach(glitem, groupClause)
 
291
        {
 
292
                SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
 
293
 
 
294
                groupOperators[colno] = groupcl->eqop;
 
295
                Assert(OidIsValid(groupOperators[colno]));
 
296
                colno++;
 
297
        }
 
298
 
 
299
        return groupOperators;
 
300
}
 
301
 
 
302
/*
 
303
 * extract_grouping_cols - make an array of the grouping column resnos
 
304
 *              for a SortGroupClause list
 
305
 */
 
306
AttrNumber *
 
307
extract_grouping_cols(List *groupClause, List *tlist)
 
308
{
 
309
        AttrNumber *grpColIdx;
 
310
        int                     numCols = list_length(groupClause);
 
311
        int                     colno = 0;
 
312
        ListCell   *glitem;
 
313
 
 
314
        grpColIdx = (AttrNumber *) palloc(sizeof(AttrNumber) * numCols);
 
315
 
 
316
        foreach(glitem, groupClause)
 
317
        {
 
318
                SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
 
319
                TargetEntry *tle = get_sortgroupclause_tle(groupcl, tlist);
 
320
 
 
321
                grpColIdx[colno++] = tle->resno;
 
322
        }
 
323
 
 
324
        return grpColIdx;
 
325
}
 
326
 
 
327
/*
 
328
 * grouping_is_sortable - is it possible to implement grouping list by sorting?
 
329
 *
 
330
 * This is easy since the parser will have included a sortop if one exists.
 
331
 */
 
332
bool
 
333
grouping_is_sortable(List *groupClause)
 
334
{
 
335
        ListCell   *glitem;
 
336
 
 
337
        foreach(glitem, groupClause)
 
338
        {
 
339
                SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
 
340
 
 
341
                if (!OidIsValid(groupcl->sortop))
 
342
                        return false;
 
343
        }
 
344
        return true;
 
345
}
 
346
 
 
347
/*
 
348
 * grouping_is_hashable - is it possible to implement grouping list by hashing?
 
349
 *
 
350
 * We assume hashing is OK if the equality operators are marked oprcanhash.
 
351
 * (If there isn't actually a supporting hash function, the executor will
 
352
 * complain at runtime; but this is a misdeclaration of the operator, not
 
353
 * a system bug.)
 
354
 */
 
355
bool
 
356
grouping_is_hashable(List *groupClause)
 
357
{
 
358
        ListCell   *glitem;
 
359
 
 
360
        foreach(glitem, groupClause)
 
361
        {
 
362
                SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
 
363
 
 
364
                if (!op_hashjoinable(groupcl->eqop))
 
365
                        return false;
 
366
        }
 
367
        return true;
 
368
}