← Back to branch summary

~vcs-imports/mammoth-replicator/trunk

« back to all changes in this revision

Viewing changes to src/backend/executor/nodeNestloop.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/executor/nodeNestloop.c
 
1
/*-------------------------------------------------------------------------
 
2
 *
 
3
 * nodeNestloop.c
 
4
 *        routines to support nest-loop joins
 
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/executor/nodeNestloop.c,v 1.38 2004-12-31 21:59:45 pgsql Exp $
 
12
 *
 
13
 *-------------------------------------------------------------------------
 
14
 */
 
15
/*
 
16
 *       INTERFACE ROUTINES
 
17
 *              ExecNestLoop     - process a nestloop join of two plans
 
18
 *              ExecInitNestLoop - initialize the join
 
19
 *              ExecEndNestLoop  - shut down the join
 
20
 */
 
21
 
 
22
#include "postgres.h"
 
23
 
 
24
#include "executor/execdebug.h"
 
25
#include "executor/nodeNestloop.h"
 
26
#include "utils/memutils.h"
 
27
 
 
28
 
 
29
/* ----------------------------------------------------------------
 
30
 *              ExecNestLoop(node)
 
31
 *
 
32
 * old comments
 
33
 *              Returns the tuple joined from inner and outer tuples which
 
34
 *              satisfies the qualification clause.
 
35
 *
 
36
 *              It scans the inner relation to join with current outer tuple.
 
37
 *
 
38
 *              If none is found, next tuple from the outer relation is retrieved
 
39
 *              and the inner relation is scanned from the beginning again to join
 
40
 *              with the outer tuple.
 
41
 *
 
42
 *              NULL is returned if all the remaining outer tuples are tried and
 
43
 *              all fail to join with the inner tuples.
 
44
 *
 
45
 *              NULL is also returned if there is no tuple from inner relation.
 
46
 *
 
47
 *              Conditions:
 
48
 *                -- outerTuple contains current tuple from outer relation and
 
49
 *                       the right son(inner relation) maintains "cursor" at the tuple
 
50
 *                       returned previously.
 
51
 *                              This is achieved by maintaining a scan position on the outer
 
52
 *                              relation.
 
53
 *
 
54
 *              Initial States:
 
55
 *                -- the outer child and the inner child
 
56
 *                         are prepared to return the first tuple.
 
57
 * ----------------------------------------------------------------
 
58
 */
 
59
TupleTableSlot *
 
60
ExecNestLoop(NestLoopState *node)
 
