Logo Search packages:      
Sourcecode: postgresql-8.4 version File versions

nodeNestloop.c

/*-------------------------------------------------------------------------
 *
 * nodeNestloop.c
 *      routines to support nest-loop joins
 *
 * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *      $PostgreSQL: pgsql/src/backend/executor/nodeNestloop.c,v 1.52 2009/04/02 20:59:10 momjian Exp $
 *
 *-------------------------------------------------------------------------
 */
/*
 *     INTERFACE ROUTINES
 *          ExecNestLoop       - process a nestloop join of two plans
 *          ExecInitNestLoop - initialize the join
 *          ExecEndNestLoop  - shut down the join
 */

#include "postgres.h"

#include "executor/execdebug.h"
#include "executor/nodeNestloop.h"
#include "utils/memutils.h"


/* ----------------------------------------------------------------
 *          ExecNestLoop(node)
 *
 * old comments
 *          Returns the tuple joined from inner and outer tuples which
 *          satisfies the qualification clause.
 *
 *          It scans the inner relation to join with current outer tuple.
 *
 *          If none is found, next tuple from the outer relation is retrieved
 *          and the inner relation is scanned from the beginning again to join
 *          with the outer tuple.
 *
 *          NULL is returned if all the remaining outer tuples are tried and
 *          all fail to join with the inner tuples.
 *
 *          NULL is also returned if there is no tuple from inner relation.
 *
 *          Conditions:
 *            -- outerTuple contains current tuple from outer relation and
 *                 the right son(inner relation) maintains "cursor" at the tuple
 *                 returned previously.
 *                      This is achieved by maintaining a scan position on the outer
 *                      relation.
 *
 *          Initial States:
 *            -- the outer child and the inner child
 *                   are prepared to return the first tuple.
 * ----------------------------------------------------------------
 */
