granicus.if.org Git - postgresql/blob - src/backend/executor/nodeNestloop.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * nodeNestloop.c
   4  *        routines to support nest-loop joins
   5  *
   6  * Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $Header: /cvsroot/pgsql/src/backend/executor/nodeNestloop.c,v 1.30 2003/01/20 18:54:46 tgl Exp $
  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 "utils/memutils.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 TupleTableSlot *
  60 ExecNestLoop(NestLoopState *node)
  61 {
  62         PlanState  *innerPlan;
  63         PlanState  *outerPlan;
  64         TupleTableSlot *outerTupleSlot;
  65         TupleTableSlot *innerTupleSlot;
  66         List       *joinqual;
  67         List       *otherqual;
  68         ExprContext *econtext;
  69
  70         /*
  71          * get information from the node
  72          */
  73         ENL1_printf("getting info from node");
  74
  75         joinqual = node->js.joinqual;
  76         otherqual = node->js.ps.qual;
  77         outerPlan = outerPlanState(node);
  78         innerPlan = innerPlanState(node);
  79         econtext = node->js.ps.ps_ExprContext;
  80
  81         /*
  82          * get the current outer tuple
  83          */
  84         outerTupleSlot = node->js.ps.ps_OuterTupleSlot;
  85         econtext->ecxt_outertuple = outerTupleSlot;
  86
  87         /*
  88          * Check to see if we're still projecting out tuples from a previous
  89          * join tuple (because there is a function-returning-set in the
  90          * projection expressions).  If so, try to project another one.
  91          */
  92         if (node->js.ps.ps_TupFromTlist)
  93         {
  94                 TupleTableSlot *result;
  95                 ExprDoneCond isDone;
  96
  97                 result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
  98                 if (isDone == ExprMultipleResult)
  99                         return result;
 100                 /* Done with that source tuple... */
 101                 node->js.ps.ps_TupFromTlist = false;
 102         }
 103
 104         /*
 105          * If we're doing an IN join, we want to return at most one row per
 106          * outer tuple; so we can stop scanning the inner scan if we matched on
 107          * the previous try.
 108          */
 109         if (node->js.jointype == JOIN_IN &&
 110                 node->nl_MatchedOuter)
 111                 node->nl_NeedNewOuter = true;
 112
 113         /*
 114          * Reset per-tuple memory context to free any expression evaluation
 115          * storage allocated in the previous tuple cycle.  Note this can't
 116          * happen until we're done projecting out tuples from a join tuple.
 117          */
 118         ResetExprContext(econtext);
 119
 120         /*
 121          * Ok, everything is setup for the join so now loop until we return a
 122          * qualifying join tuple.
 123          */
 124         ENL1_printf("entering main loop");
 125
 126         for (;;)
 127         {
 128                 /*
 129                  * If we don't have an outer tuple, get the next one and reset the
 130                  * inner scan.
 131                  */
 132                 if (node->nl_NeedNewOuter)
 133                 {
 134                         ENL1_printf("getting new outer tuple");
 135                         outerTupleSlot = ExecProcNode(outerPlan);
 136
 137                         /*
 138                          * if there are no more outer tuples, then the join is
 139                          * complete..
 140                          */
 141                         if (TupIsNull(outerTupleSlot))
 142                         {
 143                                 ENL1_printf("no outer tuple, ending join");
 144                                 return NULL;
 145                         }
 146
 147                         ENL1_printf("saving new outer tuple information");
 148                         node->js.ps.ps_OuterTupleSlot = outerTupleSlot;
 149                         econtext->ecxt_outertuple = outerTupleSlot;
 150                         node->nl_NeedNewOuter = false;
 151                         node->nl_MatchedOuter = false;
 152
 153                         /*
 154                          * now rescan the inner plan
 155                          */
 156                         ENL1_printf("rescanning inner plan");
 157
 158                         /*
 159                          * The scan key of the inner plan might depend on the current
 160                          * outer tuple (e.g. in index scans), that's why we pass our
 161                          * expr context.
 162                          */
 163                         ExecReScan(innerPlan, econtext);
 164                 }
 165
 166                 /*
 167                  * we have an outerTuple, try to get the next inner tuple.
 168                  */
 169                 ENL1_printf("getting new inner tuple");
 170
 171                 innerTupleSlot = ExecProcNode(innerPlan);
 172                 econtext->ecxt_innertuple = innerTupleSlot;
 173
 174                 if (TupIsNull(innerTupleSlot))
 175                 {
 176                         ENL1_printf("no inner tuple, need new outer tuple");
 177
 178                         node->nl_NeedNewOuter = true;
 179
 180                         if (!node->nl_MatchedOuter &&
 181                                 node->js.jointype == JOIN_LEFT)
 182                         {
 183                                 /*
 184                                  * We are doing an outer join and there were no join
 185                                  * matches for this outer tuple.  Generate a fake join
 186                                  * tuple with nulls for the inner tuple, and return it if
 187                                  * it passes the non-join quals.
 188                                  */
 189                                 econtext->ecxt_innertuple = node->nl_NullInnerTupleSlot;
 190
 191                                 ENL1_printf("testing qualification for outer-join tuple");
 192
 193                                 if (ExecQual(otherqual, econtext, false))
 194                                 {
 195                                         /*
 196                                          * qualification was satisfied so we project and
 197                                          * return the slot containing the result tuple using
 198                                          * ExecProject().
 199                                          */
 200                                         TupleTableSlot *result;
 201                                         ExprDoneCond isDone;
 202
 203                                         ENL1_printf("qualification succeeded, projecting tuple");
 204
 205                                         result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
 206
 207                                         if (isDone != ExprEndResult)
 208                                         {
 209                                                 node->js.ps.ps_TupFromTlist =
 210                                                         (isDone == ExprMultipleResult);
 211                                                 return result;
 212                                         }
 213                                 }
 214                         }
 215
 216                         /*
 217                          * Otherwise just return to top of loop for a new outer tuple.
 218                          */
 219                         continue;
 220                 }
 221
 222                 /*
 223                  * at this point we have a new pair of inner and outer tuples so
 224                  * we test the inner and outer tuples to see if they satisfy the
 225                  * node's qualification.
 226                  *
 227                  * Only the joinquals determine MatchedOuter status, but all quals
 228                  * must pass to actually return the tuple.
 229                  */
 230                 ENL1_printf("testing qualification");
 231
 232                 if (ExecQual(joinqual, econtext, false))
 233                 {
 234                         node->nl_MatchedOuter = true;
 235
 236                         if (otherqual == NIL || ExecQual(otherqual, econtext, false))
 237                         {
 238                                 /*
 239                                  * qualification was satisfied so we project and return
 240                                  * the slot containing the result tuple using
 241                                  * ExecProject().
 242                                  */
 243                                 TupleTableSlot *result;
 244                                 ExprDoneCond isDone;
 245
 246                                 ENL1_printf("qualification succeeded, projecting tuple");
 247
 248                                 result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
 249
 250                                 if (isDone != ExprEndResult)
 251                                 {
 252                                         node->js.ps.ps_TupFromTlist =
 253                                                 (isDone == ExprMultipleResult);
 254                                         return result;
 255                                 }
 256                         }
 257                 }
 258
 259                 /*
 260                  * Tuple fails qual, so free per-tuple memory and try again.
 261                  */
 262                 ResetExprContext(econtext);
 263
 264                 ENL1_printf("qualification failed, looping");
 265         }
 266 }
 267
 268 /* ----------------------------------------------------------------
 269  *              ExecInitNestLoop
 270  * ----------------------------------------------------------------
 271  */
 272 NestLoopState *
 273 ExecInitNestLoop(NestLoop *node, EState *estate)
 274 {
 275         NestLoopState *nlstate;
 276
 277         NL1_printf("ExecInitNestLoop: %s\n",
 278                            "initializing node");
 279
 280         /*
 281          * create state structure
 282          */
 283         nlstate = makeNode(NestLoopState);
 284         nlstate->js.ps.plan = (Plan *) node;
 285         nlstate->js.ps.state = estate;
 286
 287         /*
 288          * Miscellaneous initialization
 289          *
 290          * create expression context for node
 291          */
 292         ExecAssignExprContext(estate, &nlstate->js.ps);
 293
 294         /*
 295          * initialize child expressions
 296          */
 297         nlstate->js.ps.targetlist = (List *)
 298                 ExecInitExpr((Expr *) node->join.plan.targetlist,
 299                                          (PlanState *) nlstate);
 300         nlstate->js.ps.qual = (List *)
 301                 ExecInitExpr((Expr *) node->join.plan.qual,
 302                                          (PlanState *) nlstate);
 303         nlstate->js.jointype = node->join.jointype;
 304         nlstate->js.joinqual = (List *)
 305                 ExecInitExpr((Expr *) node->join.joinqual,
 306                                          (PlanState *) nlstate);
 307
 308         /*
 309          * initialize child nodes
 310          */
 311         outerPlanState(nlstate) = ExecInitNode(outerPlan(node), estate);
 312         innerPlanState(nlstate) = ExecInitNode(innerPlan(node), estate);
 313
 314 #define NESTLOOP_NSLOTS 2
 315
 316         /*
 317          * tuple table initialization
 318          */
 319         ExecInitResultTupleSlot(estate, &nlstate->js.ps);
 320
 321         switch (node->join.jointype)
 322         {
 323                 case JOIN_INNER:
 324                 case JOIN_IN:
 325                         break;
 326                 case JOIN_LEFT:
 327                         nlstate->nl_NullInnerTupleSlot =
 328                                 ExecInitNullTupleSlot(estate,
 329                                                            ExecGetTupType(innerPlanState(nlstate)));
 330                         break;
 331                 default:
 332                         elog(ERROR, "ExecInitNestLoop: unsupported join type %d",
 333                                  (int) node->join.jointype);
 334         }
 335
 336         /*
 337          * initialize tuple type and projection info
 338          */
 339         ExecAssignResultTypeFromTL(&nlstate->js.ps);
 340         ExecAssignProjectionInfo(&nlstate->js.ps);
 341
 342         /*
 343          * finally, wipe the current outer tuple clean.
 344          */
 345         nlstate->js.ps.ps_OuterTupleSlot = NULL;
 346         nlstate->js.ps.ps_TupFromTlist = false;
 347         nlstate->nl_NeedNewOuter = true;
 348         nlstate->nl_MatchedOuter = false;
 349
 350         NL1_printf("ExecInitNestLoop: %s\n",
 351                            "node initialized");
 352
 353         return nlstate;
 354 }
 355
 356 int
 357 ExecCountSlotsNestLoop(NestLoop *node)
 358 {
 359         return ExecCountSlotsNode(outerPlan(node)) +
 360                 ExecCountSlotsNode(innerPlan(node)) +
 361                 NESTLOOP_NSLOTS;
 362 }
 363
 364 /* ----------------------------------------------------------------
 365  *              ExecEndNestLoop
 366  *
 367  *              closes down scans and frees allocated storage
 368  * ----------------------------------------------------------------
 369  */
 370 void
 371 ExecEndNestLoop(NestLoopState *node)
 372 {
 373         NL1_printf("ExecEndNestLoop: %s\n",
 374                            "ending node processing");
 375
 376         /*
 377          * Free the exprcontext
 378          */
 379         ExecFreeExprContext(&node->js.ps);
 380
 381         /*
 382          * clean out the tuple table
 383          */
 384         ExecClearTuple(node->js.ps.ps_ResultTupleSlot);
 385
 386         /*
 387          * close down subplans
 388          */
 389         ExecEndNode(outerPlanState(node));
 390         ExecEndNode(innerPlanState(node));
 391
 392         NL1_printf("ExecEndNestLoop: %s\n",
 393                            "node processing ended");
 394 }
 395
 396 /* ----------------------------------------------------------------
 397  *              ExecReScanNestLoop
 398  * ----------------------------------------------------------------
 399  */
 400 void
 401 ExecReScanNestLoop(NestLoopState *node, ExprContext *exprCtxt)
 402 {
 403         PlanState   *outerPlan = outerPlanState(node);
 404
 405         /*
 406          * If outerPlan->chgParam is not null then plan will be automatically
 407          * re-scanned by first ExecProcNode. innerPlan is re-scanned for each
 408          * new outer tuple and MUST NOT be re-scanned from here or you'll get
 409          * troubles from inner index scans when outer Vars are used as
 410          * run-time keys...
 411          */
 412         if (outerPlan->chgParam == NULL)
 413                 ExecReScan(outerPlan, exprCtxt);
 414
 415         /* let outerPlan to free its result tuple ... */
 416         node->js.ps.ps_OuterTupleSlot = NULL;
 417         node->js.ps.ps_TupFromTlist = false;
 418         node->nl_NeedNewOuter = true;
 419         node->nl_MatchedOuter = false;
 420 }