Age Owner Branch data TLA Line data Source code
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 *
3024 andres@anarazel.de 60 :CBC 1412769 : ExecNestLoop(PlanState *pstate)
61 : : {
62 : 1412769 : 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 : :
3016 73 [ + + ]: 1412769 : CHECK_FOR_INTERRUPTS();
74 : :
75 : : /*
76 : : * get information from the node
77 : : */
78 : : ENL1_printf("getting info from node");
79 : :
5586 tgl@sss.pgh.pa.us 80 : 1412768 : nl = (NestLoop *) node->js.ps.plan;
8362 81 : 1412768 : joinqual = node->js.joinqual;
82 : 1412768 : otherqual = node->js.ps.qual;
83 : 1412768 : outerPlan = outerPlanState(node);
84 : 1412768 : innerPlan = innerPlanState(node);
85 : 1412768 : 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 : : */
9195 91 : 1412768 : 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 : : */
8362 105 [ + + ]: 4035511 : if (node->nl_NeedNewOuter)
106 : : {
107 : : ENL1_printf("getting new outer tuple");
108 : 673561 : outerTupleSlot = ExecProcNode(outerPlan);
109 : :
110 : : /*
111 : : * if there are no more outer tuples, then the join is complete..
112 : : */
10277 bruce@momjian.us 113 [ + + + + ]: 673558 : if (TupIsNull(outerTupleSlot))
114 : : {
115 : : ENL1_printf("no outer tuple, ending join");
116 : 52895 : return NULL;
117 : : }
118 : :
119 : : ENL1_printf("saving new outer tuple information");
9176 tgl@sss.pgh.pa.us 120 : 620663 : econtext->ecxt_outertuple = outerTupleSlot;
8362 121 : 620663 : node->nl_NeedNewOuter = false;
122 : 620663 : 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 : : */
5586 128 [ + + + + : 1250592 : foreach(lc, nl->nestParams)
+ + ]
129 : : {
130 : 629929 : NestLoopParam *nlp = (NestLoopParam *) lfirst(lc);
131 : 629929 : int paramno = nlp->paramno;
132 : : ParamExecData *prm;
133 : :
134 : 629929 : prm = &(econtext->ecxt_param_exec_vals[paramno]);
135 : : /* Param value should be an OUTER_VAR var */
5107 136 [ - + ]: 629929 : Assert(IsA(nlp->paramval, Var));
5130 137 [ - + ]: 629929 : Assert(nlp->paramval->varno == OUTER_VAR);
5586 138 [ - + ]: 629929 : Assert(nlp->paramval->varattno > 0);
139 : 1259858 : prm->value = slot_getattr(outerTupleSlot,
140 : 629929 : nlp->paramval->varattno,
141 : : &(prm->isnull));
142 : : /* Flag parameter value as changed */
143 : 629929 : 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 : 620663 : 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 : :
8362 159 : 3982613 : innerTupleSlot = ExecProcNode(innerPlan);
9176 160 : 3982582 : econtext->ecxt_innertuple = innerTupleSlot;
161 : :
162 [ + + + + ]: 3982582 : if (TupIsNull(innerTupleSlot))
163 : : {
164 : : ENL1_printf("no inner tuple, need new outer tuple");
165 : :
8362 166 : 424343 : node->nl_NeedNewOuter = true;
167 : :
168 [ + + ]: 424343 : if (!node->nl_MatchedOuter &&
6283 169 [ + + ]: 270899 : (node->js.jointype == JOIN_LEFT ||
170 [ + + ]: 257341 : 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 : : */
8362 178 : 51430 : econtext->ecxt_innertuple = node->nl_NullInnerTupleSlot;
179 : :
180 : : ENL1_printf("testing qualification for outer-join tuple");
181 : :
3149 andres@anarazel.de 182 [ + + + + ]: 51430 : 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 : :
3203 191 : 50411 : return ExecProject(node->js.ps.ps_ProjInfo);
192 : : }
193 : : else
5149 tgl@sss.pgh.pa.us 194 [ - + ]: 1019 : InstrCountFiltered2(node, 1);
195 : : }
196 : :
197 : : /*
198 : : * Otherwise just return to top of loop for a new outer tuple.
199 : : */
9176 200 : 373932 : 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 : :
3149 andres@anarazel.de 213 [ + + ]: 3558239 : if (ExecQual(joinqual, econtext))
214 : : {
8362 tgl@sss.pgh.pa.us 215 : 1432824 : node->nl_MatchedOuter = true;
216 : :
217 : : /* In an antijoin, we never return a matched tuple */
6283 218 [ + + ]: 1432824 : if (node->js.jointype == JOIN_ANTI)
219 : : {
220 : 118043 : node->nl_NeedNewOuter = true;
6282 221 : 118043 : 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 : : */
3125 229 [ + + ]: 1314781 : if (node->js.single_match)
6282 230 : 78155 : node->nl_NeedNewOuter = true;
231 : :
3149 andres@anarazel.de 232 [ + + + + ]: 1314781 : 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 : :
3203 240 : 1309428 : return ExecProject(node->js.ps.ps_ProjInfo);
241 : : }
242 : : else
5149 tgl@sss.pgh.pa.us 243 [ - + ]: 5353 : InstrCountFiltered2(node, 1);
244 : : }
245 : : else
246 [ + + ]: 2125415 : InstrCountFiltered1(node, 1);
247 : :
248 : : /*
249 : : * Tuple fails qual, so free per-tuple memory and try again.
250 : : */
9238 251 : 2130768 : ResetExprContext(econtext);
252 : :
253 : : ENL1_printf("qualification failed, looping");
254 : : }
255 : : }
256 : :
257 : : /* ----------------------------------------------------------------
258 : : * ExecInitNestLoop
259 : : * ----------------------------------------------------------------
260 : : */
261 : : NestLoopState *
7181 262 : 50892 : ExecInitNestLoop(NestLoop *node, EState *estate, int eflags)
263 : : {
264 : : NestLoopState *nlstate;
265 : :
266 : : /* check for unsupported flags */
267 [ - + ]: 50892 : 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 : : */
10277 bruce@momjian.us 275 : 50892 : nlstate = makeNode(NestLoopState);
8362 tgl@sss.pgh.pa.us 276 : 50892 : nlstate->js.ps.plan = (Plan *) node;
277 : 50892 : nlstate->js.ps.state = estate;
3024 andres@anarazel.de 278 : 50892 : nlstate->js.ps.ExecProcNode = ExecNestLoop;
279 : :
280 : : /*
281 : : * Miscellaneous initialization
282 : : *
283 : : * create expression context for node
284 : : */
8362 tgl@sss.pgh.pa.us 285 : 50892 : 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 : : */
7181 296 : 50892 : outerPlanState(nlstate) = ExecInitNode(outerPlan(node), estate, eflags);
5586 297 [ + + ]: 50892 : if (node->nestParams == NIL)
298 : 26142 : eflags |= EXEC_FLAG_REWIND;
299 : : else
300 : 24750 : eflags &= ~EXEC_FLAG_REWIND;
301 : 50892 : innerPlanState(nlstate) = ExecInitNode(innerPlan(node), estate, eflags);
302 : :
303 : : /*
304 : : * Initialize result slot, type and projection.
305 : : */
2538 andres@anarazel.de 306 : 50892 : ExecInitResultTupleSlotTL(&nlstate->js.ps, &TTSOpsVirtual);
2810 307 : 50892 : ExecAssignProjectionInfo(&nlstate->js.ps, NULL);
308 : :
309 : : /*
310 : : * initialize child expressions
311 : : */
312 : 50892 : nlstate->js.ps.qual =
313 : 50892 : ExecInitQual(node->join.plan.qual, (PlanState *) nlstate);
314 : 50892 : nlstate->js.jointype = node->join.jointype;
315 : 50892 : nlstate->js.joinqual =
316 : 50892 : ExecInitQual(node->join.joinqual, (PlanState *) nlstate);
317 : :
318 : : /*
319 : : * detect whether we need only consider the first matching inner tuple
320 : : */
3125 tgl@sss.pgh.pa.us 321 [ + + ]: 74374 : nlstate->js.single_match = (node->join.inner_unique ||
322 [ + + ]: 23482 : node->join.jointype == JOIN_SEMI);
323 : :
324 : : /* set up null tuples for outer joins, if needed */
9176 325 [ + + - ]: 50892 : switch (node->join.jointype)
326 : : {
327 : 39577 : case JOIN_INNER:
328 : : case JOIN_SEMI:
329 : 39577 : break;
330 : 11315 : case JOIN_LEFT:
331 : : case JOIN_ANTI:
332 : 11315 : nlstate->nl_NullInnerTupleSlot =
333 : 11315 : ExecInitNullTupleSlot(estate,
2538 andres@anarazel.de 334 :ECB (11200) : ExecGetResultType(innerPlanState(nlstate)),
335 : : &TTSOpsVirtual);
9176 tgl@sss.pgh.pa.us 336 :CBC 11315 : break;
9176 tgl@sss.pgh.pa.us 337 :UBC 0 : default:
8134 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 : : */
9176 tgl@sss.pgh.pa.us 345 :CBC 50892 : nlstate->nl_NeedNewOuter = true;
346 : 50892 : nlstate->nl_MatchedOuter = false;
347 : :
348 : : NL1_printf("ExecInitNestLoop: %s\n",
349 : : "node initialized");
350 : :
8362 351 : 50892 : return nlstate;
352 : : }
353 : :
354 : : /* ----------------------------------------------------------------
355 : : * ExecEndNestLoop
356 : : *
357 : : * closes down scans and frees allocated storage
358 : : * ----------------------------------------------------------------
359 : : */
360 : : void
361 : 50765 : ExecEndNestLoop(NestLoopState *node)
362 : : {
363 : : NL1_printf("ExecEndNestLoop: %s\n",
364 : : "ending node processing");
365 : :
366 : : /*
367 : : * close down subplans
368 : : */
8352 369 : 50765 : ExecEndNode(outerPlanState(node));
370 : 50765 : ExecEndNode(innerPlanState(node));
371 : :
372 : : NL1_printf("ExecEndNestLoop: %s\n",
373 : : "node processing ended");
10702 scrappy@hub.org 374 : 50765 : }
375 : :
376 : : /* ----------------------------------------------------------------
377 : : * ExecReScanNestLoop
378 : : * ----------------------------------------------------------------
379 : : */
380 : : void
5586 tgl@sss.pgh.pa.us 381 : 6733 : ExecReScanNestLoop(NestLoopState *node)
382 : : {
8120 bruce@momjian.us 383 : 6733 : 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 : : */
10118 vadim4o@yahoo.com 389 [ + + ]: 6733 : if (outerPlan->chgParam == NULL)
5586 tgl@sss.pgh.pa.us 390 : 350 : 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 : :
8362 398 : 6733 : node->nl_NeedNewOuter = true;
399 : 6733 : node->nl_MatchedOuter = false;
10118 vadim4o@yahoo.com 400 : 6733 : }
|
