Debian Codegraph @

src/backend/executor/nodeNestloop.c

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