← Back to branch summary

~vcs-imports/mammoth-replicator/trunk

« back to all changes in this revision

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

  • Committer: alvherre
  • Date: 2005-12-16 21:24:52 UTC
  • Revision ID: svn-v4:db760fc0-0f08-0410-9d63-cc6633f64896:trunk:1
Initial import of the REL8_0_3 sources from the Pgsql CVS repository.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/backend/optimizer/util/relnode.c
 
1
/*-------------------------------------------------------------------------
 
2
 *
 
3
 * relnode.c
 
4
 *        Relation-node lookup/construction routines
 
5
 *
 
6
 * Portions Copyright (c) 1996-2005, PostgreSQL Global Development Group
 
7
 * Portions Copyright (c) 1994, Regents of the University of California
 
8
 *
 
9
 *
 
10
 * IDENTIFICATION
 
11
 *        $PostgreSQL: pgsql/src/backend/optimizer/util/relnode.c,v 1.64 2004-12-31 22:00:23 pgsql Exp $
 
12
 *
 
13
 *-------------------------------------------------------------------------
 
14
 */
 
15
#include "postgres.h"
 
16
 
 
17
#include "optimizer/cost.h"
 
18
#include "optimizer/joininfo.h"
 
19
#include "optimizer/pathnode.h"
 
20
#include "optimizer/plancat.h"
 
21
#include "optimizer/restrictinfo.h"
 
22
#include "optimizer/tlist.h"
 
23
#include "parser/parsetree.h"
 
24
 
 
25
 
 
26
static RelOptInfo *make_base_rel(Query *root, int relid);
 
27
static void build_joinrel_tlist(Query *root, RelOptInfo *joinrel);
 
28
static List *build_joinrel_restrictlist(Query *root,
 
29
                                                   RelOptInfo *joinrel,
 
30
                                                   RelOptInfo *outer_rel,
 
31
                                                   RelOptInfo *inner_rel,
 
32
                                                   JoinType jointype);
 
33
static void build_joinrel_joinlist(RelOptInfo *joinrel,
 
34
                                           RelOptInfo *outer_rel,
 
35
                                           RelOptInfo *inner_rel);
 
36
static List *subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
 
37
                                                          List *joininfo_list);
 
38
static void subbuild_joinrel_joinlist(RelOptInfo *joinrel,
 
39
                                                  List *joininfo_list);
 
40
 
 
41
 
 
42
/*
 
43
 * build_base_rel
 
44
 *        Construct a new base relation RelOptInfo, and put it in the query's
 
45
 *        base_rel_list.
 
46
 */
 
47
void
 
48
build_base_rel(Query *root, int relid)
 
49
{
 
50
        ListCell   *l;
 
51
        RelOptInfo *rel;
 
52
 
 
53
        /* Rel should not exist already */
 
54
        foreach(l, root->base_rel_list)
 
55
        {
 
56
                rel = (RelOptInfo *) lfirst(l);
 
57
                if (relid == rel->relid)
 
58
                        elog(ERROR, "rel already exists");
 
59
        }
 
60
 
 
61
        /* It should not exist as an "other" rel, either */
 
62
        foreach(l, root->other_rel_list)
 
63
        {
 
64
                rel = (RelOptInfo *) lfirst(l);
 
65
                if (relid == rel->relid)
 
66
                        elog(ERROR, "rel already exists as \"other\" rel");
 
67
        }
 
68
 
 
69
        /* No existing RelOptInfo for this base rel, so make a new one */
 
70
        rel = make_base_rel(root, relid);
 
71
 
 
72
        /* and add it to the list */
 
73
        root->base_rel_list = lcons(rel, root->base_rel_list);
 
74
}
 
75
 
 
76
/*
 
77
 * build_other_rel
 
78
 *        Returns relation entry corresponding to 'relid', creating a new one
 
79
 *        if necessary.  This is for 'other' relations, which are much like
 
80
 *        base relations except that they live in a different list.
 
81
 */
 
82
RelOptInfo *
 
83
build_other_rel(Query *root, int relid)
 