61
{
 
62
        PlanState  *innerPlan;
 
63
        PlanState  *outerPlan;
 
64
        TupleTableSlot *outerTupleSlot;
 
65
        TupleTableSlot *innerTupleSlot;
 
66
        List       *joinqual;
 
67
        List       *otherqual;
 
68
        ExprContext *econtext;
 
69
 
 
70
        /*
 
71
         * get information from the node
 
72
         */
 
73
        ENL1_printf("getting info from node");
 
74
 
 
75
        joinqual = node->js.joinqual;
 
76
        otherqual = node->js.ps.qual;
 
77
        outerPlan = outerPlanState(node);
 
78
        innerPlan = innerPlanState(node);
 
79
        econtext = node->js.ps.ps_ExprContext;
 
80
 
 
81
        /*
 
82
         * get the current outer tuple
 
83
         */
 
84
        outerTupleSlot = node->js.ps.ps_OuterTupleSlot;
 
85
        econtext->ecxt_outertuple = outerTupleSlot;
 
86
 
 
87
        /*
 
88
         * Check to see if we're still projecting out tuples from a previous
 
89
         * join tuple (because there is a function-returning-set in the
 
90
         * projection expressions).  If so, try to project another one.
 
91
         */
 
92
        if (node->js.ps.ps_TupFromTlist)
 
93
        {
 
94
                TupleTableSlot *result;
 
95
                ExprDoneCond isDone;
 
96
 
 
97
                result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
 
98
                if (isDone == ExprMultipleResult)
 
99
                        return result;
 
100
                /* Done with that source tuple... */
 
101
                node->js.ps.ps_TupFromTlist = false;
 
102
        }
 
103
 
 
104
        /*
 
105
         * If we're doing an IN join, we want to return at most one row per
 
106
         * outer tuple; so we can stop scanning the inner scan if we matched
 
107
         * on the previous try.
 
108
         */
 
109
        if (node->js.jointype == JOIN_IN &&
 
110
                node->nl_MatchedOuter)
 
111
                node->nl_NeedNewOuter = true;
 
112
 
 
113
        /*
 
114
         * Reset per-tuple memory context to free any expression evaluation
 
115
         * storage allocated in the previous tuple cycle.  Note this can't
 
116
         * happen until we're done projecting out tuples from a join tuple.
 
117
         */
 
118
        ResetExprContext(econtext);
 
119
 
 
120
        /*
 
121
         * Ok, everything is setup for the join so now loop until we return a
 
122
         * qualifying join tuple.
 
123
         */
 
124
        ENL1_printf("entering main loop");
 
125
 
 
126
        for (;;)
 
127
        {
 
128
                /*
 
129
                 * If we don't have an outer tuple, get the next one and reset the
 
130
                 * inner scan.
 
131
                 */
 
132
                if (node->nl_NeedNewOuter)
 
133
                {
 
134
                        ENL1_printf("getting new outer tuple");
 
135
                        outerTupleSlot = ExecProcNode(outerPlan);
 
136
 
 
137
                        /*
 
138
                         * if there are no more outer tuples, then the join is
 
139
                         * complete..
 
140
                         */
 
141
                        if (TupIsNull(outerTupleSlot))
 
142
                        {
 
143
                                ENL1_printf("no outer tuple, ending join");
 
144
                                return NULL;
 
145
                        }
 
146
 
 
147
                        ENL1_printf("saving new outer tuple information");
 
148
                        node->js.ps.ps_OuterTupleSlot = outerTupleSlot;
 
149
                        econtext->ecxt_outertuple = outerTupleSlot;
 
150
                        node->nl_NeedNewOuter = false;
 
151
                        node->nl_MatchedOuter = false;
 
152
 
 
153
                        /*
 
154
                         * now rescan the inner plan
 
155
                         */
 
156
                        ENL1_printf("rescanning inner plan");
 
157
 
 
158
                        /*
 
159
                         * The scan key of the inner plan might depend on the current
 
160
                         * outer tuple (e.g. in index scans), that's why we pass our
 
161
                         * expr context.
 
162
                         */
 
163
                        ExecReScan(innerPlan, econtext);
 
164
                }
 
165
 
 
166
                /*
 
167
                 * we have an outerTuple, try to get the next inner tuple.
 
168
                 */
 
169
                ENL1_printf("getting new inner tuple");
 
170
 
 
171
                innerTupleSlot = ExecProcNode(innerPlan);
 
172
                econtext->ecxt_innertuple = innerTupleSlot;
 
173
 
 
174
                if (TupIsNull(innerTupleSlot))
 
175
                {
 
176
                        ENL1_printf("no inner tuple, need new outer tuple");
 
177
 
 
178
                        node->nl_NeedNewOuter = true;
 
179
 
 
180
                        if (!node->nl_MatchedOuter &&
 
181
                                node->js.jointype == JOIN_LEFT)
 
182
                        {
 
183
                                /*
 
184
                                 * We are doing an outer join and there were no join
 
185
                                 * matches for this outer tuple.  Generate a fake join
 
186
                                 * tuple with nulls for the inner tuple, and return it if
 
187
                                 * it passes the non-join quals.
 
188
                                 */
 
189
                                econtext->ecxt_innertuple = node->nl_NullInnerTupleSlot;
 
190
 
 
191
                                ENL1_printf("testing qualification for outer-join tuple");
 
192
 
 
193
                                if (ExecQual(otherqual, econtext, false))
 
194
                                {
 
195
                                        /*
 
196
                                         * qualification was satisfied so we project and
 
197
                                         * return the slot containing the result tuple using
 
198
                                         * ExecProject().
 
199
                                         */
 
200
                                        TupleTableSlot *result;
 
201
                                        ExprDoneCond isDone;
 
202
 
 
203
                                        ENL1_printf("qualification succeeded, projecting tuple");
 
204
 
 
205
                                        result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
 
206
 
 
207
                                        if (isDone != ExprEndResult)
 
208
                                        {
 
209
                                                node->js.ps.ps_TupFromTlist =
 
210
                                                        (isDone == ExprMultipleResult);
 
211
                                                return result;
 
212
                                        }
 
213
                                }
 
214
                        }
 
215
 
 
216
                        /*
 
217
                         * Otherwise just return to top of loop for a new outer tuple.
 
218
                         */
 
219
                        continue;
 
220
                }
 
221
 
 
222
                /*
 
223
                 * at this point we have a new pair of inner and outer tuples so
 
224
                 * we test the inner and outer tuples to see if they satisfy the
 
225
                 * node's qualification.
 
226
                 *
 
227
                 * Only the joinquals determine MatchedOuter status, but all quals
 
228
                 * must pass to actually return the tuple.
 
229
                 */
 
230
                ENL1_printf("testing qualification");
 
231
 
 
232
                if (ExecQual(joinqual, econtext, false))
 
233
                {
 
234
                        node->nl_MatchedOuter = true;
 
235
 
 
236
                        if (otherqual == NIL || ExecQual(otherqual, econtext, false))
 
237
                        {
 
238
                                /*
 
239
                                 * qualification was satisfied so we project and return
 
240
                                 * the slot containing the result tuple using
 
241
                                 * ExecProject().
 
242
                                 */
 
243
                                TupleTableSlot *result;
 
244
                                ExprDoneCond isDone;
 
245
 
 
246
                                ENL1_printf("qualification succeeded, projecting tuple");
 
247
 
 
248
                                result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
 
249
 
 
250
                                if (isDone != ExprEndResult)
 
251
                                {
 
252
                                        node->js.ps.ps_TupFromTlist =
 
253
                                                (isDone == ExprMultipleResult);
 
254
                                        return result;
 
255
                                }
 
256
                        }
 
257
 
 
258
                        /* If we didn't return a tuple, may need to set NeedNewOuter */
 
259
                        if (node->js.jointype == JOIN_IN)
 
260
                                node->nl_NeedNewOuter = true;
 
261
                }
 
262
 
 
263
                /*
 
264
                 * Tuple fails qual, so free per-tuple memory and try again.
 
265
                 */
 
266
                ResetExprContext(econtext);
 
267
 
 
268
                ENL1_printf("qualification failed, looping");
 
269
        }
 
270
}
 
