← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/postgresql-9.1/oneiric-security

« back to all changes in this revision

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

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2011-05-11 10:41:53 UTC
  • Revision ID: james.westby@ubuntu.com-20110511104153-psbh2o58553fv1m0
Tags: upstream-9.1~beta1
Import upstream version 9.1~beta1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/optimizer/util/placeholder.c
 
1
/*-------------------------------------------------------------------------
 
2
 *
 
3
 * placeholder.c
 
4
 *        PlaceHolderVar and PlaceHolderInfo manipulation routines
 
5
 *
 
6
 *
 
7
 * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
 
8
 * Portions Copyright (c) 1994, Regents of the University of California
 
9
 *
 
10
 *
 
11
 * IDENTIFICATION
 
12
 *        src/backend/optimizer/util/placeholder.c
 
13
 *
 
14
 *-------------------------------------------------------------------------
 
15
 */
 
16
#include "postgres.h"
 
17
 
 
18
#include "nodes/nodeFuncs.h"
 
19
#include "optimizer/pathnode.h"
 
20
#include "optimizer/placeholder.h"
 
21
#include "optimizer/planmain.h"
 
22
#include "optimizer/var.h"
 
23
#include "utils/lsyscache.h"
 
24
 
 
25
/* Local functions */
 
26
static Relids find_placeholders_recurse(PlannerInfo *root, Node *jtnode);
 
27
static void find_placeholders_in_qual(PlannerInfo *root, Node *qual,
 
28
                                                  Relids relids);
 
29
 
 
30
 
 
31
/*
 
32
 * make_placeholder_expr
 
33
 *              Make a PlaceHolderVar for the given expression.
 
34
 *
 
35
 * phrels is the syntactic location (as a set of baserels) to attribute
 
36
 * to the expression.
 
37
 */
 
38
PlaceHolderVar *
 
39
make_placeholder_expr(PlannerInfo *root, Expr *expr, Relids phrels)
 
40
{
 
41
        PlaceHolderVar *phv = makeNode(PlaceHolderVar);
 
42
 
 
43
        phv->phexpr = expr;
 
44
        phv->phrels = phrels;
 
45
        phv->phid = ++(root->glob->lastPHId);
 
46
        phv->phlevelsup = 0;
 
47
 
 
48
        return phv;
 
49
}
 
50
 
 
51
/*
 
52
 * find_placeholder_info
 
53
 *              Fetch the PlaceHolderInfo for the given PHV; create it if not found
 
54
 *
 
55
 * This is separate from make_placeholder_expr because subquery pullup has
 
56
 * to make PlaceHolderVars for expressions that might not be used at all in
 
57
 * the upper query, or might not remain after const-expression simplification.
 
58
 * We build PlaceHolderInfos only for PHVs that are still present in the
 
59
 * simplified query passed to query_planner().
 
60
 *
 
61
 * Note: this should only be called after query_planner() has started.
 
62
 */
 
63
PlaceHolderInfo *
 
64
find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv)
 
65
{
 
66
        PlaceHolderInfo *phinfo;
 
67
        ListCell   *lc;
 
68
 
 
69
        /* if this ever isn't true, we'd need to be able to look in parent lists */
 
70
        Assert(phv->phlevelsup == 0);
 
71
 
 
72
        foreach(lc, root->placeholder_list)
 
73
        {
 
74
                phinfo = (PlaceHolderInfo *) lfirst(lc);
 
75
                if (phinfo->phid == phv->phid)
 
76
                        return phinfo;
 
77
        }
 
78
 
 
79
        /* Not found, so create it */
 
80
        phinfo = makeNode(PlaceHolderInfo);
 
81
 
 
82
        phinfo->phid = phv->phid;
 
83
        phinfo->ph_var = copyObject(phv);
 
84
        phinfo->ph_eval_at = pull_varnos((Node *) phv);
 
85
        /* ph_eval_at may change later, see update_placeholder_eval_levels */
 
86
        phinfo->ph_needed = NULL;       /* initially it's unused */
 
87
        phinfo->ph_may_need = NULL;
 
88
        /* for the moment, estimate width using just the datatype info */
 
89
        phinfo->ph_width = get_typavgwidth(exprType((Node *) phv->phexpr),
 
90
                                                                           exprTypmod((Node *) phv->phexpr));
 
91
 
 
92
        root->placeholder_list = lappend(root->placeholder_list, phinfo);
 
93
 
 
94
        return phinfo;
 
95
}
 
96
 
 
97
/*
 
98
 * find_placeholders_in_jointree
 
99
 *              Search the jointree for PlaceHolderVars, and build PlaceHolderInfos
 
100
 *
 
101
 * We don't need to look at the targetlist because build_base_rel_tlists()
 
102
 * will already have made entries for any PHVs in the tlist.
 
103
 */
 
104
void
 