84
{
 
85
        ListCell   *l;
 
86
        RelOptInfo *rel;
 
87
 
 
88
        /* Already made? */
 
89
        foreach(l, root->other_rel_list)
 
90
        {
 
91
                rel = (RelOptInfo *) lfirst(l);
 
92
                if (relid == rel->relid)
 
93
                        return rel;
 
94
        }
 
95
 
 
96
        /* It should not exist as a base rel */
 
97
        foreach(l, root->base_rel_list)
 
98
        {
 
99
                rel = (RelOptInfo *) lfirst(l);
 
100
                if (relid == rel->relid)
 
101
                        elog(ERROR, "rel already exists as base rel");
 
102
        }
 
103
 
 
104
        /* No existing RelOptInfo for this other rel, so make a new one */
 
105
        rel = make_base_rel(root, relid);
 
106
 
 
107
        /* presently, must be an inheritance child rel */
 
108
        Assert(rel->reloptkind == RELOPT_BASEREL);
 
109
        rel->reloptkind = RELOPT_OTHER_CHILD_REL;
 
110
 
 
111
        /* and add it to the list */
 
112
        root->other_rel_list = lcons(rel, root->other_rel_list);
 
113
 
 
114
        return rel;
 
115
}
 
116
 
 
117
/*
 
118
 * make_base_rel
 
119
 *        Construct a base-relation RelOptInfo for the specified rangetable index.
 
120
 *
 
121
 * Common code for build_base_rel and build_other_rel.
 
122
 */
 
123
static RelOptInfo *
 
124
make_base_rel(Query *root, int relid)
 
125
{
 
126
        RelOptInfo *rel = makeNode(RelOptInfo);
 
127
        RangeTblEntry *rte = rt_fetch(relid, root->rtable);
 
128
 
 
129
        rel->reloptkind = RELOPT_BASEREL;
 
130
        rel->relids = bms_make_singleton(relid);
 
131
        rel->rows = 0;
 
132
        rel->width = 0;
 
133
        rel->reltargetlist = NIL;
 
134
        rel->pathlist = NIL;
 
135
        rel->cheapest_startup_path = NULL;
 
136
        rel->cheapest_total_path = NULL;
 
137
        rel->cheapest_unique_path = NULL;
 
138
        rel->relid = relid;
 
139
        rel->rtekind = rte->rtekind;
 
140
        /* min_attr, max_attr, attr_needed, attr_widths are set below */
 
141
        rel->indexlist = NIL;
 
142
        rel->pages = 0;
 
143
        rel->tuples = 0;
 
144
        rel->subplan = NULL;
 
145
        rel->baserestrictinfo = NIL;
 
146
        rel->baserestrictcost.startup = 0;
 
147
        rel->baserestrictcost.per_tuple = 0;
 
148
        rel->outerjoinset = NULL;
 
149
        rel->joininfo = NIL;
 
150
        rel->index_outer_relids = NULL;
 
151
        rel->index_inner_paths = NIL;
 
152
 
 
153
        /* Check type of rtable entry */
 
154
        switch (rte->rtekind)
 
155
        {
 
156
                case RTE_RELATION:
 
157
                        /* Table --- retrieve statistics from the system catalogs */
 
158
                        get_relation_info(rte->relid, rel);
 
159
                        break;
 
160
                case RTE_SUBQUERY:
 
161
                case RTE_FUNCTION:
 
162
                        /* Subquery or function --- set up attr range and arrays */
 
163
                        /* Note: 0 is included in range to support whole-row Vars */
 
164
                        rel->min_attr = 0;
 
165
                        rel->max_attr = list_length(rte->eref->colnames);
 
166
                        rel->attr_needed = (Relids *)
 
167
                                palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(Relids));
 
168
                        rel->attr_widths = (int32 *)
 
169
                                palloc0((rel->max_attr - rel->min_attr + 1) * sizeof(int32));
 
170
                        break;
 
171
                default:
 
172
                        elog(ERROR, "unrecognized RTE kind: %d",
 
173
                                 (int) rte->rtekind);
 
174
                        break;
 
175
        }
 
176
 
 
177
        return rel;
 
178
}
 
179
 
 
180
/*
 
181
 * find_base_rel
 
182
 *        Find a base or other relation entry, which must already exist
 
183
 *        (since we'd have no idea which list to add it to).
 
184
 */
 
