1 /*-------------------------------------------------------------------------
2 *
3 * nodeNestloop.c
4 * routines to support nest-loop joins
5 *
6 * Portions Copyright (c) 1996-2016, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
8 *
9 *
10 * IDENTIFICATION
11 * src/backend/executor/nodeNestloop.c
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 *
ExecNestLoop(NestLoopState * node)60 ExecNestLoop(NestLoopState *node)
61 {
62 NestLoop *nl;
63 PlanState *innerPlan;
64 PlanState *outerPlan;
65 TupleTableSlot *outerTupleSlot;
66 TupleTableSlot *innerTupleSlot;
67 List *joinqual;
68 List *otherqual;
69 ExprContext *econtext;
70 ListCell *lc;
71
72 /*
73 * get information from the node
74 */
75 ENL1_printf("getting info from node");
76
77 nl = (NestLoop *) node->js.ps.plan;
78 joinqual = node->js.joinqual;
79 otherqual = node->js.ps.qual;
80 outerPlan = outerPlanState(node);
81 innerPlan = innerPlanState(node);
82 econtext = node->js.ps.ps_ExprContext;
83
84 /*
85 * Check to see if we're still projecting out tuples from a previous join
86 * tuple (because there is a function-returning-set in the projection
87 * expressions). If so, try to project another one.
88 */
89 if (node->js.ps.ps_TupFromTlist)
90 {
91 TupleTableSlot *result;
92 ExprDoneCond isDone;
93
94 result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
95 if (isDone == ExprMultipleResult)
96 return result;
97 /* Done with that source tuple... */
98 node->js.ps.ps_TupFromTlist = false;
99 }
100
101 /*
102 * Reset per-tuple memory context to free any expression evaluation
103 * storage allocated in the previous tuple cycle. Note this can't happen
104 * until we're done projecting out tuples from a join tuple.
105 */
106 ResetExprContext(econtext);
107
108 /*
109 * Ok, everything is setup for the join so now loop until we return a
110 * qualifying join tuple.
111 */
112 ENL1_printf("entering main loop");
113
114 for (;;)
115 {
116 /*
117 * If we don't have an outer tuple, get the next one and reset the
118 * inner scan.
119 */
120 if (node->nl_NeedNewOuter)
121 {
122 ENL1_printf("getting new outer tuple");
123 outerTupleSlot = ExecProcNode(outerPlan);
124
125 /*
126 * if there are no more outer tuples, then the join is complete..
127 */
128 if (TupIsNull(outerTupleSlot))
129 {
130 ENL1_printf("no outer tuple, ending join");
131 return NULL;
132 }
133
134 ENL1_printf("saving new outer tuple information");
135 econtext->ecxt_outertuple = outerTupleSlot;
136 node->nl_NeedNewOuter = false;
137 node->nl_MatchedOuter = false;
138
139 /*
140 * fetch the values of any outer Vars that must be passed to the
141 * inner scan, and store them in the appropriate PARAM_EXEC slots.
142 */
143 foreach(lc, nl->nestParams)
144 {
145 NestLoopParam *nlp = (NestLoopParam *) lfirst(lc);
146 int paramno = nlp->paramno;
147 ParamExecData *prm;
148
149 prm = &(econtext->ecxt_param_exec_vals[paramno]);
150 /* Param value should be an OUTER_VAR var */
151 Assert(IsA(nlp->paramval, Var));
152 Assert(nlp->paramval->varno == OUTER_VAR);
153 Assert(nlp->paramval->varattno > 0);
154 prm->value = slot_getattr(outerTupleSlot,
155 nlp->paramval->varattno,
156 &(prm->isnull));
157 /* Flag parameter value as changed */
158 innerPlan->chgParam = bms_add_member(innerPlan->chgParam,
159 paramno);
160 }
161
162 /*
163 * now rescan the inner plan
164 */
165 ENL1_printf("rescanning inner plan");
166 ExecReScan(innerPlan);
167 }
168
169 /*
170 * we have an outerTuple, try to get the next inner tuple.
171 */
172 ENL1_printf("getting new inner tuple");
173
174 innerTupleSlot = ExecProcNode(innerPlan);
175 econtext->ecxt_innertuple = innerTupleSlot;
176
177 if (TupIsNull(innerTupleSlot))
178 {
179 ENL1_printf("no inner tuple, need new outer tuple");
180
181 node->nl_NeedNewOuter = true;
182
183 if (!node->nl_MatchedOuter &&
184 (node->js.jointype == JOIN_LEFT ||
185 node->js.jointype == JOIN_ANTI))
186 {
187 /*
188 * We are doing an outer join and there were no join matches
189 * for this outer tuple. Generate a fake join tuple with
190 * nulls for the inner tuple, and return it if it passes the
191 * non-join quals.
192 */
193 econtext->ecxt_innertuple = node->nl_NullInnerTupleSlot;
194
195 ENL1_printf("testing qualification for outer-join tuple");
196
197 if (otherqual == NIL || ExecQual(otherqual, econtext, false))
198 {
199 /*
200 * qualification was satisfied so we project and return
201 * the slot containing the result tuple using
202 * ExecProject().
203 */
204 TupleTableSlot *result;
205 ExprDoneCond isDone;
206
207 ENL1_printf("qualification succeeded, projecting tuple");
208
209 result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
210
211 if (isDone != ExprEndResult)
212 {
213 node->js.ps.ps_TupFromTlist =
214 (isDone == ExprMultipleResult);
215 return result;
216 }
217 }
218 else
219 InstrCountFiltered2(node, 1);
220 }
221
222 /*
223 * Otherwise just return to top of loop for a new outer tuple.
224 */
225 continue;
226 }
227
228 /*
229 * at this point we have a new pair of inner and outer tuples so we
230 * test the inner and outer tuples to see if they satisfy the node's
231 * qualification.
232 *
233 * Only the joinquals determine MatchedOuter status, but all quals
234 * must pass to actually return the tuple.
235 */
236 ENL1_printf("testing qualification");
237
238 if (ExecQual(joinqual, econtext, false))
239 {
240 node->nl_MatchedOuter = true;
241
242 /* In an antijoin, we never return a matched tuple */
243 if (node->js.jointype == JOIN_ANTI)
244 {
245 node->nl_NeedNewOuter = true;
246 continue; /* return to top of loop */
247 }
248
249 /*
250 * In a semijoin, we'll consider returning the first match, but
251 * after that we're done with this outer tuple.
252 */
253 if (node->js.jointype == JOIN_SEMI)
254 node->nl_NeedNewOuter = true;
255
256 if (otherqual == NIL || ExecQual(otherqual, econtext, false))
257 {
258 /*
259 * qualification was satisfied so we project and return the
260 * slot containing the result tuple using ExecProject().
261 */
262 TupleTableSlot *result;
263 ExprDoneCond isDone;
264
265 ENL1_printf("qualification succeeded, projecting tuple");
266
267 result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
268
269 if (isDone != ExprEndResult)
270 {
271 node->js.ps.ps_TupFromTlist =
272 (isDone == ExprMultipleResult);
273 return result;
274 }
275 }
276 else
277 InstrCountFiltered2(node, 1);
278 }
279 else
280 InstrCountFiltered1(node, 1);
281
282 /*
283 * Tuple fails qual, so free per-tuple memory and try again.
284 */
285 ResetExprContext(econtext);
286
287 ENL1_printf("qualification failed, looping");
288 }
289 }
290
291 /* ----------------------------------------------------------------
292 * ExecInitNestLoop
293 * ----------------------------------------------------------------
294 */
295 NestLoopState *
ExecInitNestLoop(NestLoop * node,EState * estate,int eflags)296 ExecInitNestLoop(NestLoop *node, EState *estate, int eflags)
297 {
298 NestLoopState *nlstate;
299
300 /* check for unsupported flags */
301 Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
302
303 NL1_printf("ExecInitNestLoop: %s\n",
304 "initializing node");
305
306 /*
307 * create state structure
308 */
309 nlstate = makeNode(NestLoopState);
310 nlstate->js.ps.plan = (Plan *) node;
311 nlstate->js.ps.state = estate;
312
313 /*
314 * Miscellaneous initialization
315 *
316 * create expression context for node
317 */
318 ExecAssignExprContext(estate, &nlstate->js.ps);
319
320 /*
321 * initialize child expressions
322 */
323 nlstate->js.ps.targetlist = (List *)
324 ExecInitExpr((Expr *) node->join.plan.targetlist,
325 (PlanState *) nlstate);
326 nlstate->js.ps.qual = (List *)
327 ExecInitExpr((Expr *) node->join.plan.qual,
328 (PlanState *) nlstate);
329 nlstate->js.jointype = node->join.jointype;
330 nlstate->js.joinqual = (List *)
331 ExecInitExpr((Expr *) node->join.joinqual,
332 (PlanState *) nlstate);
333
334 /*
335 * initialize child nodes
336 *
337 * If we have no parameters to pass into the inner rel from the outer,
338 * tell the inner child that cheap rescans would be good. If we do have
339 * such parameters, then there is no point in REWIND support at all in the
340 * inner child, because it will always be rescanned with fresh parameter
341 * values.
342 */
343 outerPlanState(nlstate) = ExecInitNode(outerPlan(node), estate, eflags);
344 if (node->nestParams == NIL)
345 eflags |= EXEC_FLAG_REWIND;
346 else
347 eflags &= ~EXEC_FLAG_REWIND;
348 innerPlanState(nlstate) = ExecInitNode(innerPlan(node), estate, eflags);
349
350 /*
351 * tuple table initialization
352 */
353 ExecInitResultTupleSlot(estate, &nlstate->js.ps);
354
355 switch (node->join.jointype)
356 {
357 case JOIN_INNER:
358 case JOIN_SEMI:
359 break;
360 case JOIN_LEFT:
361 case JOIN_ANTI:
362 nlstate->nl_NullInnerTupleSlot =
363 ExecInitNullTupleSlot(estate,
364 ExecGetResultType(innerPlanState(nlstate)));
365 break;
366 default:
367 elog(ERROR, "unrecognized join type: %d",
368 (int) node->join.jointype);
369 }
370
371 /*
372 * initialize tuple type and projection info
373 */
374 ExecAssignResultTypeFromTL(&nlstate->js.ps);
375 ExecAssignProjectionInfo(&nlstate->js.ps, NULL);
376
377 /*
378 * finally, wipe the current outer tuple clean.
379 */
380 nlstate->js.ps.ps_TupFromTlist = false;
381 nlstate->nl_NeedNewOuter = true;
382 nlstate->nl_MatchedOuter = false;
383
384 NL1_printf("ExecInitNestLoop: %s\n",
385 "node initialized");
386
387 return nlstate;
388 }
389
390 /* ----------------------------------------------------------------
391 * ExecEndNestLoop
392 *
393 * closes down scans and frees allocated storage
394 * ----------------------------------------------------------------
395 */
396 void
ExecEndNestLoop(NestLoopState * node)397 ExecEndNestLoop(NestLoopState *node)
398 {
399 NL1_printf("ExecEndNestLoop: %s\n",
400 "ending node processing");
401
402 /*
403 * Free the exprcontext
404 */
405 ExecFreeExprContext(&node->js.ps);
406
407 /*
408 * clean out the tuple table
409 */
410 ExecClearTuple(node->js.ps.ps_ResultTupleSlot);
411
412 /*
413 * close down subplans
414 */
415 ExecEndNode(outerPlanState(node));
416 ExecEndNode(innerPlanState(node));
417
418 NL1_printf("ExecEndNestLoop: %s\n",
419 "node processing ended");
420 }
421
422 /* ----------------------------------------------------------------
423 * ExecReScanNestLoop
424 * ----------------------------------------------------------------
425 */
426 void
ExecReScanNestLoop(NestLoopState * node)427 ExecReScanNestLoop(NestLoopState *node)
428 {
429 PlanState *outerPlan = outerPlanState(node);
430
431 /*
432 * If outerPlan->chgParam is not null then plan will be automatically
433 * re-scanned by first ExecProcNode.
434 */
435 if (outerPlan->chgParam == NULL)
436 ExecReScan(outerPlan);
437
438 /*
439 * innerPlan is re-scanned for each new outer tuple and MUST NOT be
440 * re-scanned from here or you'll get troubles from inner index scans when
441 * outer Vars are used as run-time keys...
442 */
443
444 node->js.ps.ps_TupFromTlist = false;
445 node->nl_NeedNewOuter = true;
446 node->nl_MatchedOuter = false;
447 }
448