← Back to branch summary

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

« back to all changes in this revision

Viewing changes to src/backend/executor/nodeRecursiveunion.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/executor/nodeRecursiveunion.c
 
1
/*-------------------------------------------------------------------------
 
2
 *
 
3
 * nodeRecursiveunion.c
 
4
 *        routines to handle RecursiveUnion nodes.
 
5
 *
 
6
 * Portions Copyright (c) 1996-2011, PostgreSQL Global Development Group
 
7
 * Portions Copyright (c) 1994, Regents of the University of California
 
8
 *
 
9
 *
 
10
 * IDENTIFICATION
 
11
 *        src/backend/executor/nodeRecursiveunion.c
 
12
 *
 
13
 *-------------------------------------------------------------------------
 
14
 */
 
15
#include "postgres.h"
 
16
 
 
17
#include "executor/execdebug.h"
 
18
#include "executor/nodeRecursiveunion.h"
 
19
#include "miscadmin.h"
 
20
#include "utils/memutils.h"
 
21
 
 
22
 
 
23
/*
 
24
 * To implement UNION (without ALL), we need a hashtable that stores tuples
 
25
 * already seen.  The hash key is computed from the grouping columns.
 
26
 */
 
27
typedef struct RUHashEntryData *RUHashEntry;
 
28
 
 
29
typedef struct RUHashEntryData
 
30
{
 
31
        TupleHashEntryData shared;      /* common header for hash table entries */
 
32
}       RUHashEntryData;
 
33
 
 
34
 
 
35
/*
 
36
 * Initialize the hash table to empty.
 
37
 */
 
38
static void
 
39
build_hash_table(RecursiveUnionState *rustate)
 
40
{
 
41
        RecursiveUnion *node = (RecursiveUnion *) rustate->ps.plan;
 
42
 
 
43
        Assert(node->numCols > 0);
 
44
        Assert(node->numGroups > 0);
 
45
 
 
46
        rustate->hashtable = BuildTupleHashTable(node->numCols,
 
47
                                                                                         node->dupColIdx,
 
48
                                                                                         rustate->eqfunctions,
 
49
                                                                                         rustate->hashfunctions,
 
50
                                                                                         node->numGroups,
 
51
                                                                                         sizeof(RUHashEntryData),
 
52
                                                                                         rustate->tableContext,
 
53
                                                                                         rustate->tempContext);
 
54
}
 
55
 
 
56
 
 
57
/* ----------------------------------------------------------------
 
58
 *              ExecRecursiveUnion(node)
 
59
 *
 
60
 *              Scans the recursive query sequentially and returns the next
 
61
 *              qualifying tuple.
 
62
 *
 
63
 * 1. evaluate non recursive term and assign the result to RT
 
64
 *
 
65
 * 2. execute recursive terms
 
66
 *
 
67
 * 2.1 WT := RT
 
68
 * 2.2 while WT is not empty repeat 2.3 to 2.6. if WT is empty returns RT
 
69
 * 2.3 replace the name of recursive term with WT
 
70
 * 2.4 evaluate the recursive term and store into WT
 
71
 * 2.5 append WT to RT
 
72
 * 2.6 go back to 2.2
 
73
 * ----------------------------------------------------------------
 
74
 */
 
75
TupleTableSlot *
 
76
ExecRecursiveUnion(RecursiveUnionState *node)
 