185
RelOptInfo *
 
186
find_base_rel(Query *root, int relid)
 
187
{
 
188
        ListCell   *l;
 
189
        RelOptInfo *rel;
 
190
 
 
191
        foreach(l, root->base_rel_list)
 
192
        {
 
193
                rel = (RelOptInfo *) lfirst(l);
 
194
                if (relid == rel->relid)
 
195
                        return rel;
 
196
        }
 
197
 
 
198
        foreach(l, root->other_rel_list)
 
199
        {
 
200
                rel = (RelOptInfo *) lfirst(l);
 
201
                if (relid == rel->relid)
 
202
                        return rel;
 
203
        }
 
204
 
 
205
        elog(ERROR, "no relation entry for relid %d", relid);
 
206
 
 
207
        return NULL;                            /* keep compiler quiet */
 
208
}
 
209
 
 
210
/*
 
211
 * find_join_rel
 
212
 *        Returns relation entry corresponding to 'relids' (a set of RT indexes),
 
213
 *        or NULL if none exists.  This is for join relations.
 
214
 */
 
215
RelOptInfo *
 
216
find_join_rel(Query *root, Relids relids)
 
217
{
 
218
        ListCell   *l;
 
219
 
 
220
        foreach(l, root->join_rel_list)
 
221
        {
 
222
                RelOptInfo *rel = (RelOptInfo *) lfirst(l);
 
223
 
 
224
                if (bms_equal(rel->relids, relids))
 
225
                        return rel;
 
226
        }
 
227
 
 
228
        return NULL;
 
229
}
 
230
 
 
231
/*
 
232
 * build_join_rel
 
233
 *        Returns relation entry corresponding to the union of two given rels,
 
234
 *        creating a new relation entry if none already exists.
 
235
 *
 
236
 * 'joinrelids' is the Relids set that uniquely identifies the join
 
237
 * 'outer_rel' and 'inner_rel' are relation nodes for the relations to be
 
238
 *              joined
 
239
 * 'jointype': type of join (inner/outer)
 
240
 * 'restrictlist_ptr': result variable.  If not NULL, *restrictlist_ptr
 
241
 *              receives the list of RestrictInfo nodes that apply to this
 
242
 *              particular pair of joinable relations.
 
243
 *
 
244
 * restrictlist_ptr makes the routine's API a little grotty, but it saves
 
245
 * duplicated calculation of the restrictlist...
 
246
 */
 
247
RelOptInfo *
 
248
build_join_rel(Query *root,
 
249
                           Relids joinrelids,
 
250
                           RelOptInfo *outer_rel,
 
251
                           RelOptInfo *inner_rel,
 
252
                           JoinType jointype,
 
253
                           List **restrictlist_ptr)
 