105
find_placeholders_in_jointree(PlannerInfo *root)
 
106
{
 
107
        /* We need do nothing if the query contains no PlaceHolderVars */
 
108
        if (root->glob->lastPHId != 0)
 
109
        {
 
110
                /* Start recursion at top of jointree */
 
111
                Assert(root->parse->jointree != NULL &&
 
112
                           IsA(root->parse->jointree, FromExpr));
 
113
                (void) find_placeholders_recurse(root, (Node *) root->parse->jointree);
 
114
        }
 
115
}
 
116
 
 
117
/*
 
118
 * find_placeholders_recurse
 
119
 *        One recursion level of find_placeholders_in_jointree.
 
120
 *
 
121
 * jtnode is the current jointree node to examine.
 
122
 *
 
123
 * The result is the set of base Relids contained in or below jtnode.
 
124
 * This is just an internal convenience, it's not used at the top level.
 
125
 */
 
126
static Relids
 
127
find_placeholders_recurse(PlannerInfo *root, Node *jtnode)
 
128
{
 
129
        Relids          jtrelids;
 
130
 
 
131
        if (jtnode == NULL)
 
132
                return NULL;
 
133
        if (IsA(jtnode, RangeTblRef))
 
134
        {
 
135
                int                     varno = ((RangeTblRef *) jtnode)->rtindex;
 
136
 
 
137
                /* No quals to deal with, just return correct result */
 
138
                jtrelids = bms_make_singleton(varno);
 
139
        }
 
140
        else if (IsA(jtnode, FromExpr))
 
141
        {
 
142
                FromExpr   *f = (FromExpr *) jtnode;
 
143
                ListCell   *l;
 
144
 
 
145
                /*
 
146
                 * First, recurse to handle child joins, and form their relid set.
 
147
                 */
 
148
                jtrelids = NULL;
 
149
                foreach(l, f->fromlist)
 
150
                {
 
151
                        Relids          sub_relids;
 
152
 
 
153
                        sub_relids = find_placeholders_recurse(root, lfirst(l));
 
154
                        jtrelids = bms_join(jtrelids, sub_relids);
 
155
                }
 
156
 
 
157
                /*
 
158
                 * Now process the top-level quals.
 
159
                 */
 
160
                find_placeholders_in_qual(root, f->quals, jtrelids);
 
161
        }
 
162
        else if (IsA(jtnode, JoinExpr))
 
163
        {
 
164
                JoinExpr   *j = (JoinExpr *) jtnode;
 
165
                Relids          leftids,
 
166
                                        rightids;
 
167
 
 
168
                /*
 
169
                 * First, recurse to handle child joins, and form their relid set.
 
170
                 */
 
171
                leftids = find_placeholders_recurse(root, j->larg);
 
172
                rightids = find_placeholders_recurse(root, j->rarg);
 
173
                jtrelids = bms_join(leftids, rightids);
 
174
 
 
175
                /* Process the qual clauses */
 
176
                find_placeholders_in_qual(root, j->quals, jtrelids);
 
177
        }
 
178
        else
 
179
        {
 
180
                elog(ERROR, "unrecognized node type: %d",
 
181
                         (int) nodeTag(jtnode));
 
182
                jtrelids = NULL;                /* keep compiler quiet */
 
183
        }
 
184
        return jtrelids;
 
185
}
 
186
 
 
187
/*
 
188
 * find_placeholders_in_qual
 
189
 *              Process a qual clause for find_placeholders_in_jointree.
 
190
 *
 
191
 * relids is the syntactic join level to mark as the "maybe needed" level
 
192
 * for each PlaceHolderVar found in the qual clause.
 
193
 */
 
194
static void
 
195
find_placeholders_in_qual(PlannerInfo *root, Node *qual, Relids relids)
 
196
{
 
197
        List       *vars;
 
198
        ListCell   *vl;
 
199
 
 
200
        /*
 
201
         * pull_var_clause does more than we need here, but it'll do and it's
 
202
         * convenient to use.
 
203
         */
 
204
        vars = pull_var_clause(qual, PVC_INCLUDE_PLACEHOLDERS);
 
205
        foreach(vl, vars)
 
206
        {
 
207
                PlaceHolderVar *phv = (PlaceHolderVar *) lfirst(vl);
 
208
                PlaceHolderInfo *phinfo;
 
209
 
 
210
                /* Ignore any plain Vars */
 
211
                if (!IsA(phv, PlaceHolderVar))
 
212
                        continue;
 
213
 
 
214
                /* Create a PlaceHolderInfo entry if there's not one already */
 
215
                phinfo = find_placeholder_info(root, phv);
 
216
 
 
217
                /* Mark the PHV as possibly needed at the qual's syntactic level */
 
218
                phinfo->ph_may_need = bms_add_members(phinfo->ph_may_need, relids);
 
219
 
 
220
                /*
 
221
                 * This is a bit tricky: the PHV's contained expression may contain
 
222
                 * other, lower-level PHVs.  We need to get those into the
 
223
                 * PlaceHolderInfo list, but they aren't going to be needed where the
 
224
                 * outer PHV is referenced.  Rather, they'll be needed where the outer
 
225
                 * PHV is evaluated.  We can estimate that (conservatively) as the
 
226
                 * syntactic location of the PHV's expression.  Recurse to take care
 
227
                 * of any such PHVs.
 
228
                 */
 
229
                find_placeholders_in_qual(root, (Node *) phv->phexpr, phv->phrels);
 
230
        }
 
231
        list_free(vars);
 
232
}
 