271
 
 
272
/* ----------------------------------------------------------------
 
273
 *              ExecInitNestLoop
 
274
 * ----------------------------------------------------------------
 
275
 */
 
276
NestLoopState *
 
277
ExecInitNestLoop(NestLoop *node, EState *estate)
 
278
{
 
279
        NestLoopState *nlstate;
 
280
 
 
281
        NL1_printf("ExecInitNestLoop: %s\n",
 
282
                           "initializing node");
 
283
 
 
284
        /*
 
285
         * create state structure
 
286
         */
 
287
        nlstate = makeNode(NestLoopState);
 
288
        nlstate->js.ps.plan = (Plan *) node;
 
289
        nlstate->js.ps.state = estate;
 
290
 
 
291
        /*
 
292
         * Miscellaneous initialization
 
293
         *
 
294
         * create expression context for node
 
295
         */
 
296
        ExecAssignExprContext(estate, &nlstate->js.ps);
 
297
 
 
298
        /*
 
299
         * initialize child expressions
 
300
         */
 
301
        nlstate->js.ps.targetlist = (List *)
 
302
                ExecInitExpr((Expr *) node->join.plan.targetlist,
 
303
                                         (PlanState *) nlstate);
 
304
        nlstate->js.ps.qual = (List *)
 
305
                ExecInitExpr((Expr *) node->join.plan.qual,
 
306
                                         (PlanState *) nlstate);
 
307
        nlstate->js.jointype = node->join.jointype;
 
308
        nlstate->js.joinqual = (List *)
 
309
                ExecInitExpr((Expr *) node->join.joinqual,
 
310
                                         (PlanState *) nlstate);
 
311
 
 
312
        /*
 
313
         * initialize child nodes
 
314
         */
 
315
        outerPlanState(nlstate) = ExecInitNode(outerPlan(node), estate);
 
316
        innerPlanState(nlstate) = ExecInitNode(innerPlan(node), estate);
 
317
 
 
318
#define NESTLOOP_NSLOTS 2
 
319
 
 
320
        /*
 
321
         * tuple table initialization
 
322
         */
 
323
        ExecInitResultTupleSlot(estate, &nlstate->js.ps);
 
324
 
 
325
        switch (node->join.jointype)
 
326
        {
 
327
                case JOIN_INNER:
 
328
                case JOIN_IN:
 
329
                        break;
 
330
                case JOIN_LEFT:
 
331
                        nlstate->nl_NullInnerTupleSlot =
 
332
                                ExecInitNullTupleSlot(estate,
 
333
                                                         ExecGetResultType(innerPlanState(nlstate)));
 
334
                        break;
 
335
                default:
 
336
                        elog(ERROR, "unrecognized join type: %d",
 
337
                                 (int) node->join.jointype);
 
338
        }
 
339
 
 
340
        /*
 
341
         * initialize tuple type and projection info
 
342
         */
 
343
        ExecAssignResultTypeFromTL(&nlstate->js.ps);
 
344
        ExecAssignProjectionInfo(&nlstate->js.ps);
 
345
 
 
346
        /*
 
347
         * finally, wipe the current outer tuple clean.
 
348
         */
 
349
        nlstate->js.ps.ps_OuterTupleSlot = NULL;
 
350
        nlstate->js.ps.ps_TupFromTlist = false;
 
351
        nlstate->nl_NeedNewOuter = true;
 
352
        nlstate->nl_MatchedOuter = false;
 
353
 
 
354
        NL1_printf("ExecInitNestLoop: %s\n",
 
355
                           "node initialized");
 
356
 
 
357
        return nlstate;
 
358
}
 