254
{
 
255
        RelOptInfo *joinrel;
 
256
        List       *restrictlist;
 
257
 
 
258
        /*
 
259
         * See if we already have a joinrel for this set of base rels.
 
260
         */
 
261
        joinrel = find_join_rel(root, joinrelids);
 
262
 
 
263
        if (joinrel)
 
264
        {
 
265
                /*
 
266
                 * Yes, so we only need to figure the restrictlist for this
 
267
                 * particular pair of component relations.
 
268
                 */
 
269
                if (restrictlist_ptr)
 
270
                        *restrictlist_ptr = build_joinrel_restrictlist(root,
 
271
                                                                                                                   joinrel,
 
272
                                                                                                                   outer_rel,
 
273
                                                                                                                   inner_rel,
 
274
                                                                                                                   jointype);
 
275
                return joinrel;
 
276
        }
 
277
 
 
278
        /*
 
279
         * Nope, so make one.
 
280
         */
 
281
        joinrel = makeNode(RelOptInfo);
 
282
        joinrel->reloptkind = RELOPT_JOINREL;
 
283
        joinrel->relids = bms_copy(joinrelids);
 
284
        joinrel->rows = 0;
 
285
        joinrel->width = 0;
 
286
        joinrel->reltargetlist = NIL;
 
287
        joinrel->pathlist = NIL;
 
288
        joinrel->cheapest_startup_path = NULL;
 
289
        joinrel->cheapest_total_path = NULL;
 
290
        joinrel->cheapest_unique_path = NULL;
 
291
        joinrel->relid = 0;                     /* indicates not a baserel */
 
292
        joinrel->rtekind = RTE_JOIN;
 
293
        joinrel->min_attr = 0;
 
294
        joinrel->max_attr = 0;
 
295
        joinrel->attr_needed = NULL;
 
296
        joinrel->attr_widths = NULL;
 
297
        joinrel->indexlist = NIL;
 
298
        joinrel->pages = 0;
 
299
        joinrel->tuples = 0;
 
300
        joinrel->subplan = NULL;
 
301
        joinrel->baserestrictinfo = NIL;
 
302
        joinrel->baserestrictcost.startup = 0;
 
303
        joinrel->baserestrictcost.per_tuple = 0;
 
304
        joinrel->outerjoinset = NULL;
 
305
        joinrel->joininfo = NIL;
 
306
        joinrel->index_outer_relids = NULL;
 
307
        joinrel->index_inner_paths = NIL;
 
308
 
 
309
        /*
 
310
         * Create a new tlist containing just the vars that need to be output
 
311
         * from this join (ie, are needed for higher joinclauses or final
 
312
         * output).
 
313
         */
 
314
        build_joinrel_tlist(root, joinrel);
 
315
 
 
316
        /*
 
317
         * Construct restrict and join clause lists for the new joinrel. (The
 
318
         * caller might or might not need the restrictlist, but I need it
 
319
         * anyway for set_joinrel_size_estimates().)
 
320
         */
 
321
        restrictlist = build_joinrel_restrictlist(root,
 
322
                                                                                          joinrel,
 
323
                                                                                          outer_rel,
 
324
                                                                                          inner_rel,
 
325
                                                                                          jointype);
 
326
        if (restrictlist_ptr)
 
327
                *restrictlist_ptr = restrictlist;
 
328
        build_joinrel_joinlist(joinrel, outer_rel, inner_rel);
 
329
 
 
330
        /*
 
331
         * Set estimates of the joinrel's size.
 
332
         */
 
333
        set_joinrel_size_estimates(root, joinrel, outer_rel, inner_rel,
 
334
                                                           jointype, restrictlist);
 
335
 
 
336
        /*
 
337
         * Add the joinrel to the query's joinrel list.
 
338
         */
 
339
        root->join_rel_list = lcons(joinrel, root->join_rel_list);
 
340
 
 
341
        return joinrel;
 
342
}
 
343
 
 
344
/*
 
345
 * build_joinrel_tlist
 
346
 *        Builds a join relation's target list.
 
347
 *
 
348
 * The join's targetlist includes all Vars of its member relations that
 
349
 * will still be needed above the join.
 
350
 *
 
351
 * In a former lifetime, this just merged the tlists of the two member
 
352
 * relations first presented.  While we could still do that, working from
 
353
 * lists of Vars would mean doing a find_base_rel lookup for each Var.
 
354
 * It seems more efficient to scan the list of base rels and collect the
 
355
 * needed vars directly from there.
 
356
 *
 
357
 * We also compute the expected width of the join's output, making use
 
358
 * of data that was cached at the baserel level by set_rel_width().
 
359
 */
 
360
static void
 
361
build_joinrel_tlist(Query *root, RelOptInfo *joinrel)
 
362
{
 
363
        Relids          relids = joinrel->relids;
 
364
        ListCell   *rels;
 
365
 
 
366
        joinrel->reltargetlist = NIL;
 
367
        joinrel->width = 0;
 
368
 
 
369
        foreach(rels, root->base_rel_list)
 
370
        {
 
371
                RelOptInfo *baserel = (RelOptInfo *) lfirst(rels);
 
372
                ListCell   *vars;
 
373
 
 
374
                if (!bms_is_member(baserel->relid, relids))
 
375
                        continue;
 
376
 
 
377
                foreach(vars, baserel->reltargetlist)
 
378
                {
 
379
                        Var                *var = (Var *) lfirst(vars);
 
380
                        int                     ndx = var->varattno - baserel->min_attr;
 
381
 
 
382
                        /* We can't run into any child RowExprs here */
 
383
                        Assert(IsA(var, Var));
 
384
 
 
385
                        if (bms_nonempty_difference(baserel->attr_needed[ndx], relids))
 
386
                        {
 
387
                                joinrel->reltargetlist = lappend(joinrel->reltargetlist, var);
 
388
                                Assert(baserel->attr_widths[ndx] > 0);
 
389
                                joinrel->width += baserel->attr_widths[ndx];
 
390
                        }
 
391
                }
 
392
        }
 
393
}
 
