Age Owner TLA Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * nodeNestloop.c
4 : * routines to support nest-loop joins
5 : *
6 : * Portions Copyright (c) 1996-2023, 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 *
2092 andres 61 CBC 1391519 : ExecNestLoop(PlanState *pstate)
62 : {
63 1391519 : 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 :
2084 74 1391519 : CHECK_FOR_INTERRUPTS();
75 :
76 : /*
77 : * get information from the node
78 : */
79 : ENL1_printf("getting info from node");
80 :
4654 tgl 81 1391519 : nl = (NestLoop *) node->js.ps.plan;
7430 82 1391519 : joinqual = node->js.joinqual;
83 1391519 : otherqual = node->js.ps.qual;
84 1391519 : outerPlan = outerPlanState(node);
85 1391519 : innerPlan = innerPlanState(node);
86 1391519 : 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 : */
8263 92 1391519 : 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 : */
7430 106 5001986 : if (node->nl_NeedNewOuter)
107 : {
108 : ENL1_printf("getting new outer tuple");
109 641887 : outerTupleSlot = ExecProcNode(outerPlan);
110 :
111 : /*
112 : * if there are no more outer tuples, then the join is complete..
113 : */
9345 bruce 114 641887 : if (TupIsNull(outerTupleSlot))
115 : {
116 : ENL1_printf("no outer tuple, ending join");
117 36348 : return NULL;
118 : }
119 :
120 : ENL1_printf("saving new outer tuple information");
8244 tgl 121 605539 : econtext->ecxt_outertuple = outerTupleSlot;
7430 122 605539 : node->nl_NeedNewOuter = false;
123 605539 : 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 : */
4654 129 955039 : foreach(lc, nl->nestParams)
130 : {
131 349500 : NestLoopParam *nlp = (NestLoopParam *) lfirst(lc);
132 349500 : int paramno = nlp->paramno;
133 : ParamExecData *prm;
134 :
135 349500 : prm = &(econtext->ecxt_param_exec_vals[paramno]);
136 : /* Param value should be an OUTER_VAR var */
4175 137 349500 : Assert(IsA(nlp->paramval, Var));
4198 138 349500 : Assert(nlp->paramval->varno == OUTER_VAR);
4654 139 349500 : Assert(nlp->paramval->varattno > 0);
140 699000 : prm->value = slot_getattr(outerTupleSlot,
141 349500 : nlp->paramval->varattno,
142 : &(prm->isnull));
143 : /* Flag parameter value as changed */
144 349500 : 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 605539 : 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 :
7430 160 4965638 : innerTupleSlot = ExecProcNode(innerPlan);
8244 161 4965613 : econtext->ecxt_innertuple = innerTupleSlot;
162 :
163 4965613 : if (TupIsNull(innerTupleSlot))
164 : {
165 : ENL1_printf("no inner tuple, need new outer tuple");
166 :
7430 167 546278 : node->nl_NeedNewOuter = true;
168 :
169 546278 : if (!node->nl_MatchedOuter &&
5351 170 421129 : (node->js.jointype == JOIN_LEFT ||
171 410850 : 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 : */
7430 179 247603 : econtext->ecxt_innertuple = node->nl_NullInnerTupleSlot;
180 :
181 : ENL1_printf("testing qualification for outer-join tuple");
182 :
2217 andres 183 247603 : 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 :
2271 192 246945 : return ExecProject(node->js.ps.ps_ProjInfo);
193 : }
194 : else
4217 tgl 195 658 : InstrCountFiltered2(node, 1);
196 : }
197 :
198 : /*
199 : * Otherwise just return to top of loop for a new outer tuple.
200 : */
8244 201 299333 : 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 :
2217 andres 214 4419335 : if (ExecQual(joinqual, econtext))
215 : {
7430 tgl 216 1119684 : node->nl_MatchedOuter = true;
217 :
218 : /* In an antijoin, we never return a matched tuple */
5351 219 1119684 : if (node->js.jointype == JOIN_ANTI)
220 : {
221 6127 : node->nl_NeedNewOuter = true;
5350 222 6127 : 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 : */
2193 230 1113557 : if (node->js.single_match)
5350 231 53034 : node->nl_NeedNewOuter = true;
232 :
2217 andres 233 1113557 : 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 :
2271 241 1108201 : return ExecProject(node->js.ps.ps_ProjInfo);
242 : }
243 : else
4217 tgl 244 5356 : InstrCountFiltered2(node, 1);
245 : }
246 : else
247 3299651 : InstrCountFiltered1(node, 1);
248 :
249 : /*
250 : * Tuple fails qual, so free per-tuple memory and try again.
251 : */
8306 252 3305007 : ResetExprContext(econtext);
253 :
254 : ENL1_printf("qualification failed, looping");
255 : }
256 : }
257 :
258 : /* ----------------------------------------------------------------
259 : * ExecInitNestLoop
260 : * ----------------------------------------------------------------
261 : */
262 : NestLoopState *
6249 263 34217 : ExecInitNestLoop(NestLoop *node, EState *estate, int eflags)
264 : {
265 : NestLoopState *nlstate;
266 :
267 : /* check for unsupported flags */
268 34217 : 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 : */
9345 bruce 276 34217 : nlstate = makeNode(NestLoopState);
7430 tgl 277 34217 : nlstate->js.ps.plan = (Plan *) node;
278 34217 : nlstate->js.ps.state = estate;
2092 andres 279 34217 : nlstate->js.ps.ExecProcNode = ExecNestLoop;
280 :
281 : /*
282 : * Miscellaneous initialization
283 : *
284 : * create expression context for node
285 : */
7430 tgl 286 34217 : ExecAssignExprContext(estate, &nlstate->js.ps);
287 :
288 : /*
289 : * initialize child nodes
290 : *
291 : * If we have no parameters to pass into the inner rel from the outer,
292 : * tell the inner child that cheap rescans would be good. If we do have
293 : * such parameters, then there is no point in REWIND support at all in the
294 : * inner child, because it will always be rescanned with fresh parameter
295 : * values.
296 : */
6249 297 34217 : outerPlanState(nlstate) = ExecInitNode(outerPlan(node), estate, eflags);
4654 298 34217 : if (node->nestParams == NIL)
299 17181 : eflags |= EXEC_FLAG_REWIND;
300 : else
301 17036 : eflags &= ~EXEC_FLAG_REWIND;
302 34217 : innerPlanState(nlstate) = ExecInitNode(innerPlan(node), estate, eflags);
303 :
304 : /*
305 : * Initialize result slot, type and projection.
306 : */
1606 andres 307 34217 : ExecInitResultTupleSlotTL(&nlstate->js.ps, &TTSOpsVirtual);
1878 308 34217 : ExecAssignProjectionInfo(&nlstate->js.ps, NULL);
309 :
310 : /*
311 : * initialize child expressions
312 : */
313 34217 : nlstate->js.ps.qual =
314 34217 : ExecInitQual(node->join.plan.qual, (PlanState *) nlstate);
315 34217 : nlstate->js.jointype = node->join.jointype;
316 34217 : nlstate->js.joinqual =
317 34217 : ExecInitQual(node->join.joinqual, (PlanState *) nlstate);
318 :
319 : /*
320 : * detect whether we need only consider the first matching inner tuple
321 : */
2193 tgl 322 52035 : nlstate->js.single_match = (node->join.inner_unique ||
323 17818 : node->join.jointype == JOIN_SEMI);
324 :
325 : /* set up null tuples for outer joins, if needed */
8244 326 34217 : switch (node->join.jointype)
327 : {
328 24727 : case JOIN_INNER:
329 : case JOIN_SEMI:
330 24727 : break;
331 9490 : case JOIN_LEFT:
332 : case JOIN_ANTI:
333 9490 : nlstate->nl_NullInnerTupleSlot =
334 9490 : ExecInitNullTupleSlot(estate,
1606 andres 335 9490 : ExecGetResultType(innerPlanState(nlstate)),
336 : &TTSOpsVirtual);
8244 tgl 337 9490 : break;
8244 tgl 338 UBC 0 : default:
7202 339 0 : elog(ERROR, "unrecognized join type: %d",
340 : (int) node->join.jointype);
341 : }
342 :
343 : /*
344 : * finally, wipe the current outer tuple clean.
345 : */
8244 tgl 346 CBC 34217 : nlstate->nl_NeedNewOuter = true;
347 34217 : nlstate->nl_MatchedOuter = false;
348 :
349 : NL1_printf("ExecInitNestLoop: %s\n",
350 : "node initialized");
351 :
7430 352 34217 : return nlstate;
353 : }
354 :
355 : /* ----------------------------------------------------------------
356 : * ExecEndNestLoop
357 : *
358 : * closes down scans and frees allocated storage
359 : * ----------------------------------------------------------------
360 : */
361 : void
362 34120 : ExecEndNestLoop(NestLoopState *node)
363 : {
364 : NL1_printf("ExecEndNestLoop: %s\n",
365 : "ending node processing");
366 :
367 : /*
368 : * Free the exprcontext
369 : */
370 34120 : ExecFreeExprContext(&node->js.ps);
371 :
372 : /*
373 : * clean out the tuple table
374 : */
7420 375 34120 : ExecClearTuple(node->js.ps.ps_ResultTupleSlot);
376 :
377 : /*
378 : * close down subplans
379 : */
380 34120 : ExecEndNode(outerPlanState(node));
381 34120 : ExecEndNode(innerPlanState(node));
382 :
383 : NL1_printf("ExecEndNestLoop: %s\n",
384 : "node processing ended");
9770 scrappy 385 34120 : }
386 :
387 : /* ----------------------------------------------------------------
388 : * ExecReScanNestLoop
389 : * ----------------------------------------------------------------
390 : */
391 : void
4654 tgl 392 5323 : ExecReScanNestLoop(NestLoopState *node)
393 : {
7188 bruce 394 5323 : PlanState *outerPlan = outerPlanState(node);
395 :
396 : /*
397 : * If outerPlan->chgParam is not null then plan will be automatically
398 : * re-scanned by first ExecProcNode.
399 : */
9186 vadim4o 400 5323 : if (outerPlan->chgParam == NULL)
4654 tgl 401 260 : ExecReScan(outerPlan);
402 :
403 : /*
404 : * innerPlan is re-scanned for each new outer tuple and MUST NOT be
405 : * re-scanned from here or you'll get troubles from inner index scans when
406 : * outer Vars are used as run-time keys...
407 : */
408 :
7430 409 5323 : node->nl_NeedNewOuter = true;
410 5323 : node->nl_MatchedOuter = false;
9186 vadim4o 411 5323 : }
|