77
{
 
78
        PlanState  *outerPlan = outerPlanState(node);
 
79
        PlanState  *innerPlan = innerPlanState(node);
 
80
        RecursiveUnion *plan = (RecursiveUnion *) node->ps.plan;
 
81
        TupleTableSlot *slot;
 
82
        bool            isnew;
 
83
 
 
84
        /* 1. Evaluate non-recursive term */
 
85
        if (!node->recursing)
 
86
        {
 
87
                for (;;)
 
88
                {
 
89
                        slot = ExecProcNode(outerPlan);
 
90
                        if (TupIsNull(slot))
 
91
                                break;
 
92
                        if (plan->numCols > 0)
 
93
                        {
 
94
                                /* Find or build hashtable entry for this tuple's group */
 
95
                                LookupTupleHashEntry(node->hashtable, slot, &isnew);
 
96
                                /* Must reset temp context after each hashtable lookup */
 
97
                                MemoryContextReset(node->tempContext);
 
98
                                /* Ignore tuple if already seen */
 
99
                                if (!isnew)
 
100
                                        continue;
 
101
                        }
 
102
                        /* Each non-duplicate tuple goes to the working table ... */
 
103
                        tuplestore_puttupleslot(node->working_table, slot);
 
104
                        /* ... and to the caller */
 
105
                        return slot;
 
106
                }
 
107
                node->recursing = true;
 
108
        }
 
109
 
 
110
        /* 2. Execute recursive term */
 
111
        for (;;)
 
112
        {
 
113
                slot = ExecProcNode(innerPlan);
 
114
                if (TupIsNull(slot))
 
115
                {
 
116
                        /* Done if there's nothing in the intermediate table */
 
117
                        if (node->intermediate_empty)
 
118
                                break;
 
119
 
 
120
                        /* done with old working table ... */
 
121
                        tuplestore_end(node->working_table);
 
122
 
 
123
                        /* intermediate table becomes working table */
 
124
                        node->working_table = node->intermediate_table;
 
125
 
 
126
                        /* create new empty intermediate table */
 
127
                        node->intermediate_table = tuplestore_begin_heap(false, false,
 
128
                                                                                                                         work_mem);
 
129
                        node->intermediate_empty = true;
 
130
 
 
131
                        /* reset the recursive term */
 
132
                        innerPlan->chgParam = bms_add_member(innerPlan->chgParam,
 
133
                                                                                                 plan->wtParam);
 
134
 
 
135
                        /* and continue fetching from recursive term */
 
136
                        continue;
 
137
                }
 
138
 
 
139
                if (plan->numCols > 0)
 
140
                {
 
141
                        /* Find or build hashtable entry for this tuple's group */
 
142
                        LookupTupleHashEntry(node->hashtable, slot, &isnew);
 
143
                        /* Must reset temp context after each hashtable lookup */
 
144
                        MemoryContextReset(node->tempContext);
 
145
                        /* Ignore tuple if already seen */
 
146
                        if (!isnew)
 
147
                                continue;
 
148
                }
 
149
 
 
150
                /* Else, tuple is good; stash it in intermediate table ... */
 
151
                node->intermediate_empty = false;
 
152
                tuplestore_puttupleslot(node->intermediate_table, slot);
 
153
                /* ... and return it */
 
154
                return slot;
 
155
        }
 
156
 
 
157
        return NULL;
 
158
}
 
159
 
 
160
/* ----------------------------------------------------------------
 
161
 *              ExecInitRecursiveUnionScan
 
162
 * ----------------------------------------------------------------
 
163
 */
 
164
RecursiveUnionState *
 
165
ExecInitRecursiveUnion(RecursiveUnion *node, EState *estate, int eflags)
 
166
{
 
167
        RecursiveUnionState *rustate;
 
168
        ParamExecData *prmdata;
 
169
 
 
170
        /* check for unsupported flags */
 
171
        Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
 
172
 
 
173
        /*
 
174
         * create state structure
 
175
         */
 
176
        rustate = makeNode(RecursiveUnionState);
 
177
        rustate->ps.plan = (Plan *) node;
 
178
        rustate->ps.state = estate;
 
179
 
 
180
        rustate->eqfunctions = NULL;
 
181
        rustate->hashfunctions = NULL;
 
182
        rustate->hashtable = NULL;
 
183
        rustate->tempContext = NULL;
 
184
        rustate->tableContext = NULL;
 
185
 
 
186
        /* initialize processing state */
 
187
        rustate->recursing = false;
 
188
        rustate->intermediate_empty = true;
 
189
        rustate->working_table = tuplestore_begin_heap(false, false, work_mem);
 
190
        rustate->intermediate_table = tuplestore_begin_heap(false, false, work_mem);
 
191
 
 
192
        /*
 
193
         * If hashing, we need a per-tuple memory context for comparisons, and a
 
194
         * longer-lived context to store the hash table.  The table can't just be
 
195
         * kept in the per-query context because we want to be able to throw it
 
196
         * away when rescanning.
 
197
         */
 
198
        if (node->numCols > 0)
 
199
        {
 
200
                rustate->tempContext =
 
201
                        AllocSetContextCreate(CurrentMemoryContext,
 
202
                                                                  "RecursiveUnion",
 
203
                                                                  ALLOCSET_DEFAULT_MINSIZE,
 
204
                                                                  ALLOCSET_DEFAULT_INITSIZE,
 
205
                                                                  ALLOCSET_DEFAULT_MAXSIZE);
 
206
                rustate->tableContext =
 
207
                        AllocSetContextCreate(CurrentMemoryContext,
 
208
                                                                  "RecursiveUnion hash table",
 
209
                                                                  ALLOCSET_DEFAULT_MINSIZE,
 
210
                                                                  ALLOCSET_DEFAULT_INITSIZE,
 
211
                                                                  ALLOCSET_DEFAULT_MAXSIZE);
 
212
        }
 
213
 
 
214
        /*
 
215
         * Make the state structure available to descendant WorkTableScan nodes
 
216
         * via the Param slot reserved for it.
 
217
         */
 
218
        prmdata = &(estate->es_param_exec_vals[node->wtParam]);
 
219
        Assert(prmdata->execPlan == NULL);
 
220
        prmdata->value = PointerGetDatum(rustate);
 
221
        prmdata->isnull = false;
 
222
 
 
223
        /*
 
224
         * Miscellaneous initialization
 
225
         *
 
226
         * RecursiveUnion plans don't have expression contexts because they never
 
227
         * call ExecQual or ExecProject.
 
228
         */
 
229
        Assert(node->plan.qual == NIL);
 
230
 
 
231
        /*
 
232
         * RecursiveUnion nodes still have Result slots, which hold pointers to
 
233
         * tuples, so we have to initialize them.
 
234
         */
 
235
        ExecInitResultTupleSlot(estate, &rustate->ps);
 
236
 
 
237
        /*
 
238
         * Initialize result tuple type and projection info.  (Note: we have to
 
239
         * set up the result type before initializing child nodes, because
 
240
         * nodeWorktablescan.c expects it to be valid.)
 
241
         */
 
242
        ExecAssignResultTypeFromTL(&rustate->ps);
 
243
        rustate->ps.ps_ProjInfo = NULL;
 
244
 
 
245
        /*
 
246
         * initialize child nodes
 
247
         */
 
248
        outerPlanState(rustate) = ExecInitNode(outerPlan(node), estate, eflags);
 
249
        innerPlanState(rustate) = ExecInitNode(innerPlan(node), estate, eflags);
 
250
 
 
251
        /*
 
252
         * If hashing, precompute fmgr lookup data for inner loop, and create the
 
253
         * hash table.
 
254
         */
 
255
        if (node->numCols > 0)
 
256
        {
 
257
                execTuplesHashPrepare(node->numCols,
 
258
                                                          node->dupOperators,
 
259
                                                          &rustate->eqfunctions,
 
260
                                                          &rustate->hashfunctions);
 
261
                build_hash_table(rustate);
 
262
        }
 
263
 
 
264
        return rustate;
 
265
}
 