233
 
 
234
/*
 
235
 * update_placeholder_eval_levels
 
236
 *              Adjust the target evaluation levels for placeholders
 
237
 *
 
238
 * The initial eval_at level set by find_placeholder_info was the set of
 
239
 * rels used in the placeholder's expression (or the whole subselect below
 
240
 * the placeholder's syntactic location, if the expr is variable-free).
 
241
 * If the subselect contains any outer joins that can null any of those rels,
 
242
 * we must delay evaluation to above those joins.
 
243
 *
 
244
 * We repeat this operation each time we add another outer join to
 
245
 * root->join_info_list.  It's somewhat annoying to have to do that, but
 
246
 * since we don't have very much information on the placeholders' locations,
 
247
 * it's hard to avoid.  Each placeholder's eval_at level must be correct
 
248
 * by the time it starts to figure in outer-join delay decisions for higher
 
249
 * outer joins.
 
250
 *
 
251
 * In future we might want to put additional policy/heuristics here to
 
252
 * try to determine an optimal evaluation level.  The current rules will
 
253
 * result in evaluation at the lowest possible level.  However, pushing a
 
254
 * placeholder eval up the tree is likely to further constrain evaluation
 
255
 * order for outer joins, so it could easily be counterproductive; and we
 
256
 * don't have enough information at this point to make an intelligent choice.
 
257
 */
 
258
void
 
259
update_placeholder_eval_levels(PlannerInfo *root, SpecialJoinInfo *new_sjinfo)
 
260
{
 
261
        ListCell   *lc1;
 
262
 
 
263
        foreach(lc1, root->placeholder_list)
 
264
        {
 
265
                PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc1);
 
266
                Relids          syn_level = phinfo->ph_var->phrels;
 
267
                Relids          eval_at;
 
268
                bool            found_some;
 
269
                ListCell   *lc2;
 
270
 
 
271
                /*
 
272
                 * We don't need to do any work on this placeholder unless the
 
273
                 * newly-added outer join is syntactically beneath its location.
 
274
                 */
 
275
                if (!bms_is_subset(new_sjinfo->syn_lefthand, syn_level) ||
 
276
                        !bms_is_subset(new_sjinfo->syn_righthand, syn_level))
 
277
                        continue;
 
278
 
 
279
                /*
 
280
                 * Check for delays due to lower outer joins.  This is the same logic
 
281
                 * as in check_outerjoin_delay in initsplan.c, except that we don't
 
282
                 * have anything to do with the delay_upper_joins flags; delay of
 
283
                 * upper outer joins will be handled later, based on the eval_at
 
284
                 * values we compute now.
 
285
                 */
 
286
                eval_at = phinfo->ph_eval_at;
 
287
 
 
288
                do
 
289
                {
 
290
                        found_some = false;
 
291
                        foreach(lc2, root->join_info_list)
 
292
                        {
 
293
                                SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc2);
 
294
 
 
295
                                /* disregard joins not within the PHV's sub-select */
 
296
                                if (!bms_is_subset(sjinfo->syn_lefthand, syn_level) ||
 
297
                                        !bms_is_subset(sjinfo->syn_righthand, syn_level))
 
298
                                        continue;
 
299
 
 
300
                                /* do we reference any nullable rels of this OJ? */
 
301
                                if (bms_overlap(eval_at, sjinfo->min_righthand) ||
 
302
                                        (sjinfo->jointype == JOIN_FULL &&
 
303
                                         bms_overlap(eval_at, sjinfo->min_lefthand)))
 
304
                                {
 
305
                                        /* yes; have we included all its rels in eval_at? */
 
306
                                        if (!bms_is_subset(sjinfo->min_lefthand, eval_at) ||
 
307
                                                !bms_is_subset(sjinfo->min_righthand, eval_at))
 
308
                                        {
 
309
                                                /* no, so add them in */
 
310
                                                eval_at = bms_add_members(eval_at,
 
311
                                                                                                  sjinfo->min_lefthand);
 
312
                                                eval_at = bms_add_members(eval_at,
 
313
                                                                                                  sjinfo->min_righthand);
 
314
                                                /* we'll need another iteration */
 
315
                                                found_some = true;
 
316
                                        }
 
317
                                }
 
318
                        }
 
319
                } while (found_some);
 
