Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * nodeNestloop.c
4 : * routines to support nest-loop joins
5 : *
6 : * Portions Copyright (c) 1996-2024, 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 3143948 : ExecNestLoop(PlanState *pstate)
61 : {
62 3143948 : 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 3143948 : CHECK_FOR_INTERRUPTS();
74 :
75 : /*
76 : * get information from the node
77 : */
78 : ENL1_printf("getting info from node");
79 :
80 3143946 : nl = (NestLoop *) node->js.ps.plan;
81 3143946 : joinqual = node->js.joinqual;
82 3143946 : otherqual = node->js.ps.qual;
83 3143946 : outerPlan = outerPlanState(node);
84 3143946 : innerPlan = innerPlanState(node);
85 3143946 : 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 3143946 : 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 7682182 : if (node->nl_NeedNewOuter)
106 : {
107 : ENL1_printf("getting new outer tuple");
108 1021138 : outerTupleSlot = ExecProcNode(outerPlan);
109 :
110 : /*
111 : * if there are no more outer tuples, then the join is complete..
112 : */
113 1021132 : if (TupIsNull(outerTupleSlot))
114 : {
115 : ENL1_printf("no outer tuple, ending join");
116 89382 : return NULL;
117 : }
118 :
119 : ENL1_printf("saving new outer tuple information");
120 931750 : econtext->ecxt_outertuple = outerTupleSlot;
121 931750 : node->nl_NeedNewOuter = false;
122 931750 : 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 1757188 : foreach(lc, nl->nestParams)
129 : {
130 825438 : NestLoopParam *nlp = (NestLoopParam *) lfirst(lc);
131 825438 : int paramno = nlp->paramno;
132 : ParamExecData *prm;
133 :
134 825438 : 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 1650876 : prm->value = slot_getattr(outerTupleSlot,
140 825438 : nlp->paramval->varattno,
141 : &(prm->isnull));
142 : /* Flag parameter value as changed */
143 825438 : 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 931750 : 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 7592794 : innerTupleSlot = ExecProcNode(innerPlan);
160 7592732 : econtext->ecxt_innertuple = innerTupleSlot;
161 :
162 7592732 : if (TupIsNull(innerTupleSlot))
163 : {
164 : ENL1_printf("no inner tuple, need new outer tuple");
165 :
166 773708 : node->nl_NeedNewOuter = true;
167 :
168 773708 : if (!node->nl_MatchedOuter &&
169 487150 : (node->js.jointype == JOIN_LEFT ||
170 454774 : 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 99890 : econtext->ecxt_innertuple = node->nl_NullInnerTupleSlot;
179 :
180 : ENL1_printf("testing qualification for outer-join tuple");
181 :
182 99890 : 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 97822 : return ExecProject(node->js.ps.ps_ProjInfo);
192 : }
193 : else
194 2068 : InstrCountFiltered2(node, 1);
195 : }
196 :
197 : /*
198 : * Otherwise just return to top of loop for a new outer tuple.
199 : */
200 675886 : 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 6819024 : if (ExecQual(joinqual, econtext))
214 : {
215 2983590 : node->nl_MatchedOuter = true;
216 :
217 : /* In an antijoin, we never return a matched tuple */
218 2983590 : if (node->js.jointype == JOIN_ANTI)
219 : {
220 15658 : node->nl_NeedNewOuter = true;
221 15658 : 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 2967932 : if (node->js.single_match)
230 142158 : node->nl_NeedNewOuter = true;
231 :
232 2967932 : 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 2956674 : return ExecProject(node->js.ps.ps_ProjInfo);
241 : }
242 : else
243 11258 : InstrCountFiltered2(node, 1);
244 : }
245 : else
246 3835434 : InstrCountFiltered1(node, 1);
247 :
248 : /*
249 : * Tuple fails qual, so free per-tuple memory and try again.
250 : */
251 3846692 : ResetExprContext(econtext);
252 :
253 : ENL1_printf("qualification failed, looping");
254 : }
255 : }
256 :
257 : /* ----------------------------------------------------------------
258 : * ExecInitNestLoop
259 : * ----------------------------------------------------------------
260 : */
261 : NestLoopState *
262 85458 : 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 85458 : nlstate = makeNode(NestLoopState);
276 85458 : nlstate->js.ps.plan = (Plan *) node;
277 85458 : nlstate->js.ps.state = estate;
278 85458 : nlstate->js.ps.ExecProcNode = ExecNestLoop;
279 :
280 : /*
281 : * Miscellaneous initialization
282 : *
283 : * create expression context for node
284 : */
285 85458 : 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 85458 : outerPlanState(nlstate) = ExecInitNode(outerPlan(node), estate, eflags);
297 85458 : if (node->nestParams == NIL)
298 42802 : eflags |= EXEC_FLAG_REWIND;
299 : else
300 42656 : eflags &= ~EXEC_FLAG_REWIND;
301 85458 : innerPlanState(nlstate) = ExecInitNode(innerPlan(node), estate, eflags);
302 :
303 : /*
304 : * Initialize result slot, type and projection.
305 : */
306 85458 : ExecInitResultTupleSlotTL(&nlstate->js.ps, &TTSOpsVirtual);
307 85458 : ExecAssignProjectionInfo(&nlstate->js.ps, NULL);
308 :
309 : /*
310 : * initialize child expressions
311 : */
312 85458 : nlstate->js.ps.qual =
313 85458 : ExecInitQual(node->join.plan.qual, (PlanState *) nlstate);
314 85458 : nlstate->js.jointype = node->join.jointype;
315 85458 : nlstate->js.joinqual =
316 85458 : ExecInitQual(node->join.joinqual, (PlanState *) nlstate);
317 :
318 : /*
319 : * detect whether we need only consider the first matching inner tuple
320 : */
321 128926 : nlstate->js.single_match = (node->join.inner_unique ||
322 43468 : node->join.jointype == JOIN_SEMI);
323 :
324 : /* set up null tuples for outer joins, if needed */
325 85458 : switch (node->join.jointype)
326 : {
327 67398 : case JOIN_INNER:
328 : case JOIN_SEMI:
329 67398 : break;
330 18060 : case JOIN_LEFT:
331 : case JOIN_ANTI:
332 18060 : nlstate->nl_NullInnerTupleSlot =
333 18060 : ExecInitNullTupleSlot(estate,
334 18060 : ExecGetResultType(innerPlanState(nlstate)),
335 : &TTSOpsVirtual);
336 18060 : break;
337 0 : default:
338 0 : elog(ERROR, "unrecognized join type: %d",
339 : (int) node->join.jointype);
340 : }
341 :
342 : /*
343 : * finally, wipe the current outer tuple clean.
344 : */
345 85458 : nlstate->nl_NeedNewOuter = true;
346 85458 : nlstate->nl_MatchedOuter = false;
347 :
348 : NL1_printf("ExecInitNestLoop: %s\n",
349 : "node initialized");
350 :
351 85458 : return nlstate;
352 : }
353 :
354 : /* ----------------------------------------------------------------
355 : * ExecEndNestLoop
356 : *
357 : * closes down scans and frees allocated storage
358 : * ----------------------------------------------------------------
359 : */
360 : void
361 85210 : ExecEndNestLoop(NestLoopState *node)
362 : {
363 : NL1_printf("ExecEndNestLoop: %s\n",
364 : "ending node processing");
365 :
366 : /*
367 : * close down subplans
368 : */
369 85210 : ExecEndNode(outerPlanState(node));
370 85210 : ExecEndNode(innerPlanState(node));
371 :
372 : NL1_printf("ExecEndNestLoop: %s\n",
373 : "node processing ended");
374 85210 : }
375 :
376 : /* ----------------------------------------------------------------
377 : * ExecReScanNestLoop
378 : * ----------------------------------------------------------------
379 : */
380 : void
381 11950 : ExecReScanNestLoop(NestLoopState *node)
382 : {
383 11950 : 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 11950 : if (outerPlan->chgParam == NULL)
390 608 : 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 11950 : node->nl_NeedNewOuter = true;
399 11950 : node->nl_MatchedOuter = false;
400 11950 : }
|
