| 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 * |
| 60 |
ExecNestLoop(PlanState *pstate) |
| 61 |
{ |
| 62 |
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 |
CHECK_FOR_INTERRUPTS(); |
| 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"); |
| 151 |
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 |
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 |
*/ |
| 261 |
NestLoopState * |
| 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 |
*/ |
| 306 |
ExecInitResultTupleSlotTL(&nlstate->js.ps, &TTSOpsVirtual); |
| 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, |
| 334 |
ExecGetResultType(innerPlanState(nlstate)), |
| 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 |
| 361 |
ExecEndNestLoop(NestLoopState *node) |
| 362 |
{ |
| 363 |
NL1_printf("ExecEndNestLoop: %s\n", |
| 364 |
"ending node processing"); |
| 365 |
|
| 366 |
/* |
| 367 |
* close down subplans |
| 368 |
*/ |
| 369 |
ExecEndNode(outerPlanState(node)); |
| 370 |
ExecEndNode(innerPlanState(node)); |
| 371 |
|
| 372 |
NL1_printf("ExecEndNestLoop: %s\n", |
| 373 |
"node processing ended"); |
| 374 |
} |
| 375 |
|
| 376 |
/* ---------------------------------------------------------------- |
| 377 |
* ExecReScanNestLoop |
| 378 |
* ---------------------------------------------------------------- |
| 379 |
*/ |
| 380 |
void |
| 381 |
ExecReScanNestLoop(NestLoopState *node) |
| 382 |
{ |
| 383 |
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 |
if (outerPlan->chgParam == NULL) |
| 390 |
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 |
node->nl_NeedNewOuter = true; |
| 399 |
node->nl_MatchedOuter = false; |
| 400 |
} |