TupleTableSlot *
ExecNestLoop(NestLoopState *node)
{
      PlanState  *innerPlan;
      PlanState  *outerPlan;
      TupleTableSlot *outerTupleSlot;
      TupleTableSlot *innerTupleSlot;
      List     *joinqual;
      List     *otherqual;
      ExprContext *econtext;

      /*
       * get information from the node
       */
      ENL1_printf("getting info from node");

      joinqual = node->js.joinqual;
      otherqual = node->js.ps.qual;
      outerPlan = outerPlanState(node);
      innerPlan = innerPlanState(node);
      econtext = node->js.ps.ps_ExprContext;

      /*
       * Check to see if we're still projecting out tuples from a previous join
       * tuple (because there is a function-returning-set in the projection
       * expressions).  If so, try to project another one.
       */
      if (node->js.ps.ps_TupFromTlist)
      {
            TupleTableSlot *result;
            ExprDoneCond isDone;

            result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);
            if (isDone == ExprMultipleResult)
                  return result;
            /* Done with that source tuple... */
            node->js.ps.ps_TupFromTlist = false;
      }

      /*
       * Reset per-tuple memory context to free any expression evaluation
       * storage allocated in the previous tuple cycle.  Note this can't happen
       * until we're done projecting out tuples from a join tuple.
       */
      ResetExprContext(econtext);

      /*
       * Ok, everything is setup for the join so now loop until we return a
       * qualifying join tuple.
       */
      ENL1_printf("entering main loop");

      for (;;)
      {
            /*
             * If we don't have an outer tuple, get the next one and reset the
             * inner scan.
             */
            if (node->nl_NeedNewOuter)
            {
                  ENL1_printf("getting new outer tuple");
                  outerTupleSlot = ExecProcNode(outerPlan);

                  /*
                   * if there are no more outer tuples, then the join is complete..
                   */
                  if (TupIsNull(outerTupleSlot))
                  {
                        ENL1_printf("no outer tuple, ending join");
                        return NULL;
                  }

                  ENL1_printf("saving new outer tuple information");
                  econtext->ecxt_outertuple = outerTupleSlot;
                  node->nl_NeedNewOuter = false;
                  node->nl_MatchedOuter = false;

                  /*
                   * now rescan the inner plan
                   */
                  ENL1_printf("rescanning inner plan");

                  /*
                   * The scan key of the inner plan might depend on the current
                   * outer tuple (e.g. in index scans), that's why we pass our expr
                   * context.
                   */
                  ExecReScan(innerPlan, econtext);
            }

            /*
             * we have an outerTuple, try to get the next inner tuple.
             */
            ENL1_printf("getting new inner tuple");

            innerTupleSlot = ExecProcNode(innerPlan);
            econtext->ecxt_innertuple = innerTupleSlot;

            if (TupIsNull(innerTupleSlot))
            {
                  ENL1_printf("no inner tuple, need new outer tuple");

                  node->nl_NeedNewOuter = true;

                  if (!node->nl_MatchedOuter &&
                        (node->js.jointype == JOIN_LEFT ||
                         node->js.jointype == JOIN_ANTI))
                  {
                        /*
                         * We are doing an outer join and there were no join matches
                         * for this outer tuple.  Generate a fake join tuple with
                         * nulls for the inner tuple, and return it if it passes the
                         * non-join quals.
                         */
                        econtext->ecxt_innertuple = node->nl_NullInnerTupleSlot;

                        ENL1_printf("testing qualification for outer-join tuple");

                        if (otherqual == NIL || ExecQual(otherqual, econtext, false))
                        {
                              /*
                               * qualification was satisfied so we project and return
                               * the slot containing the result tuple using
                               * ExecProject().
                               */
                              TupleTableSlot *result;
                              ExprDoneCond isDone;

                              ENL1_printf("qualification succeeded, projecting tuple");

                              result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);

                              if (isDone != ExprEndResult)
                              {
                                    node->js.ps.ps_TupFromTlist =
                                          (isDone == ExprMultipleResult);
                                    return result;
                              }
                        }
                  }

                  /*
                   * Otherwise just return to top of loop for a new outer tuple.
                   */
                  continue;
            }

            /*
             * at this point we have a new pair of inner and outer tuples so we
             * test the inner and outer tuples to see if they satisfy the node's
             * qualification.
             *
             * Only the joinquals determine MatchedOuter status, but all quals
             * must pass to actually return the tuple.
             */
            ENL1_printf("testing qualification");

            if (ExecQual(joinqual, econtext, false))
            {
                  node->nl_MatchedOuter = true;

                  /* In an antijoin, we never return a matched tuple */
                  if (node->js.jointype == JOIN_ANTI)
                  {
                        node->nl_NeedNewOuter = true;
                        continue;         /* return to top of loop */
                  }

                  /*
                   * In a semijoin, we'll consider returning the first match,
                   * but after that we're done with this outer tuple.
                   */
                  if (node->js.jointype == JOIN_SEMI)
                        node->nl_NeedNewOuter = true;

                  if (otherqual == NIL || ExecQual(otherqual, econtext, false))
                  {
                        /*
                         * qualification was satisfied so we project and return the
                         * slot containing the result tuple using ExecProject().
                         */
                        TupleTableSlot *result;
                        ExprDoneCond isDone;

                        ENL1_printf("qualification succeeded, projecting tuple");

                        result = ExecProject(node->js.ps.ps_ProjInfo, &isDone);

                        if (isDone != ExprEndResult)
                        {
                              node->js.ps.ps_TupFromTlist =
                                    (isDone == ExprMultipleResult);
                              return result;
                        }
                  }
            }

            /*
             * Tuple fails qual, so free per-tuple memory and try again.
             */
            ResetExprContext(econtext);

            ENL1_printf("qualification failed, looping");
      }
}

/* ----------------------------------------------------------------
 *          ExecInitNestLoop
 * ----------------------------------------------------------------
 */