394
 
 
395
/*
 
396
 * build_joinrel_restrictlist
 
397
 * build_joinrel_joinlist
 
398
 *        These routines build lists of restriction and join clauses for a
 
399
 *        join relation from the joininfo lists of the relations it joins.
 
400
 *
 
401
 *        These routines are separate because the restriction list must be
 
402
 *        built afresh for each pair of input sub-relations we consider, whereas
 
403
 *        the join lists need only be computed once for any join RelOptInfo.
 
404
 *        The join lists are fully determined by the set of rels making up the
 
405
 *        joinrel, so we should get the same results (up to ordering) from any
 
406
 *        candidate pair of sub-relations.      But the restriction list is whatever
 
407
 *        is not handled in the sub-relations, so it depends on which
 
408
 *        sub-relations are considered.
 
409
 *
 
410
 *        If a join clause from an input relation refers to base rels still not
 
411
 *        present in the joinrel, then it is still a join clause for the joinrel;
 
412
 *        we put it into an appropriate JoinInfo list for the joinrel.  Otherwise,
 
413
 *        the clause is now a restrict clause for the joined relation, and we
 
414
 *        return it to the caller of build_joinrel_restrictlist() to be stored in
 
415
 *        join paths made from this pair of sub-relations.      (It will not need to
 
416
 *        be considered further up the join tree.)
 
417
 *
 
418
 *        When building a restriction list, we eliminate redundant clauses.
 
419
 *        We don't try to do that for join clause lists, since the join clauses
 
420
 *        aren't really doing anything, just waiting to become part of higher
 
421
 *        levels' restriction lists.
 
422
 *
 
423
 * 'joinrel' is a join relation node
 
424
 * 'outer_rel' and 'inner_rel' are a pair of relations that can be joined
 
425
 *              to form joinrel.
 
426
 * 'jointype' is the type of join used.
 
427
 *
 
428
 * build_joinrel_restrictlist() returns a list of relevant restrictinfos,
 
429
 * whereas build_joinrel_joinlist() stores its results in the joinrel's
 
430
 * joininfo lists.      One or the other must accept each given clause!
 
431
 *
 
432
 * NB: Formerly, we made deep(!) copies of each input RestrictInfo to pass
 
433
 * up to the join relation.  I believe this is no longer necessary, because
 
434
 * RestrictInfo nodes are no longer context-dependent.  Instead, just include
 
435
 * the original nodes in the lists made for the join relation.
 
436
 */
 
437
static List *
 
438
build_joinrel_restrictlist(Query *root,
 
439
                                                   RelOptInfo *joinrel,
 
440
                                                   RelOptInfo *outer_rel,
 
441
                                                   RelOptInfo *inner_rel,
 
442
                                                   JoinType jointype)
 
443
{
 
444
        List       *result;
 
445
        List       *rlist;
 
446
 
 
447
        /*
 
448
         * Collect all the clauses that syntactically belong at this level.
 
449
         */
 
450
        rlist = list_concat(subbuild_joinrel_restrictlist(joinrel,
 
451
                                                                                                        outer_rel->joininfo),
 
452
                                                subbuild_joinrel_restrictlist(joinrel,
 
453
                                                                                                   inner_rel->joininfo));
 
454
 
 
455
        /*
 
456
         * Eliminate duplicate and redundant clauses.
 
457
         *
 
458
         * We must eliminate duplicates, since we will see many of the same
 
459
         * clauses arriving from both input relations.  Also, if a clause is a
 
460
         * mergejoinable clause, it's possible that it is redundant with
 
461
         * previous clauses (see optimizer/README for discussion).      We detect
 
462
         * that case and omit the redundant clause from the result list.
 
463
         */
 
464
        result = remove_redundant_join_clauses(root, rlist, jointype);
 
465
 
 
466
        list_free(rlist);
 
467
 
 
468
        return result;
 
469
}
 
