Header And Logo

PostgreSQL
| The world's most advanced open source database.

nodeNestloop.c

Go to the documentation of this file.
00001 /*-------------------------------------------------------------------------
00002  *
00003  * nodeNestloop.c
00004  *    routines to support nest-loop joins
00005  *
00006  * Portions Copyright (c) 1996-2013, PostgreSQL Global Development Group
00007  * Portions Copyright (c) 1994, Regents of the University of California
00008  *
00009  *
00010  * IDENTIFICATION
00011  *    src/backend/executor/nodeNestloop.c
00012  *
00013  *-------------------------------------------------------------------------
00014  */
00015 /*
00016  *   INTERFACE ROUTINES
00017  *      ExecNestLoop     - process a nestloop join of two plans
00018  *      ExecInitNestLoop - initialize the join
00019  *      ExecEndNestLoop  - shut down the join
00020  */
00021 
00022 #include "postgres.h"
00023 
00024 #include "executor/execdebug.h"
00025 #include "executor/nodeNestloop.h"
00026 #include "utils/memutils.h"
00027 
00028 
00029 /* ----------------------------------------------------------------
00030  *      ExecNestLoop(node)
00031  *
00032  * old comments
00033  *      Returns the tuple joined from inner and outer tuples which
00034  *      satisfies the qualification clause.
00035  *
00036  *      It scans the inner relation to join with current outer tuple.
00037  *
00038  *      If none is found, next tuple from the outer relation is retrieved
00039  *      and the inner relation is scanned from the beginning again to join
00040  *      with the outer tuple.
00041  *
00042  *      NULL is returned if all the remaining outer tuples are tried and
00043  *      all fail to join with the inner tuples.
00044  *
00045  *      NULL is also returned if there is no tuple from inner relation.
00046  *
00047  *      Conditions:
00048  *        -- outerTuple contains current tuple from outer relation and
00049  *           the right son(inner relation) maintains "cursor" at the tuple
00050  *           returned previously.
00051  *              This is achieved by maintaining a scan position on the outer
00052  *              relation.
00053  *
00054  *      Initial States:
00055  *        -- the outer child and the inner child
00056  *             are prepared to return the first tuple.
00057  * ----------------------------------------------------------------
00058  */
00059 TupleTableSlot *
00060 ExecNestLoop(NestLoopState *node)
00061 {
00062     NestLoop   *nl;
00063     PlanState  *innerPlan;
00064     PlanState  *outerPlan;
00065     TupleTableSlot *outerTupleSlot;
00066     TupleTableSlot *innerTupleSlot;
00067     List       *joinqual;
00068     List       *otherqual;
00069     ExprContext *econtext;
00070     ListCell   *lc;
00071 
00072     /*
00073      * get information from the node
00074      */
00075     ENL1_printf("getting info from node");
00076 
00077     nl = (NestLoop *) node->js.ps.plan;
00078     joinqual = node->js.joinqual;
00079     otherqual = node->js.ps.qual;
00080     outerPlan = outerPlanState(node);
00081     innerPlan = innerPlanState(node);
00082     econtext = node->js.ps.ps_ExprContext;
00083 
00084     /*
00085      * Check to see if we're still projecting out tuples from a previous join
00086      * tuple (because there is a function-returning-set in the projection
00087      * expressions).  If so, try to project another one.
00088      */
00089     if (node->js.ps.ps_TupFromTlist)
00090     {
00091         TupleTableSlot *result;
00092         ExprDoneCond isDone;
00093 
00094         result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
00095         if (isDone == ExprMultipleResult)
00096             return result;
00097         /* Done with that source tuple... */
00098         node->js.ps.ps_TupFromTlist = false;
00099     }
00100 
00101     /*
00102      * Reset per-tuple memory context to free any expression evaluation
00103      * storage allocated in the previous tuple cycle.  Note this can't happen
00104      * until we're done projecting out tuples from a join tuple.
00105      */
00106     ResetExprContext(econtext);
00107 
00108     /*
00109      * Ok, everything is setup for the join so now loop until we return a
00110      * qualifying join tuple.
00111      */
00112     ENL1_printf("entering main loop");
00113 
00114     for (;;)
00115     {
00116         /*
00117          * If we don't have an outer tuple, get the next one and reset the
00118          * inner scan.
00119          */
00120         if (node->nl_NeedNewOuter)
00121         {
00122             ENL1_printf("getting new outer tuple");
00123             outerTupleSlot = ExecProcNode(outerPlan);
00124 
00125             /*
00126              * if there are no more outer tuples, then the join is complete..
00127              */
00128             if (TupIsNull(outerTupleSlot))
00129             {
00130                 ENL1_printf("no outer tuple, ending join");
00131                 return NULL;
00132             }
00133 
00134             ENL1_printf("saving new outer tuple information");
00135             econtext->ecxt_outertuple = outerTupleSlot;
00136             node->nl_NeedNewOuter = false;
00137             node->nl_MatchedOuter = false;
00138 
00139             /*
00140              * fetch the values of any outer Vars that must be passed to the
00141              * inner scan, and store them in the appropriate PARAM_EXEC slots.
00142              */
00143             foreach(lc, nl->nestParams)
00144             {
00145                 NestLoopParam *nlp = (NestLoopParam *) lfirst(lc);
00146                 int         paramno = nlp->paramno;
00147                 ParamExecData *prm;
00148 
00149                 prm = &(econtext->ecxt_param_exec_vals[paramno]);
00150                 /* Param value should be an OUTER_VAR var */
00151                 Assert(IsA(nlp->paramval, Var));
00152                 Assert(nlp->paramval->varno == OUTER_VAR);
00153                 Assert(nlp->paramval->varattno > 0);
00154                 prm->value = slot_getattr(outerTupleSlot,
00155                                           nlp->paramval->varattno,
00156                                           &(prm->isnull));
00157                 /* Flag parameter value as changed */
00158                 innerPlan->chgParam = bms_add_member(innerPlan->chgParam,
00159                                                      paramno);
00160             }
00161 
00162             /*
00163              * now rescan the inner plan
00164              */
00165             ENL1_printf("rescanning inner plan");
00166             ExecReScan(innerPlan);
00167         }
00168 
00169         /*
00170          * we have an outerTuple, try to get the next inner tuple.
00171          */
00172         ENL1_printf("getting new inner tuple");
00173 
00174         innerTupleSlot = ExecProcNode(innerPlan);
00175         econtext->ecxt_innertuple = innerTupleSlot;
00176 
00177         if (TupIsNull(innerTupleSlot))
00178         {
00179             ENL1_printf("no inner tuple, need new outer tuple");
00180 
00181             node->nl_NeedNewOuter = true;
00182 
00183             if (!node->nl_MatchedOuter &&
00184                 (node->js.jointype == JOIN_LEFT ||
00185                  node->js.jointype == JOIN_ANTI))
00186             {
00187                 /*
00188                  * We are doing an outer join and there were no join matches
00189                  * for this outer tuple.  Generate a fake join tuple with
00190                  * nulls for the inner tuple, and return it if it passes the
00191                  * non-join quals.
00192                  */
00193                 econtext->ecxt_innertuple = node->nl_NullInnerTupleSlot;
00194 
00195                 ENL1_printf("testing qualification for outer-join tuple");
00196 
00197                 if (otherqual == NIL || ExecQual(otherqual, econtext, false))
00198                 {
00199                     /*
00200                      * qualification was satisfied so we project and return
00201                      * the slot containing the result tuple using
00202                      * ExecProject().
00203                      */
00204                     TupleTableSlot *result;
00205                     ExprDoneCond isDone;
00206 
00207                     ENL1_printf("qualification succeeded, projecting tuple");
00208 
00209                     result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
00210 
00211                     if (isDone != ExprEndResult)
00212                     {
00213                         node->js.ps.ps_TupFromTlist =
00214                             (isDone == ExprMultipleResult);
00215                         return result;
00216                     }
00217                 }
00218                 else
00219                     InstrCountFiltered2(node, 1);
00220             }
00221 
00222             /*
00223              * Otherwise just return to top of loop for a new outer tuple.
00224              */
00225             continue;
00226         }
00227 
00228         /*
00229          * at this point we have a new pair of inner and outer tuples so we
00230          * test the inner and outer tuples to see if they satisfy the node's
00231          * qualification.
00232          *
00233          * Only the joinquals determine MatchedOuter status, but all quals
00234          * must pass to actually return the tuple.
00235          */
00236         ENL1_printf("testing qualification");
00237 
00238         if (ExecQual(joinqual, econtext, false))
00239         {
00240             node->nl_MatchedOuter = true;
00241 
00242             /* In an antijoin, we never return a matched tuple */
00243             if (node->js.jointype == JOIN_ANTI)
00244             {
00245                 node->nl_NeedNewOuter = true;
00246                 continue;       /* return to top of loop */
00247             }
00248 
00249             /*
00250              * In a semijoin, we'll consider returning the first match, but
00251              * after that we're done with this outer tuple.
00252              */
00253             if (node->js.jointype == JOIN_SEMI)
00254                 node->nl_NeedNewOuter = true;
00255 
00256             if (otherqual == NIL || ExecQual(otherqual, econtext, false))
00257             {
00258                 /*
00259                  * qualification was satisfied so we project and return the
00260                  * slot containing the result tuple using ExecProject().
00261                  */
00262                 TupleTableSlot *result;
00263                 ExprDoneCond isDone;
00264 
00265                 ENL1_printf("qualification succeeded, projecting tuple");
00266 
00267                 result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
00268 
00269                 if (isDone != ExprEndResult)
00270                 {
00271                     node->js.ps.ps_TupFromTlist =
00272                         (isDone == ExprMultipleResult);
00273                     return result;
00274                 }
00275             }
00276             else
00277                 InstrCountFiltered2(node, 1);
00278         }
00279         else
00280             InstrCountFiltered1(node, 1);
00281 
00282         /*
00283          * Tuple fails qual, so free per-tuple memory and try again.
00284          */
00285         ResetExprContext(econtext);
00286 
00287         ENL1_printf("qualification failed, looping");
00288     }
00289 }
00290 
00291 /* ----------------------------------------------------------------
00292  *      ExecInitNestLoop
00293  * ----------------------------------------------------------------
00294  */
00295 NestLoopState *
00296 ExecInitNestLoop(NestLoop *node, EState *estate, int eflags)
00297 {
00298     NestLoopState *nlstate;
00299 
00300     /* check for unsupported flags */
00301     Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
00302 
00303     NL1_printf("ExecInitNestLoop: %s\n",
00304                "initializing node");
00305 
00306     /*
00307      * create state structure
00308      */
00309     nlstate = makeNode(NestLoopState);
00310     nlstate->js.ps.plan = (Plan *) node;
00311     nlstate->js.ps.state = estate;
00312 
00313     /*
00314      * Miscellaneous initialization
00315      *
00316      * create expression context for node
00317      */
00318     ExecAssignExprContext(estate, &nlstate->js.ps);
00319 
00320     /*
00321      * initialize child expressions
00322      */
00323     nlstate->js.ps.targetlist = (List *)
00324         ExecInitExpr((Expr *) node->join.plan.targetlist,
00325                      (PlanState *) nlstate);
00326     nlstate->js.ps.qual = (List *)
00327         ExecInitExpr((Expr *) node->join.plan.qual,
00328                      (PlanState *) nlstate);
00329     nlstate->js.jointype = node->join.jointype;
00330     nlstate->js.joinqual = (List *)
00331         ExecInitExpr((Expr *) node->join.joinqual,
00332                      (PlanState *) nlstate);
00333 
00334     /*
00335      * initialize child nodes
00336      *
00337      * If we have no parameters to pass into the inner rel from the outer,
00338      * tell the inner child that cheap rescans would be good.  If we do have
00339      * such parameters, then there is no point in REWIND support at all in the
00340      * inner child, because it will always be rescanned with fresh parameter
00341      * values.
00342      */
00343     outerPlanState(nlstate) = ExecInitNode(outerPlan(node), estate, eflags);
00344     if (node->nestParams == NIL)
00345         eflags |= EXEC_FLAG_REWIND;
00346     else
00347         eflags &= ~EXEC_FLAG_REWIND;
00348     innerPlanState(nlstate) = ExecInitNode(innerPlan(node), estate, eflags);
00349 
00350     /*
00351      * tuple table initialization
00352      */
00353     ExecInitResultTupleSlot(estate, &nlstate->js.ps);
00354 
00355     switch (node->join.jointype)
00356     {
00357         case JOIN_INNER:
00358         case JOIN_SEMI:
00359             break;
00360         case JOIN_LEFT:
00361         case JOIN_ANTI:
00362             nlstate->nl_NullInnerTupleSlot =
00363                 ExecInitNullTupleSlot(estate,
00364                                  ExecGetResultType(innerPlanState(nlstate)));
00365             break;
00366         default:
00367             elog(ERROR, "unrecognized join type: %d",
00368                  (int) node->join.jointype);
00369     }
00370 
00371     /*
00372      * initialize tuple type and projection info
00373      */
00374     ExecAssignResultTypeFromTL(&nlstate->js.ps);
00375     ExecAssignProjectionInfo(&nlstate->js.ps, NULL);
00376 
00377     /*
00378      * finally, wipe the current outer tuple clean.
00379      */
00380     nlstate->js.ps.ps_TupFromTlist = false;
00381     nlstate->nl_NeedNewOuter = true;
00382     nlstate->nl_MatchedOuter = false;
00383 
00384     NL1_printf("ExecInitNestLoop: %s\n",
00385                "node initialized");
00386 
00387     return nlstate;
00388 }
00389 
00390 /* ----------------------------------------------------------------
00391  *      ExecEndNestLoop
00392  *
00393  *      closes down scans and frees allocated storage
00394  * ----------------------------------------------------------------
00395  */
00396 void
00397 ExecEndNestLoop(NestLoopState *node)
00398 {
00399     NL1_printf("ExecEndNestLoop: %s\n",
00400                "ending node processing");
00401 
00402     /*
00403      * Free the exprcontext
00404      */
00405     ExecFreeExprContext(&node->js.ps);
00406 
00407     /*
00408      * clean out the tuple table
00409      */
00410     ExecClearTuple(node->js.ps.ps_ResultTupleSlot);
00411 
00412     /*
00413      * close down subplans
00414      */
00415     ExecEndNode(outerPlanState(node));
00416     ExecEndNode(innerPlanState(node));
00417 
00418     NL1_printf("ExecEndNestLoop: %s\n",
00419                "node processing ended");
00420 }
00421 
00422 /* ----------------------------------------------------------------
00423  *      ExecReScanNestLoop
00424  * ----------------------------------------------------------------
00425  */
00426 void
00427 ExecReScanNestLoop(NestLoopState *node)
00428 {
00429     PlanState  *outerPlan = outerPlanState(node);
00430 
00431     /*
00432      * If outerPlan->chgParam is not null then plan will be automatically
00433      * re-scanned by first ExecProcNode.
00434      */
00435     if (outerPlan->chgParam == NULL)
00436         ExecReScan(outerPlan);
00437 
00438     /*
00439      * innerPlan is re-scanned for each new outer tuple and MUST NOT be
00440      * re-scanned from here or you'll get troubles from inner index scans when
00441      * outer Vars are used as run-time keys...
00442      */
00443 
00444     node->js.ps.ps_TupFromTlist = false;
00445     node->nl_NeedNewOuter = true;
00446     node->nl_MatchedOuter = false;
00447 }