PostgreSQL Source Code  git master
nodeNestloop.c
Go to the documentation of this file.
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 *
61 {
62  NestLoopState *node = castNode(NestLoopState, pstate);
63  NestLoop *nl;
66  TupleTableSlot *outerTupleSlot;
67  TupleTableSlot *innerTupleSlot;
68  ExprState *joinqual;
69  ExprState *otherqual;
70  ExprContext *econtext;
71  ListCell *lc;
72 
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");
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  */
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  */
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,
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
362 {
363  NL1_printf("ExecEndNestLoop: %s\n",
364  "ending node processing");
365 
366  /*
367  * close down subplans
368  */
371 
372  NL1_printf("ExecEndNestLoop: %s\n",
373  "node processing ended");
374 }
375 
376 /* ----------------------------------------------------------------
377  * ExecReScanNestLoop
378  * ----------------------------------------------------------------
379  */
380 void
382 {
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)
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 }
Bitmapset * bms_add_member(Bitmapset *a, int x)
Definition: bitmapset.c:815
#define Assert(condition)
Definition: c.h:858
#define ERROR
Definition: elog.h:39
#define elog(elevel,...)
Definition: elog.h:224
void ExecReScan(PlanState *node)
Definition: execAmi.c:76
ExprState * ExecInitQual(List *qual, PlanState *parent)
Definition: execExpr.c:220
void ExecEndNode(PlanState *node)
Definition: execProcnode.c:557
PlanState * ExecInitNode(Plan *node, EState *estate, int eflags)
Definition: execProcnode.c:142
const TupleTableSlotOps TTSOpsVirtual
Definition: execTuples.c:84
TupleTableSlot * ExecInitNullTupleSlot(EState *estate, TupleDesc tupType, const TupleTableSlotOps *tts_ops)
Definition: execTuples.c:1934
void ExecInitResultTupleSlotTL(PlanState *planstate, const TupleTableSlotOps *tts_ops)
Definition: execTuples.c:1886
TupleDesc ExecGetResultType(PlanState *planstate)
Definition: execUtils.c:493
void ExecAssignExprContext(EState *estate, PlanState *planstate)
Definition: execUtils.c:483
void ExecAssignProjectionInfo(PlanState *planstate, TupleDesc inputDesc)
Definition: execUtils.c:538
#define ENL1_printf(message)
Definition: execdebug.h:78
#define NL1_printf(s, a)
Definition: execdebug.h:77
#define InstrCountFiltered1(node, delta)
Definition: execnodes.h:1222
#define outerPlanState(node)
Definition: execnodes.h:1214
#define InstrCountFiltered2(node, delta)
Definition: execnodes.h:1227
#define innerPlanState(node)
Definition: execnodes.h:1213
#define EXEC_FLAG_BACKWARD
Definition: executor.h:68
#define EXEC_FLAG_REWIND
Definition: executor.h:67
static TupleTableSlot * ExecProject(ProjectionInfo *projInfo)
Definition: executor.h:376
#define ResetExprContext(econtext)
Definition: executor.h:544
static bool ExecQual(ExprState *state, ExprContext *econtext)
Definition: executor.h:413
#define EXEC_FLAG_MARK
Definition: executor.h:69
static TupleTableSlot * ExecProcNode(PlanState *node)
Definition: executor.h:269
#define CHECK_FOR_INTERRUPTS()
Definition: miscadmin.h:122
static TupleTableSlot * ExecNestLoop(PlanState *pstate)
Definition: nodeNestloop.c:60
void ExecEndNestLoop(NestLoopState *node)
Definition: nodeNestloop.c:361
void ExecReScanNestLoop(NestLoopState *node)
Definition: nodeNestloop.c:381
NestLoopState * ExecInitNestLoop(NestLoop *node, EState *estate, int eflags)
Definition: nodeNestloop.c:262
#define IsA(nodeptr, _type_)
Definition: nodes.h:158
#define makeNode(_type_)
Definition: nodes.h:155
#define castNode(_type_, nodeptr)
Definition: nodes.h:176
@ JOIN_SEMI
Definition: nodes.h:307
@ JOIN_INNER
Definition: nodes.h:293
@ JOIN_LEFT
Definition: nodes.h:294
@ JOIN_ANTI
Definition: nodes.h:308
#define lfirst(lc)
Definition: pg_list.h:172
#define NIL
Definition: pg_list.h:68
#define innerPlan(node)
Definition: plannodes.h:181
#define outerPlan(node)
Definition: plannodes.h:182
#define OUTER_VAR
Definition: primnodes.h:237
TupleTableSlot * ecxt_innertuple
Definition: execnodes.h:257
ParamExecData * ecxt_param_exec_vals
Definition: execnodes.h:266
TupleTableSlot * ecxt_outertuple
Definition: execnodes.h:259
JoinType jointype
Definition: execnodes.h:2086
PlanState ps
Definition: execnodes.h:2085
ExprState * joinqual
Definition: execnodes.h:2089
bool single_match
Definition: execnodes.h:2087
List * joinqual
Definition: plannodes.h:793
JoinType jointype
Definition: plannodes.h:791
bool inner_unique
Definition: plannodes.h:792
Var * paramval
Definition: plannodes.h:819
TupleTableSlot * nl_NullInnerTupleSlot
Definition: execnodes.h:2105
bool nl_NeedNewOuter
Definition: execnodes.h:2103
JoinState js
Definition: execnodes.h:2102
bool nl_MatchedOuter
Definition: execnodes.h:2104
List * nestParams
Definition: plannodes.h:810
Join join
Definition: plannodes.h:809
bool isnull
Definition: params.h:150
Datum value
Definition: params.h:149
ExprState * qual
Definition: execnodes.h:1139
Plan * plan
Definition: execnodes.h:1118
EState * state
Definition: execnodes.h:1120
ExprContext * ps_ExprContext
Definition: execnodes.h:1157
ProjectionInfo * ps_ProjInfo
Definition: execnodes.h:1158
ExecProcNodeMtd ExecProcNode
Definition: execnodes.h:1124
Definition: primnodes.h:248
AttrNumber varattno
Definition: primnodes.h:260
int varno
Definition: primnodes.h:255
static Datum slot_getattr(TupleTableSlot *slot, int attnum, bool *isnull)
Definition: tuptable.h:395
#define TupIsNull(slot)
Definition: tuptable.h:306