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