359
 
 
360
int
 
361
ExecCountSlotsNestLoop(NestLoop *node)
 
362
{
 
363
        return ExecCountSlotsNode(outerPlan(node)) +
 
364
                ExecCountSlotsNode(innerPlan(node)) +
 
365
                NESTLOOP_NSLOTS;
 
366
}
 
367
 
 
368
/* ----------------------------------------------------------------
 
369
 *              ExecEndNestLoop
 
370
 *
 
371
 *              closes down scans and frees allocated storage
 
372
 * ----------------------------------------------------------------
 
373
 */
 
374
void
 
375
ExecEndNestLoop(NestLoopState *node)
 
376
{
 
377
        NL1_printf("ExecEndNestLoop: %s\n",
 
378
                           "ending node processing");
 
379
 
 
380
        /*
 
381
         * Free the exprcontext
 
382
         */
 
383
        ExecFreeExprContext(&node->js.ps);
 
384
 
 
385
        /*
 
386
         * clean out the tuple table
 
387
         */
 
388
        ExecClearTuple(node->js.ps.ps_ResultTupleSlot);
 
389
 
 
390
        /*
 
391
         * close down subplans
 
392
         */
 
393
        ExecEndNode(outerPlanState(node));
 
394
        ExecEndNode(innerPlanState(node));
 
395
 
 
396
        NL1_printf("ExecEndNestLoop: %s\n",
 
397
                           "node processing ended");
 
398
}
 
399
 
 
400
/* ----------------------------------------------------------------
 
401
 *              ExecReScanNestLoop
 
402
 * ----------------------------------------------------------------
 
403
 */
 
404
void
 
405
ExecReScanNestLoop(NestLoopState *node, ExprContext *exprCtxt)
 
406
{
 
407
        PlanState  *outerPlan = outerPlanState(node);
 
408
 
 
409
        /*
 
410
         * If outerPlan->chgParam is not null then plan will be automatically
 
411
         * re-scanned by first ExecProcNode. innerPlan is re-scanned for each
 
412
         * new outer tuple and MUST NOT be re-scanned from here or you'll get
 
413
         * troubles from inner index scans when outer Vars are used as
 
414
         * run-time keys...
 
415
         */
 
416
        if (outerPlan->chgParam == NULL)
 
417
                ExecReScan(outerPlan, exprCtxt);
 
418
 
 
419
        /* let outerPlan to free its result tuple ... */
 
420
        node->js.ps.ps_OuterTupleSlot = NULL;
 
421
        node->js.ps.ps_TupFromTlist = false;
 
422
        node->nl_NeedNewOuter = true;
 
423
        node->nl_MatchedOuter = false;
 
424
}