470
 
 
471
static void
 
472
build_joinrel_joinlist(RelOptInfo *joinrel,
 
473
                                           RelOptInfo *outer_rel,
 
474
                                           RelOptInfo *inner_rel)
 
475
{
 
476
        subbuild_joinrel_joinlist(joinrel, outer_rel->joininfo);
 
477
        subbuild_joinrel_joinlist(joinrel, inner_rel->joininfo);
 
478
}
 
479
 
 
480
static List *
 
481
subbuild_joinrel_restrictlist(RelOptInfo *joinrel,
 
482
                                                          List *joininfo_list)
 
483
{
 
484
        List       *restrictlist = NIL;
 
485
        ListCell   *xjoininfo;
 
486
 
 
487
        foreach(xjoininfo, joininfo_list)
 
488
        {
 
489
                JoinInfo   *joininfo = (JoinInfo *) lfirst(xjoininfo);
 
490
 
 
491
                if (bms_is_subset(joininfo->unjoined_relids, joinrel->relids))
 
492
                {
 
493
                        /*
 
494
                         * Clauses in this JoinInfo list become restriction clauses
 
495
                         * for the joinrel, since they refer to no outside rels.
 
496
                         *
 
497
                         * We must copy the list to avoid disturbing the input relation,
 
498
                         * but we can use a shallow copy.
 
499
                         */
 
500
                        restrictlist = list_concat(restrictlist,
 
501
                                                                list_copy(joininfo->jinfo_restrictinfo));
 
502
                }
 
503
                else
 
504
                {
 
505
                        /*
 
506
                         * These clauses are still join clauses at this level, so we
 
507
                         * ignore them in this routine.
 
508
                         */
 
509
                }
 
510
        }
 
511
 
 
512
        return restrictlist;
 
513
}
 
514
 
 
515
static void
 
516
subbuild_joinrel_joinlist(RelOptInfo *joinrel,
 
517
                                                  List *joininfo_list)
 
518
{
 
519
        ListCell   *xjoininfo;
 
520
 
 
521
        foreach(xjoininfo, joininfo_list)
 
522
        {
 
523
                JoinInfo   *joininfo = (JoinInfo *) lfirst(xjoininfo);
 
524
                Relids          new_unjoined_relids;
 
525
 
 
526
                new_unjoined_relids = bms_difference(joininfo->unjoined_relids,
 
527
                                                                                         joinrel->relids);
 
528
                if (bms_is_empty(new_unjoined_relids))
 
529
                {
 
530
                        /*
 
531
                         * Clauses in this JoinInfo list become restriction clauses
 
532
                         * for the joinrel, since they refer to no outside rels. So we
 
533
                         * can ignore them in this routine.
 
534
                         */
 
535
                        bms_free(new_unjoined_relids);
 
536
                }
 
537
                else
 
538
                {
 
539
                        /*
 
540
                         * These clauses are still join clauses at this level, so find
 
541
                         * or make the appropriate JoinInfo item for the joinrel, and
 
542
                         * add the clauses to it, eliminating duplicates.  (Since
 
543
                         * RestrictInfo nodes are normally multiply-linked rather than
 
544
                         * copied, pointer equality should be a sufficient test.  If
 
545
                         * two equal() nodes should happen to sneak in, no great harm
 
546
                         * is done --- they'll be detected by redundant-clause testing
 
547
                         * when they reach a restriction list.)
 
548
                         */
 
549
                        JoinInfo   *new_joininfo;
 
550
 
 
551
                        new_joininfo = make_joininfo_node(joinrel, new_unjoined_relids);
 
552
                        new_joininfo->jinfo_restrictinfo =
 
553
                                list_union_ptr(new_joininfo->jinfo_restrictinfo,
 
554
                                                           joininfo->jinfo_restrictinfo);
 
555
                }
 
556
        }
 
557
}