266
 
 
267
/* ----------------------------------------------------------------
 
268
 *              ExecEndRecursiveUnionScan
 
269
 *
 
270
 *              frees any storage allocated through C routines.
 
271
 * ----------------------------------------------------------------
 
272
 */
 
273
void
 
274
ExecEndRecursiveUnion(RecursiveUnionState *node)
 
275
{
 
276
        /* Release tuplestores */
 
277
        tuplestore_end(node->working_table);
 
278
        tuplestore_end(node->intermediate_table);
 
279
 
 
280
        /* free subsidiary stuff including hashtable */
 
281
        if (node->tempContext)
 
282
                MemoryContextDelete(node->tempContext);
 
283
        if (node->tableContext)
 
284
                MemoryContextDelete(node->tableContext);
 
285
 
 
286
        /*
 
287
         * clean out the upper tuple table
 
288
         */
 
289
        ExecClearTuple(node->ps.ps_ResultTupleSlot);
 
290
 
 
291
        /*
 
292
         * close down subplans
 
293
         */
 
294
        ExecEndNode(outerPlanState(node));
 
295
        ExecEndNode(innerPlanState(node));
 
296
}
 
297
 
 
298
/* ----------------------------------------------------------------
 
299
 *              ExecReScanRecursiveUnion
 
300
 *
 
301
 *              Rescans the relation.
 
302
 * ----------------------------------------------------------------
 
303
 */
 
304
void
 
305
ExecReScanRecursiveUnion(RecursiveUnionState *node)
 
306
{
 
307
        PlanState  *outerPlan = outerPlanState(node);
 
308
        PlanState  *innerPlan = innerPlanState(node);
 
309
        RecursiveUnion *plan = (RecursiveUnion *) node->ps.plan;
 
310
 
 
311
        /*
 
312
         * Set recursive term's chgParam to tell it that we'll modify the working
 
313
         * table and therefore it has to rescan.
 
314
         */
 
315
        innerPlan->chgParam = bms_add_member(innerPlan->chgParam, plan->wtParam);
 
316
 
 
317
        /*
 
318
         * if chgParam of subnode is not null then plan will be re-scanned by
 
319
         * first ExecProcNode.  Because of above, we only have to do this to the
 
320
         * non-recursive term.
 
321
         */
 
322
        if (outerPlan->chgParam == NULL)
 
323
                ExecReScan(outerPlan);
 
324
 
 
325
        /* Release any hashtable storage */
 
326
        if (node->tableContext)
 
327
                MemoryContextResetAndDeleteChildren(node->tableContext);
 
328
 
 
329
        /* And rebuild empty hashtable if needed */
 
330
        if (plan->numCols > 0)
 
331
                build_hash_table(node);
 
332
 
 
333
        /* reset processing state */
 
334
        node->recursing = false;
 
335
        node->intermediate_empty = true;
 
336
        tuplestore_clear(node->working_table);
 
337
        tuplestore_clear(node->intermediate_table);
 
338
}