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