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-2026, 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/instrument.h"
26 : : #include "executor/nodeNestloop.h"
27 : : #include "miscadmin.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 *
3239 andres@anarazel.de 61 :CBC 1995001 : ExecNestLoop(PlanState *pstate)
62 : : {
63 : 1995001 : 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 : :
3231 74 [ + + ]: 1995001 : CHECK_FOR_INTERRUPTS();
75 : :
76 : : /*
77 : : * get information from the node
78 : : */
79 : : ENL1_printf("getting info from node");
80 : :
5801 tgl@sss.pgh.pa.us 81 : 1995000 : nl = (NestLoop *) node->js.ps.plan;
8577 82 : 1995000 : joinqual = node->js.joinqual;
83 : 1995000 : otherqual = node->js.ps.qual;
84 : 1995000 : outerPlan = outerPlanState(node);
85 : 1995000 : innerPlan = innerPlanState(node);
86 : 1995000 : 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 : : */
9410 92 : 1995000 : 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 : : */
8577 106 [ + + ]: 7215012 : if (node->nl_NeedNewOuter)
107 : : {
108 : : ENL1_printf("getting new outer tuple");
109 : 1034392 : outerTupleSlot = ExecProcNode(outerPlan);
110 : :
111 : : /*
112 : : * if there are no more outer tuples, then the join is complete..
113 : : */
10492 bruce@momjian.us 114 [ + + + + ]: 1034388 : if (TupIsNull(outerTupleSlot))
115 : : {
116 : : ENL1_printf("no outer tuple, ending join");
117 : 71485 : return NULL;
118 : : }
119 : :
120 : : ENL1_printf("saving new outer tuple information");
9391 tgl@sss.pgh.pa.us 121 : 962903 : econtext->ecxt_outertuple = outerTupleSlot;
8577 122 : 962903 : node->nl_NeedNewOuter = false;
123 : 962903 : 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 : : */
5801 129 [ + + + + : 1971039 : foreach(lc, nl->nestParams)
+ + ]
130 : : {
131 : 1008136 : NestLoopParam *nlp = (NestLoopParam *) lfirst(lc);
132 : 1008136 : int paramno = nlp->paramno;
133 : : ParamExecData *prm;
134 : :
135 : 1008136 : prm = &(econtext->ecxt_param_exec_vals[paramno]);
136 : : /* Param value should be an OUTER_VAR var */
5322 137 [ - + ]: 1008136 : Assert(IsA(nlp->paramval, Var));
5345 138 [ - + ]: 1008136 : Assert(nlp->paramval->varno == OUTER_VAR);
5801 139 [ - + ]: 1008136 : Assert(nlp->paramval->varattno > 0);
140 : 2016272 : prm->value = slot_getattr(outerTupleSlot,
141 : 1008136 : nlp->paramval->varattno,
142 : : &(prm->isnull));
143 : : /* Flag parameter value as changed */
144 : 1008136 : 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 : 962903 : 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 : :
8577 160 : 7143523 : innerTupleSlot = ExecProcNode(innerPlan);
9391 161 : 7143489 : econtext->ecxt_innertuple = innerTupleSlot;
162 : :
163 [ + + + + ]: 7143489 : if (TupIsNull(innerTupleSlot))
164 : : {
165 : : ENL1_printf("no inner tuple, need new outer tuple");
166 : :
8577 167 : 553518 : node->nl_NeedNewOuter = true;
168 : :
169 [ + + ]: 553518 : if (!node->nl_MatchedOuter &&
6498 170 [ + + ]: 349773 : (node->js.jointype == JOIN_LEFT ||
171 [ + + ]: 335300 : 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 : : */
8577 179 : 58258 : econtext->ecxt_innertuple = node->nl_NullInnerTupleSlot;
180 : :
181 : : ENL1_printf("testing qualification for outer-join tuple");
182 : :
3364 andres@anarazel.de 183 [ + + + + ]: 58258 : 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 : :
3418 192 : 57284 : return ExecProject(node->js.ps.ps_ProjInfo);
193 : : }
194 : : else
5364 tgl@sss.pgh.pa.us 195 [ - + ]: 974 : InstrCountFiltered2(node, 1);
196 : : }
197 : :
198 : : /*
199 : : * Otherwise just return to top of loop for a new outer tuple.
200 : : */
9391 201 : 496234 : 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 : :
3364 andres@anarazel.de 214 [ + + ]: 6589971 : if (ExecQual(joinqual, econtext))
215 : : {
8577 tgl@sss.pgh.pa.us 216 : 2103313 : node->nl_MatchedOuter = true;
217 : :
218 : : /* In an antijoin, we never return a matched tuple */
6498 219 [ + + ]: 2103313 : if (node->js.jointype == JOIN_ANTI)
220 : : {
221 : 230047 : node->nl_NeedNewOuter = true;
6497 222 : 230047 : 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 : : */
3340 230 [ + + ]: 1873266 : if (node->js.single_match)
6497 231 : 179202 : node->nl_NeedNewOuter = true;
232 : :
3364 andres@anarazel.de 233 [ + + + + ]: 1873266 : 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 : :
3418 241 : 1866193 : return ExecProject(node->js.ps.ps_ProjInfo);
242 : : }
243 : : else
5364 tgl@sss.pgh.pa.us 244 [ - + ]: 7073 : InstrCountFiltered2(node, 1);
245 : : }
246 : : else
247 [ + + ]: 4486658 : InstrCountFiltered1(node, 1);
248 : :
249 : : /*
250 : : * Tuple fails qual, so free per-tuple memory and try again.
251 : : */
9453 252 : 4493731 : ResetExprContext(econtext);
253 : :
254 : : ENL1_printf("qualification failed, looping");
255 : : }
256 : : }
257 : :
258 : : /* ----------------------------------------------------------------
259 : : * ExecInitNestLoop
260 : : * ----------------------------------------------------------------
261 : : */
262 : : NestLoopState *
7396 263 : 69319 : ExecInitNestLoop(NestLoop *node, EState *estate, int eflags)
264 : : {
265 : : NestLoopState *nlstate;
266 : :
267 : : /* check for unsupported flags */
268 [ - + ]: 69319 : 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 : : */
10492 bruce@momjian.us 276 : 69319 : nlstate = makeNode(NestLoopState);
8577 tgl@sss.pgh.pa.us 277 : 69319 : nlstate->js.ps.plan = (Plan *) node;
278 : 69319 : nlstate->js.ps.state = estate;
3239 andres@anarazel.de 279 : 69319 : nlstate->js.ps.ExecProcNode = ExecNestLoop;
280 : :
281 : : /*
282 : : * Miscellaneous initialization
283 : : *
284 : : * create expression context for node
285 : : */
8577 tgl@sss.pgh.pa.us 286 : 69319 : 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 : : */
7396 297 : 69319 : outerPlanState(nlstate) = ExecInitNode(outerPlan(node), estate, eflags);
5801 298 [ + + ]: 69319 : if (node->nestParams == NIL)
299 : 36703 : eflags |= EXEC_FLAG_REWIND;
300 : : else
301 : 32616 : eflags &= ~EXEC_FLAG_REWIND;
302 : 69319 : innerPlanState(nlstate) = ExecInitNode(innerPlan(node), estate, eflags);
303 : :
304 : : /*
305 : : * Initialize result slot, type and projection.
306 : : */
2753 andres@anarazel.de 307 : 69319 : ExecInitResultTupleSlotTL(&nlstate->js.ps, &TTSOpsVirtual);
3025 308 : 69319 : ExecAssignProjectionInfo(&nlstate->js.ps, NULL);
309 : :
310 : : /*
311 : : * initialize child expressions
312 : : */
313 : 69319 : nlstate->js.ps.qual =
314 : 69319 : ExecInitQual(node->join.plan.qual, (PlanState *) nlstate);
315 : 69319 : nlstate->js.jointype = node->join.jointype;
316 : 69319 : nlstate->js.joinqual =
317 : 69319 : ExecInitQual(node->join.joinqual, (PlanState *) nlstate);
318 : :
319 : : /*
320 : : * detect whether we need only consider the first matching inner tuple
321 : : */
3340 tgl@sss.pgh.pa.us 322 [ + + ]: 98957 : nlstate->js.single_match = (node->join.inner_unique ||
323 [ + + ]: 29638 : node->join.jointype == JOIN_SEMI);
324 : :
325 : : /* set up null tuples for outer joins, if needed */
9391 326 [ + + - ]: 69319 : switch (node->join.jointype)
327 : : {
328 : 53035 : case JOIN_INNER:
329 : : case JOIN_SEMI:
330 : 53035 : break;
331 : 16284 : case JOIN_LEFT:
332 : : case JOIN_ANTI:
333 : 16284 : nlstate->nl_NullInnerTupleSlot =
334 : 16284 : ExecInitNullTupleSlot(estate,
2753 andres@anarazel.de 335 :ECB (11258) : ExecGetResultType(innerPlanState(nlstate)),
336 : : &TTSOpsVirtual);
9391 tgl@sss.pgh.pa.us 337 :CBC 16284 : break;
9391 tgl@sss.pgh.pa.us 338 :UBC 0 : default:
8349 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 : : */
9391 tgl@sss.pgh.pa.us 346 :CBC 69319 : nlstate->nl_NeedNewOuter = true;
347 : 69319 : nlstate->nl_MatchedOuter = false;
348 : :
349 : : NL1_printf("ExecInitNestLoop: %s\n",
350 : : "node initialized");
351 : :
8577 352 : 69319 : return nlstate;
353 : : }
354 : :
355 : : /* ----------------------------------------------------------------
356 : : * ExecEndNestLoop
357 : : *
358 : : * closes down scans and frees allocated storage
359 : : * ----------------------------------------------------------------
360 : : */
361 : : void
362 : 69173 : ExecEndNestLoop(NestLoopState *node)
363 : : {
364 : : NL1_printf("ExecEndNestLoop: %s\n",
365 : : "ending node processing");
366 : :
367 : : /*
368 : : * close down subplans
369 : : */
8567 370 : 69173 : ExecEndNode(outerPlanState(node));
371 : 69173 : ExecEndNode(innerPlanState(node));
372 : :
373 : : NL1_printf("ExecEndNestLoop: %s\n",
374 : : "node processing ended");
10917 scrappy@hub.org 375 : 69173 : }
376 : :
377 : : /* ----------------------------------------------------------------
378 : : * ExecReScanNestLoop
379 : : * ----------------------------------------------------------------
380 : : */
381 : : void
5801 tgl@sss.pgh.pa.us 382 : 9149 : ExecReScanNestLoop(NestLoopState *node)
383 : : {
8335 bruce@momjian.us 384 : 9149 : PlanState *outerPlan = outerPlanState(node);
385 : :
386 : : /*
387 : : * If outerPlan->chgParam is not null then plan will be automatically
388 : : * re-scanned by first ExecProcNode.
389 : : */
10333 vadim4o@yahoo.com 390 [ + + ]: 9149 : if (outerPlan->chgParam == NULL)
5801 tgl@sss.pgh.pa.us 391 : 185 : ExecReScan(outerPlan);
392 : :
393 : : /*
394 : : * innerPlan is re-scanned for each new outer tuple and MUST NOT be
395 : : * re-scanned from here or you'll get troubles from inner index scans when
396 : : * outer Vars are used as run-time keys...
397 : : */
398 : :
8577 399 : 9149 : node->nl_NeedNewOuter = true;
400 : 9149 : node->nl_MatchedOuter = false;
10333 vadim4o@yahoo.com 401 : 9149 : }
|
