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