NestLoopState *
ExecInitNestLoop(NestLoop *node, EState *estate, int eflags)
{
      NestLoopState *nlstate;

      /* check for unsupported flags */
      Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));

      NL1_printf("ExecInitNestLoop: %s\n",
                     "initializing node");

      /*
       * create state structure
       */
      nlstate = makeNode(NestLoopState);
      nlstate->js.ps.plan = (Plan *) node;
      nlstate->js.ps.state = estate;

      /*
       * Miscellaneous initialization
       *
       * create expression context for node
       */
      ExecAssignExprContext(estate, &nlstate->js.ps);

      /*
       * initialize child expressions
       */
      nlstate->js.ps.targetlist = (List *)
            ExecInitExpr((Expr *) node->join.plan.targetlist,
                               (PlanState *) nlstate);
      nlstate->js.ps.qual = (List *)
            ExecInitExpr((Expr *) node->join.plan.qual,
                               (PlanState *) nlstate);
      nlstate->js.jointype = node->join.jointype;
      nlstate->js.joinqual = (List *)
            ExecInitExpr((Expr *) node->join.joinqual,
                               (PlanState *) nlstate);

      /*
       * initialize child nodes
       *
       * Tell the inner child that cheap rescans would be good.  (This is
       * unnecessary if we are doing nestloop with inner indexscan, because the
       * rescan will always be with a fresh parameter --- but since
       * nodeIndexscan doesn't actually care about REWIND, there's no point in
       * dealing with that refinement.)
       */
      outerPlanState(nlstate) = ExecInitNode(outerPlan(node), estate, eflags);
      innerPlanState(nlstate) = ExecInitNode(innerPlan(node), estate,
                                                               eflags | EXEC_FLAG_REWIND);

#define NESTLOOP_NSLOTS 2

      /*
       * tuple table initialization
       */
      ExecInitResultTupleSlot(estate, &nlstate->js.ps);

      switch (node->join.jointype)
      {
            case JOIN_INNER:
            case JOIN_SEMI:
                  break;
            case JOIN_LEFT:
            case JOIN_ANTI:
                  nlstate->nl_NullInnerTupleSlot =
                        ExecInitNullTupleSlot(estate,
                                                 ExecGetResultType(innerPlanState(nlstate)));
                  break;
            default:
                  elog(ERROR, "unrecognized join type: %d",
                         (int) node->join.jointype);
      }

      /*
       * initialize tuple type and projection info
       */
      ExecAssignResultTypeFromTL(&nlstate->js.ps);
      ExecAssignProjectionInfo(&nlstate->js.ps, NULL);

      /*
       * finally, wipe the current outer tuple clean.
       */
      nlstate->js.ps.ps_TupFromTlist = false;
      nlstate->nl_NeedNewOuter = true;
      nlstate->nl_MatchedOuter = false;

      NL1_printf("ExecInitNestLoop: %s\n",
                     "node initialized");

      return nlstate;
}

int
ExecCountSlotsNestLoop(NestLoop *node)
{
      return ExecCountSlotsNode(outerPlan(node)) +
            ExecCountSlotsNode(innerPlan(node)) +
            NESTLOOP_NSLOTS;
}

/* ----------------------------------------------------------------
 *          ExecEndNestLoop
 *
 *          closes down scans and frees allocated storage
 * ----------------------------------------------------------------
 */
void
ExecEndNestLoop(NestLoopState *node)
{
      NL1_printf("ExecEndNestLoop: %s\n",
                     "ending node processing");

      /*
       * Free the exprcontext
       */
      ExecFreeExprContext(&node->js.ps);

      /*
       * clean out the tuple table
       */
      ExecClearTuple(node->js.ps.ps_ResultTupleSlot);

      /*
       * close down subplans
       */
      ExecEndNode(outerPlanState(node));
      ExecEndNode(innerPlanState(node));

      NL1_printf("ExecEndNestLoop: %s\n",
                     "node processing ended");
}

/* ----------------------------------------------------------------
 *          ExecReScanNestLoop
 * ----------------------------------------------------------------
 */
void
ExecReScanNestLoop(NestLoopState *node, ExprContext *exprCtxt)
{
      PlanState  *outerPlan = outerPlanState(node);

      /*
       * If outerPlan->chgParam is not null then plan will be automatically
       * re-scanned by first ExecProcNode. innerPlan is re-scanned for each new
       * outer tuple and MUST NOT be re-scanned from here or you'll get troubles
       * from inner index scans when outer Vars are used as run-time keys...
       */
      if (outerPlan->chgParam == NULL)
            ExecReScan(outerPlan, exprCtxt);

      node->js.ps.ps_TupFromTlist = false;
      node->nl_NeedNewOuter = true;
      node->nl_MatchedOuter = false;
}

Generated by  Doxygen 1.6.0   Back to index