320
 
 
321
                phinfo->ph_eval_at = eval_at;
 
322
        }
 
323
}
 
324
 
 
325
/*
 
326
 * fix_placeholder_input_needed_levels
 
327
 *              Adjust the "needed at" levels for placeholder inputs
 
328
 *
 
329
 * This is called after we've finished determining the eval_at levels for
 
330
 * all placeholders.  We need to make sure that all vars and placeholders
 
331
 * needed to evaluate each placeholder will be available at the join level
 
332
 * where the evaluation will be done.  Note that this loop can have
 
333
 * side-effects on the ph_needed sets of other PlaceHolderInfos; that's okay
 
334
 * because we don't examine ph_needed here, so there are no ordering issues
 
335
 * to worry about.
 
336
 */
 
337
void
 
338
fix_placeholder_input_needed_levels(PlannerInfo *root)
 
339
{
 
340
        ListCell   *lc;
 
341
 
 
342
        foreach(lc, root->placeholder_list)
 
343
        {
 
344
                PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
 
345
                Relids          eval_at = phinfo->ph_eval_at;
 
346
 
 
347
                /* No work unless it'll be evaluated above baserel level */
 
348
                if (bms_membership(eval_at) == BMS_MULTIPLE)
 
349
                {
 
350
                        List       *vars = pull_var_clause((Node *) phinfo->ph_var->phexpr,
 
351
                                                                                           PVC_INCLUDE_PLACEHOLDERS);
 
352
 
 
353
                        add_vars_to_targetlist(root, vars, eval_at);
 
354
                        list_free(vars);
 
355
                }
 
356
        }
 
357
}
 
358
 
 
359
/*
 
360
 * add_placeholders_to_base_rels
 
361
 *              Add any required PlaceHolderVars to base rels' targetlists.
 
362
 *
 
363
 * If any placeholder can be computed at a base rel and is needed above it,
 
364
 * add it to that rel's targetlist.  This might look like it could be merged
 
365
 * with fix_placeholder_input_needed_levels, but it must be separate because
 
366
 * join removal happens in between, and can change the ph_eval_at sets.  There
 
367
 * is essentially the same logic in add_placeholders_to_joinrel, but we can't
 
368
 * do that part until joinrels are formed.
 
369
 */
 
370
void
 
371
add_placeholders_to_base_rels(PlannerInfo *root)
 
372
{
 
373
        ListCell   *lc;
 
374
 
 
375
        foreach(lc, root->placeholder_list)
 
376
        {
 
377
                PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
 
378
                Relids          eval_at = phinfo->ph_eval_at;
 
379
 
 
380
                if (bms_membership(eval_at) == BMS_SINGLETON)
 
381
                {
 
382
                        int                     varno = bms_singleton_member(eval_at);
 
383
                        RelOptInfo *rel = find_base_rel(root, varno);
 
384
 
 
385
                        if (bms_nonempty_difference(phinfo->ph_needed, rel->relids))
 
386
                                rel->reltargetlist = lappend(rel->reltargetlist,
 
387
                                                                                         copyObject(phinfo->ph_var));
 
388
                }
 
389
        }
 
390
}
 
391
 
 
392
/*
 
393
 * add_placeholders_to_joinrel
 
394
 *              Add any required PlaceHolderVars to a join rel's targetlist.
 
395
 *
 
396
 * A join rel should emit a PlaceHolderVar if (a) the PHV is needed above
 
397
 * this join level and (b) the PHV can be computed at or below this level.
 
398
 * At this time we do not need to distinguish whether the PHV will be
 
399
 * computed here or copied up from below.
 
400
 */
 
401
void
 
402
add_placeholders_to_joinrel(PlannerInfo *root, RelOptInfo *joinrel)
 
403
{
 
404
        Relids          relids = joinrel->relids;
 
405
        ListCell   *lc;
 
406
 
 
407
        foreach(lc, root->placeholder_list)
 
408
        {
 
409
                PlaceHolderInfo *phinfo = (PlaceHolderInfo *) lfirst(lc);
 
410
 
 
411
                /* Is it still needed above this joinrel? */
 
412
                if (bms_nonempty_difference(phinfo->ph_needed, relids))
 
413
                {
 
414
                        /* Is it computable here? */
 
415
                        if (bms_is_subset(phinfo->ph_eval_at, relids))
 
416
                        {
 
417
                                /* Yup, add it to the output */
 
418
                                joinrel->reltargetlist = lappend(joinrel->reltargetlist,
 
419
                                                                                                 phinfo->ph_var);
 
420
                                joinrel->width += phinfo->ph_width;
 
421
                        }
 
422
                }
 
423
        }
 
424
}