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/executor.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 *
3328 andres@anarazel.de 61 :CBC 1947228 : ExecNestLoop(PlanState *pstate)
62 : : {
63 : 1947228 : 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 : :
3320 74 [ + + ]: 1947228 : CHECK_FOR_INTERRUPTS();
75 : :
76 : : /*
77 : : * get information from the node
78 : : */
5890 tgl@sss.pgh.pa.us 79 : 1947227 : nl = (NestLoop *) node->js.ps.plan;
8666 80 : 1947227 : joinqual = node->js.joinqual;
81 : 1947227 : otherqual = node->js.ps.qual;
82 : 1947227 : outerPlan = outerPlanState(node);
83 : 1947227 : innerPlan = innerPlanState(node);
84 : 1947227 : econtext = node->js.ps.ps_ExprContext;
85 : :
86 : : /*
87 : : * Reset per-tuple memory context to free any expression evaluation
88 : : * storage allocated in the previous tuple cycle.
89 : : */
9499 90 : 1947227 : ResetExprContext(econtext);
91 : :
92 : : /*
93 : : * Ok, everything is setup for the join so now loop until we return a
94 : : * qualifying join tuple.
95 : : */
96 : : for (;;)
97 : : {
98 : : /*
99 : : * If we don't have an outer tuple, get the next one and reset the
100 : : * inner scan.
101 : : */
8666 102 [ + + ]: 6957930 : if (node->nl_NeedNewOuter)
103 : : {
104 : 953948 : outerTupleSlot = ExecProcNode(outerPlan);
105 : :
106 : : /*
107 : : * if there are no more outer tuples, then the join is complete..
108 : : */
10581 bruce@momjian.us 109 [ + + + + ]: 953944 : if (TupIsNull(outerTupleSlot))
110 : 67289 : return NULL;
111 : :
9480 tgl@sss.pgh.pa.us 112 : 886655 : econtext->ecxt_outertuple = outerTupleSlot;
8666 113 : 886655 : node->nl_NeedNewOuter = false;
114 : 886655 : node->nl_MatchedOuter = false;
115 : :
116 : : /*
117 : : * fetch the values of any outer Vars that must be passed to the
118 : : * inner scan, and store them in the appropriate PARAM_EXEC slots.
119 : : */
5890 120 [ + + + + : 1828786 : foreach(lc, nl->nestParams)
+ + ]
121 : : {
122 : 942131 : NestLoopParam *nlp = (NestLoopParam *) lfirst(lc);
123 : 942131 : int paramno = nlp->paramno;
124 : : ParamExecData *prm;
125 : :
126 : 942131 : prm = &(econtext->ecxt_param_exec_vals[paramno]);
127 : : /* Param value should be an OUTER_VAR var */
5411 128 [ - + ]: 942131 : Assert(IsA(nlp->paramval, Var));
5434 129 [ - + ]: 942131 : Assert(nlp->paramval->varno == OUTER_VAR);
5890 130 [ - + ]: 942131 : Assert(nlp->paramval->varattno > 0);
131 : 1884262 : prm->value = slot_getattr(outerTupleSlot,
132 : 942131 : nlp->paramval->varattno,
133 : : &(prm->isnull));
134 : : /* Flag parameter value as changed */
135 : 942131 : innerPlan->chgParam = bms_add_member(innerPlan->chgParam,
136 : : paramno);
137 : : }
138 : :
139 : : /*
140 : : * now rescan the inner plan
141 : : */
142 : 886655 : ExecReScan(innerPlan);
143 : : }
144 : :
145 : : /*
146 : : * we have an outerTuple, try to get the next inner tuple.
147 : : */
8666 148 : 6890637 : innerTupleSlot = ExecProcNode(innerPlan);
9480 149 : 6890603 : econtext->ecxt_innertuple = innerTupleSlot;
150 : :
151 [ + + + + ]: 6890603 : if (TupIsNull(innerTupleSlot))
152 : : {
8666 153 : 554135 : node->nl_NeedNewOuter = true;
154 : :
155 [ + + ]: 554135 : if (!node->nl_MatchedOuter &&
6587 156 [ + + ]: 346561 : (node->js.jointype == JOIN_LEFT ||
157 [ + + ]: 332172 : node->js.jointype == JOIN_ANTI))
158 : : {
159 : : /*
160 : : * We are doing an outer join and there were no join matches
161 : : * for this outer tuple. Generate a fake join tuple with
162 : : * nulls for the inner tuple, and return it if it passes the
163 : : * non-join quals.
164 : : */
8666 165 : 56821 : econtext->ecxt_innertuple = node->nl_NullInnerTupleSlot;
166 : :
3453 andres@anarazel.de 167 [ + + + + ]: 56821 : if (otherqual == NULL || ExecQual(otherqual, econtext))
168 : : {
169 : : /*
170 : : * qualification was satisfied so we project and return
171 : : * the slot containing the result tuple using
172 : : * ExecProject().
173 : : */
3507 174 : 55815 : return ExecProject(node->js.ps.ps_ProjInfo);
175 : : }
176 : : else
5453 tgl@sss.pgh.pa.us 177 [ - + ]: 1006 : InstrCountFiltered2(node, 1);
178 : : }
179 : :
180 : : /*
181 : : * Otherwise just return to top of loop for a new outer tuple.
182 : : */
9480 183 : 498320 : continue;
184 : : }
185 : :
186 : : /*
187 : : * at this point we have a new pair of inner and outer tuples so we
188 : : * test the inner and outer tuples to see if they satisfy the node's
189 : : * qualification.
190 : : *
191 : : * Only the joinquals determine MatchedOuter status, but all quals
192 : : * must pass to actually return the tuple.
193 : : */
3453 andres@anarazel.de 194 [ + + ]: 6336468 : if (ExecQual(joinqual, econtext))
195 : : {
8666 tgl@sss.pgh.pa.us 196 : 2001059 : node->nl_MatchedOuter = true;
197 : :
198 : : /* In an antijoin, we never return a matched tuple */
6587 199 [ + + ]: 2001059 : if (node->js.jointype == JOIN_ANTI)
200 : : {
201 : 169608 : node->nl_NeedNewOuter = true;
6586 202 : 169608 : continue; /* return to top of loop */
203 : : }
204 : :
205 : : /*
206 : : * If we only need to join to the first matching inner tuple, then
207 : : * consider returning this one, but after that continue with next
208 : : * outer tuple.
209 : : */
3429 210 [ + + ]: 1831451 : if (node->js.single_match)
6586 211 : 162775 : node->nl_NeedNewOuter = true;
212 : :
3453 andres@anarazel.de 213 [ + + + + ]: 1831451 : if (otherqual == NULL || ExecQual(otherqual, econtext))
214 : : {
215 : : /*
216 : : * qualification was satisfied so we project and return the
217 : : * slot containing the result tuple using ExecProject().
218 : : */
3507 219 : 1824085 : return ExecProject(node->js.ps.ps_ProjInfo);
220 : : }
221 : : else
5453 tgl@sss.pgh.pa.us 222 [ - + ]: 7366 : InstrCountFiltered2(node, 1);
223 : : }
224 : : else
225 [ + + ]: 4335409 : InstrCountFiltered1(node, 1);
226 : :
227 : : /*
228 : : * Tuple fails qual, so free per-tuple memory and try again.
229 : : */
9542 230 : 4342775 : ResetExprContext(econtext);
231 : : }
232 : : }
233 : :
234 : : /* ----------------------------------------------------------------
235 : : * ExecInitNestLoop
236 : : * ----------------------------------------------------------------
237 : : */
238 : : NestLoopState *
7485 239 : 65096 : ExecInitNestLoop(NestLoop *node, EState *estate, int eflags)
240 : : {
241 : : NestLoopState *nlstate;
242 : :
243 : : /* check for unsupported flags */
244 [ - + ]: 65096 : Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
245 : :
246 : : /*
247 : : * create state structure
248 : : */
10581 bruce@momjian.us 249 : 65096 : nlstate = makeNode(NestLoopState);
8666 tgl@sss.pgh.pa.us 250 : 65096 : nlstate->js.ps.plan = (Plan *) node;
251 : 65096 : nlstate->js.ps.state = estate;
3328 andres@anarazel.de 252 : 65096 : nlstate->js.ps.ExecProcNode = ExecNestLoop;
253 : :
254 : : /*
255 : : * Miscellaneous initialization
256 : : *
257 : : * create expression context for node
258 : : */
8666 tgl@sss.pgh.pa.us 259 : 65096 : ExecAssignExprContext(estate, &nlstate->js.ps);
260 : :
261 : : /*
262 : : * initialize child nodes
263 : : *
264 : : * If we have no parameters to pass into the inner rel from the outer,
265 : : * tell the inner child that cheap rescans would be good. If we do have
266 : : * such parameters, then there is no point in REWIND support at all in the
267 : : * inner child, because it will always be rescanned with fresh parameter
268 : : * values.
269 : : */
7485 270 : 65096 : outerPlanState(nlstate) = ExecInitNode(outerPlan(node), estate, eflags);
5890 271 [ + + ]: 65096 : if (node->nestParams == NIL)
272 : 32993 : eflags |= EXEC_FLAG_REWIND;
273 : : else
274 : 32103 : eflags &= ~EXEC_FLAG_REWIND;
275 : 65096 : innerPlanState(nlstate) = ExecInitNode(innerPlan(node), estate, eflags);
276 : :
277 : : /*
278 : : * Initialize result slot, type and projection.
279 : : */
2842 andres@anarazel.de 280 : 65096 : ExecInitResultTupleSlotTL(&nlstate->js.ps, &TTSOpsVirtual);
3114 281 : 65096 : ExecAssignProjectionInfo(&nlstate->js.ps, NULL);
282 : :
283 : : /*
284 : : * initialize child expressions
285 : : */
286 : 65096 : nlstate->js.ps.qual =
287 : 65096 : ExecInitQual(node->join.plan.qual, (PlanState *) nlstate);
288 : 65096 : nlstate->js.jointype = node->join.jointype;
289 : 65096 : nlstate->js.joinqual =
290 : 65096 : ExecInitQual(node->join.joinqual, (PlanState *) nlstate);
291 : :
292 : : /*
293 : : * detect whether we need only consider the first matching inner tuple
294 : : */
3429 tgl@sss.pgh.pa.us 295 [ + + ]: 93129 : nlstate->js.single_match = (node->join.inner_unique ||
296 [ + + ]: 28033 : node->join.jointype == JOIN_SEMI);
297 : :
298 : : /* set up null tuples for outer joins, if needed */
9480 299 [ + + - ]: 65096 : switch (node->join.jointype)
300 : : {
301 : 48909 : case JOIN_INNER:
302 : : case JOIN_SEMI:
303 : 48909 : break;
304 : 16187 : case JOIN_LEFT:
305 : : case JOIN_ANTI:
306 : 16187 : nlstate->nl_NullInnerTupleSlot =
307 : 16187 : ExecInitNullTupleSlot(estate,
308 : : ExecGetResultType(innerPlanState(nlstate)),
309 : : &TTSOpsVirtual);
310 : 16187 : break;
9480 tgl@sss.pgh.pa.us 311 :UBC 0 : default:
8438 312 [ # # ]: 0 : elog(ERROR, "unrecognized join type: %d",
313 : : (int) node->join.jointype);
314 : : }
315 : :
316 : : /*
317 : : * finally, wipe the current outer tuple clean.
318 : : */
9480 tgl@sss.pgh.pa.us 319 :CBC 65096 : nlstate->nl_NeedNewOuter = true;
320 : 65096 : nlstate->nl_MatchedOuter = false;
321 : :
8666 322 : 65096 : return nlstate;
323 : : }
324 : :
325 : : /* ----------------------------------------------------------------
326 : : * ExecEndNestLoop
327 : : *
328 : : * closes down scans and frees allocated storage
329 : : * ----------------------------------------------------------------
330 : : */
331 : : void
332 : 64948 : ExecEndNestLoop(NestLoopState *node)
333 : : {
334 : : /*
335 : : * close down subplans
336 : : */
8656 337 : 64948 : ExecEndNode(outerPlanState(node));
338 : 64948 : ExecEndNode(innerPlanState(node));
11006 scrappy@hub.org 339 : 64948 : }
340 : :
341 : : /* ----------------------------------------------------------------
342 : : * ExecReScanNestLoop
343 : : * ----------------------------------------------------------------
344 : : */
345 : : void
5890 tgl@sss.pgh.pa.us 346 : 9147 : ExecReScanNestLoop(NestLoopState *node)
347 : : {
8424 bruce@momjian.us 348 : 9147 : PlanState *outerPlan = outerPlanState(node);
349 : :
350 : : /*
351 : : * If outerPlan->chgParam is not null then plan will be automatically
352 : : * re-scanned by first ExecProcNode.
353 : : */
10422 vadim4o@yahoo.com 354 [ + + ]: 9147 : if (outerPlan->chgParam == NULL)
5890 tgl@sss.pgh.pa.us 355 : 185 : ExecReScan(outerPlan);
356 : :
357 : : /*
358 : : * innerPlan is re-scanned for each new outer tuple and MUST NOT be
359 : : * re-scanned from here or you'll get troubles from inner index scans when
360 : : * outer Vars are used as run-time keys...
361 : : */
362 : :
8666 363 : 9147 : node->nl_NeedNewOuter = true;
364 : 9147 : node->nl_MatchedOuter = false;
10422 vadim4o@yahoo.com 365 : 9147 : }
|
