home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / executor / n_nestloop.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  15.6 KB  |  552 lines
  1. /* ----------------------------------------------------------------
  2.  *   FILE
  3.  *    nestloop.c
  4.  *    
  5.  *   DESCRIPTION
  6.  *    routines to support nest-loop joins
  7.  *
  8.  *   INTERFACE ROUTINES
  9.  *       ExecNestLoop     - process a nestloop join of two plans
  10.  *       ExecInitNestLoop - initialize the join
  11.  *       ExecEndNestLoop     - shut down the join
  12.  *
  13.  *   NOTES
  14.  *    
  15.  *    
  16.  *   IDENTIFICATION
  17.  *    $Header: /private/postgres/src/executor/RCS/n_nestloop.c,v 1.5 1992/08/04 17:37:58 mer Exp $
  18.  * ----------------------------------------------------------------
  19.  */
  20.  
  21. #include "executor/executor.h"
  22.  
  23.  RcsId("$Header: /private/postgres/src/executor/RCS/n_nestloop.c,v 1.5 1992/08/04 17:37:58 mer Exp $");
  24.  
  25. /* ----------------------------------------------------------------
  26.  *       ExecNestLoop(node)
  27.  *
  28.  * old comments
  29.  *       Returns the tuple joined from inner and outer tuples which 
  30.  *       satisfies the qualification clause.
  31.  *
  32.  *    It scans the inner relation to join with current outer tuple.
  33.  *
  34.  *    If none is found, next tuple form the outer relation is retrieved
  35.  *    and the inner relation is scanned from the beginning again to join
  36.  *    with the outer tuple.
  37.  *
  38.  *       Nil is returned if all the remaining outer tuples are tried and
  39.  *       all fail to join with the inner tuples.
  40.  *
  41.  *       Nil is also returned if there is no tuple from inner realtion.
  42.  *   
  43.  *       Conditions:
  44.  *         -- outerTuple contains current tuple from outer relation and
  45.  *            the right son(inner realtion) maintains "cursor" at the tuple
  46.  *            returned previously.
  47.  *              This is achieved by maintaining a scan position on the outer
  48.  *              relation.
  49.  *   
  50.  *       Initial States:
  51.  *         -- the outer child and the inner child 
  52.  *             are prepared to return the first tuple.
  53.  * ----------------------------------------------------------------
  54.  */
  55. /**** xxref:
  56.  *           ExecProcNode
  57.  ****/
  58. TupleTableSlot
  59. ExecNestLoop(node)
  60.     NestLoop node;
  61. {
  62.     NestLoopState     nlstate;
  63.     Plan          innerPlan;
  64.     Plan          outerPlan;
  65.     bool          portalFlag;
  66.     bool           needNewOuterTuple;
  67.     
  68.     TupleTableSlot      outerTupleSlot;
  69.     TupleTableSlot      innerTupleSlot;
  70.     
  71.     TupleDescriptor      tupType;
  72.     Pointer          tupValue;
  73.     List          targetList;
  74.     int              len;
  75.     
  76.     List          qual;
  77.     bool          qualResult;
  78.     ExprContext          econtext;
  79.     JoinRuleInfo    ruleInfo;
  80.     
  81.     /* ----------------
  82.      *    get information from the node
  83.      * ----------------
  84.      */
  85.     ENL1_printf("getting info from node");
  86.     
  87.     nlstate =    get_nlstate(node);
  88.     qual =       get_qpqual((Plan) node);
  89.     outerPlan =  get_outerPlan((Plan) node);
  90.     innerPlan =  get_innerPlan((Plan) node);
  91.     ruleInfo =   (JoinRuleInfo) get_ruleinfo((Join) node);
  92.     
  93.     /* ----------------
  94.      *    initialize expression context
  95.      * ----------------
  96.      */
  97.     econtext = get_cs_ExprContext((CommonState)nlstate);
  98.     
  99.     /* ----------------
  100.      *    get the current outer tuple
  101.      * ----------------
  102.      */
  103.     outerTupleSlot = get_cs_OuterTupleSlot((CommonState)nlstate);
  104.     set_ecxt_outertuple(econtext, outerTupleSlot);
  105.     
  106.     /* ----------------
  107.      *  Ok, everything is setup for the join so now loop until
  108.      *  we return a qualifying join tuple..
  109.      * ----------------
  110.      */
  111.  
  112.     if (get_cs_TupFromTlist((CommonState)nlstate)) {
  113.     TupleTableSlot  result;
  114.     bool        isDone;
  115.  
  116.     result = ExecProject(get_cs_ProjInfo((CommonState)nlstate), &isDone);
  117.     if (!isDone)
  118.         return result;
  119.     }
  120.  
  121.     ENL1_printf("entering main loop");
  122.     for(;;) {
  123.     /* ----------------
  124.      *  The essential idea now is to get the next inner tuple
  125.      *  and join it with the current outer tuple.
  126.      * ----------------
  127.      */
  128.     needNewOuterTuple = false;
  129.     
  130.     /* ----------------
  131.      *  If outer tuple is not null then that means
  132.      *  we are in the middle of a scan and we should
  133.      *  restore our previously saved scan position.
  134.      * ----------------
  135.      */
  136.     if (! TupIsNull((Pointer) outerTupleSlot)) {        
  137.         ENL1_printf("have outer tuple, restoring outer plan");
  138.         ExecRestrPos(outerPlan);
  139.     } else {
  140.         ENL1_printf("outer tuple is nil, need new outer tuple");
  141.         needNewOuterTuple = true;
  142.     }
  143.     
  144.     /* ----------------
  145.      *  portalFlag can be thought of as a
  146.      *  "need to rescan outer relation" flag.
  147.      *  I don't really understand it beyond that..  -cim 8/31/89
  148.      * ----------------
  149.      */
  150.     portalFlag =  get_nl_PortalFlag(nlstate);
  151.     if (portalFlag == false) {
  152.         ENL1_printf("portal flag false, need new outer tuple");
  153.         needNewOuterTuple = true;
  154.     }
  155.     
  156.     /* ----------------
  157.      *  if we have an outerTuple, try to get the next inner tuple.
  158.      * ----------------
  159.      */
  160.     if (!needNewOuterTuple) {
  161.         ENL1_printf("getting new inner tuple");
  162.     
  163.         innerTupleSlot = ExecProcNode(innerPlan);
  164.         set_ecxt_innertuple(econtext, innerTupleSlot);
  165.         
  166.         if (TupIsNull((Pointer) innerTupleSlot)) {
  167.         ENL1_printf("no inner tuple, need new outer tuple");
  168.         needNewOuterTuple = true;
  169.         }
  170.     }
  171.     
  172.     /* ----------------
  173.      *  loop until we have a new outer tuple and a new
  174.      *  inner tuple.
  175.      * ----------------
  176.      */
  177.     while (needNewOuterTuple) {
  178.         /* ----------------
  179.          * If portalFlag is nil, rescan outer relation.
  180.          * ----------------
  181.          */
  182.         if (portalFlag == false)
  183.         ExecReScan(outerPlan);
  184.         
  185.         /* ----------------
  186.          *    now try to get the next outer tuple
  187.          * ----------------
  188.          */
  189.         ENL1_printf("getting new outer tuple");
  190.         outerTupleSlot = ExecProcNode(outerPlan);
  191.         set_ecxt_outertuple(econtext, outerTupleSlot);
  192.         
  193.         /* ----------------
  194.          *  if there are no more outer tuples, then the join
  195.          *  is complete..
  196.          * ----------------
  197.          */
  198.         if (TupIsNull((Pointer) outerTupleSlot)) {
  199.         ENL1_printf("no outer tuple, ending join");
  200.         return NULL;
  201.         }
  202.         
  203.         /* ----------------
  204.          *  we have a new outer tuple so we mark our position
  205.          *  in the outer scan and save the outer tuple in the
  206.          *  NestLoop state
  207.          * ----------------
  208.          */
  209.         ENL1_printf("saving new outer tuple information");
  210.         ExecMarkPos(outerPlan);
  211.         set_nl_PortalFlag(nlstate, true);
  212.         set_cs_OuterTupleSlot((CommonState)nlstate, outerTupleSlot);
  213.         
  214.         /* ----------------
  215.          *    now rescan the inner plan and get a new inner tuple
  216.          * ----------------
  217.          */
  218.         
  219.         /* ----------------
  220.          *      Nest Loop joins with indexscans in the inner plan
  221.          *      are treated specially (hack hack hack).. since the
  222.          *    idea is to first get an outer tuple and then do
  223.          *      an index scan on the inner relation to find a matching
  224.          *      inner tuple, this means the inner indexscan's scan
  225.          *    key is now a function of the values in the outer tuple.
  226.          *    This means we have to recalculate the proper scan key
  227.          *    values so the index scan will work correctly.
  228.          *
  229.          *    Note: the proper thing to do would be to redesign
  230.          *    things so qualifications could refer to current attribute
  231.          *    values of tuples elsewhere in the plan..  In fact, this
  232.          *    may have to be done when we start implementing
  233.          *    bushy trees..  But for now our plans are simple and
  234.          *    we can get by doing cheezy stuff.
  235.          * ----------------
  236.          */
  237.         if (ExecIsIndexScan(innerPlan)) {
  238.         ENL1_printf("recalculating inner scan keys");
  239.         ExecUpdateIndexScanKeys((IndexScan) innerPlan, econtext);
  240.         }
  241.         
  242.         ENL1_printf("rescanning inner plan");
  243.         ExecReScan(innerPlan);
  244.         
  245.         /* ----------------
  246.          *    If we are running in a 'insert rule lock & stubs'
  247.          *    mode, insert the appropriate rule stubs to the
  248.          *    inner relation.
  249.          * ----------------
  250.          */
  251.         if (ruleInfo != (JoinRuleInfo) NULL) {
  252.         /*
  253.          * NOTE: the inner plan must be a scan!
  254.          */
  255.         ScanState       scanState;
  256.         RelationRuleInfo  relRuleInfo;
  257.         Relation       innerRelation;
  258.         Prs2OneStub       oneStub;
  259.         HeapTuple       outerHeapTuple;
  260.         Buffer           buf;
  261.         TupleDescriptor      outerTupleDesc;
  262.         TupleDescriptor   innerTupleDesc;
  263.         
  264.         if (!ExecIsSeqScan(innerPlan) && !ExecIsIndexScan(innerPlan)){
  265.             elog(WARN,"Rule stub code: inner plan not a scan");
  266.         }
  267.         
  268.         outerHeapTuple = (HeapTuple) ExecFetchTuple((Pointer)
  269.                                 outerTupleSlot);
  270.         buf = ExecSlotBuffer((Pointer)outerTupleSlot);
  271.  
  272.         /*
  273.          * add a rule stub in the inner relation.
  274.          */
  275.         scanState =         get_scanstate((Scan) innerPlan);
  276.         relRuleInfo =
  277.             get_css_ruleInfo((CommonScanState) scanState);
  278.         innerRelation =
  279.             get_css_currentRelation((CommonScanState)scanState);
  280.  
  281.         /*
  282.          * get tuple descs for the rule manager.  XXX why can't
  283.          * the rule manager just take the econtext as an argument
  284.          * and get this information itself?  ExecGetTupType is
  285.          * an obsolete way of doing things. -cim 6/3/91
  286.          */
  287.         outerTupleDesc = ExecGetTupType(outerPlan);
  288.         innerTupleDesc = ExecGetTupType(innerPlan);
  289.         
  290.         oneStub =
  291.             prs2MakeStubForInnerRelation(ruleInfo,
  292.                          outerHeapTuple,
  293.                          buf,
  294.                          outerTupleDesc,
  295.                          innerTupleDesc);
  296.         
  297.         prs2AddOneStub(relRuleInfo->relationStubs, oneStub);
  298.         relRuleInfo->relationStubsHaveChanged = true;
  299.         set_css_ruleInfo((CommonScanState)scanState, relRuleInfo);
  300.         
  301.         /*
  302.          * also store this stub to the 'ruleInfo'
  303.          */
  304.         set_jri_stub(ruleInfo, oneStub);
  305.         
  306.         /*
  307.          * update the statistics
  308.          */
  309.         prs2UpdateStats(ruleInfo, PRS2_ADDSTUB);
  310.         }
  311.  
  312.         ENL1_printf("getting new inner tuple");
  313.         
  314.         innerTupleSlot = ExecProcNode(innerPlan);
  315.         set_ecxt_innertuple(econtext, innerTupleSlot);
  316.         
  317.         if (TupIsNull((Pointer) innerTupleSlot)) {
  318.         ENL1_printf("couldn't get inner tuple - need new outer tuple");
  319.         } else {
  320.         ENL1_printf("got inner and outer tuples");
  321.         needNewOuterTuple = false;
  322.         }
  323.     }
  324.     
  325.     /* ----------------
  326.      *   at this point we have a new pair of inner and outer
  327.      *   tuples so we test the inner and outer tuples to see
  328.      *   if they satisify the node's qualification.
  329.      * ----------------
  330.      */
  331.     ENL1_printf("testing qualification");
  332.     qualResult = ExecQual(qual, econtext);
  333.     
  334.     /* ----------------
  335.      *   if we are in a 'set rule locks' mode, and the inner tuple
  336.      *   satisfies the appropriate qualification, put a new
  337.      *   lock on it.
  338.      * ----------------
  339.      */
  340.     if (ruleInfo != (JoinRuleInfo) NULL) {
  341.         RuleLock         lock;
  342.         Relation         innerRelation;
  343.         Prs2OneStub     oneStub;
  344.         HeapTuple         innerHeapTuple;
  345.         ScanState         scanState;
  346.         TupleTableSlot     scanTupleSlot;
  347.         bool        newExpLocks;
  348.         Buffer         buf;
  349.  
  350.         if (!ExecIsSeqScan(innerPlan) && !ExecIsIndexScan(innerPlan)) {
  351.         elog(WARN,"Rule stub code: inner plan not a scan");
  352.         }
  353.         scanState =     get_scanstate((Scan) innerPlan);
  354.         innerRelation =     get_css_currentRelation((CommonScanState)
  355.                             scanState);
  356.         oneStub =         get_jri_stub(ruleInfo);
  357.         scanTupleSlot =     (TupleTableSlot)
  358.         get_css_ScanTupleSlot((CommonScanState)scanState);
  359.         
  360.         innerHeapTuple = (HeapTuple)
  361.         ExecFetchTuple((Pointer)scanTupleSlot);
  362.         
  363.         buf = ExecSlotBuffer((Pointer) scanTupleSlot);
  364.         
  365.         if (prs2AddLocksAndReplaceTuple(innerHeapTuple,
  366.                         buf,
  367.                         innerRelation,
  368.                         oneStub,
  369.                         &newExpLocks)) {
  370.         prs2UpdateStats(ruleInfo, PRS2_ADDLOCK);
  371.         }
  372.         if (!newExpLocks)
  373.         qualResult = false;
  374.     }
  375.  
  376.     if (qualResult) {
  377.         /* ----------------
  378.          *  qualification was satisified so we project and
  379.          *  return the slot containing the result tuple
  380.          *  using ExecProject().
  381.          * ----------------
  382.          */
  383.         ProjectionInfo projInfo;
  384.         TupleTableSlot result;
  385.         bool           isDone;
  386.         
  387.         ENL1_printf("qualification succeeded, projecting tuple");
  388.         
  389.         projInfo = get_cs_ProjInfo((CommonState)nlstate);
  390.         result = ExecProject(projInfo, &isDone);
  391.         set_cs_TupFromTlist((CommonState)nlstate, !isDone);
  392.         return result;
  393.     } 
  394.     
  395.     /* ----------------
  396.      *  qualification failed so we have to try again..
  397.      * ----------------
  398.      */
  399.     ENL1_printf("qualification failed, looping");
  400.     }
  401. }
  402.  
  403. /* ----------------------------------------------------------------
  404.  *       ExecInitNestLoop
  405.  *   
  406.  *       Creates the run-time state information for the nestloop node
  407.  *       produced by the planner and initailizes inner and outer relations 
  408.  *       (child nodes).
  409.  * ----------------------------------------------------------------      
  410.  */
  411. /**** xxref:
  412.  *           ExecInitNode
  413.  ****/
  414. List
  415. ExecInitNestLoop(node, estate, parent)
  416.     NestLoop node;
  417.     EState   estate;
  418.     Plan     parent;
  419. {
  420.     NestLoopState   nlstate;
  421.     TupleDescriptor tupType;
  422.     Pointer        tupValue;
  423.     List        targetList;
  424.     int            len;
  425.     ExprContext        econtext;
  426.     ParamListInfo   paraminfo;
  427.     int            baseid;
  428.     
  429.     NL1_printf("ExecInitNestLoop: %s\n",
  430.            "initializing node");
  431.     
  432.     /* ----------------
  433.      *    assign execution state to node
  434.      * ----------------
  435.      */
  436.     set_state((Plan) node, (EStatePtr)estate);
  437.     
  438.     /* ----------------
  439.      *    create new nest loop state
  440.      * ----------------
  441.      */
  442.     nlstate = MakeNestLoopState(false);
  443.     set_nlstate(node, nlstate);
  444.         
  445.     /* ----------------
  446.      *  Miscellanious initialization
  447.      *
  448.      *         +    assign node's base_id
  449.      *       +    assign debugging hooks and
  450.      *       +    create expression context for node
  451.      * ----------------
  452.      */
  453.     ExecAssignNodeBaseInfo(estate, (BaseNode) nlstate, parent);
  454.     ExecAssignDebugHooks((Plan) node, (BaseNode)nlstate);
  455.     ExecAssignExprContext(estate, (CommonState)nlstate);
  456.  
  457. #define NESTLOOP_NSLOTS 1
  458.     /* ----------------
  459.      *    tuple table initialization
  460.      * ----------------
  461.      */
  462.     ExecInitResultTupleSlot(estate, (CommonState)nlstate);
  463.          
  464.     /* ----------------
  465.      *    now initialize children
  466.      * ----------------
  467.      */
  468.     ExecInitNode(get_outerPlan((Plan)node), estate, (Plan)node);
  469.     ExecInitNode(get_innerPlan((Plan)node), estate, (Plan) node);
  470.     set_nl_PortalFlag(nlstate, true);
  471.         
  472.     /* ----------------
  473.      *     initialize tuple type and projection info
  474.      * ----------------
  475.      */
  476.     ExecAssignResultTypeFromTL((Plan) node, (CommonState)nlstate);
  477.     ExecAssignProjectionInfo((Plan) node, (CommonState) nlstate);
  478.     
  479.     /* ----------------
  480.      *  finally, wipe the current outer tuple clean.
  481.      * ----------------
  482.      */
  483.     set_cs_OuterTupleSlot((CommonState)nlstate, NULL);
  484.     set_cs_TupFromTlist((CommonState)nlstate, false);
  485.     
  486.     NL1_printf("ExecInitNestLoop: %s\n",
  487.            "node initialized");
  488.     return LispTrue;
  489. }
  490.  
  491. int
  492. ExecCountSlotsNestLoop(node)
  493.     Plan node;
  494. {
  495.     return ExecCountSlotsNode(get_outerPlan(node)) +
  496.        ExecCountSlotsNode(get_innerPlan(node)) +
  497.        NESTLOOP_NSLOTS;
  498. }
  499.  
  500. /* ----------------------------------------------------------------
  501.  *       ExecEndNestLoop
  502.  *   
  503.  *       closes down scans and frees allocated storage
  504.  * ----------------------------------------------------------------
  505.  */
  506. /**** xxref:
  507.  *           ExecEndNode
  508.  ****/
  509. List
  510. ExecEndNestLoop(node)
  511.     NestLoop node;
  512. {
  513.     NestLoopState   nlstate;
  514.     Pointer        tupValue;
  515.     
  516.     NL1_printf("ExecEndNestLoop: %s\n",
  517.            "ending node processing");
  518.     
  519.     /* ----------------
  520.      *    get info from the node
  521.      * ----------------
  522.      */
  523.     nlstate =  get_nlstate(node);
  524.     
  525.     /* ----------------
  526.      *    Free the projection info
  527.      *
  528.      *  Note: we don't ExecFreeResultType(nlstate) 
  529.      *        because the rule manager depends on the tupType
  530.      *          returned by ExecMain().  So for now, this
  531.      *          is freed at end-transaction time.  -cim 6/2/91     
  532.      * ----------------
  533.      */    
  534.     ExecFreeProjectionInfo((CommonState)nlstate);
  535.  
  536.     /* ----------------
  537.      *    close down subplans
  538.      * ----------------
  539.      */
  540.     ExecEndNode(get_outerPlan((Plan) node));
  541.     ExecEndNode(get_innerPlan((Plan) node));
  542.  
  543.     /* ----------------
  544.      *    clean out the tuple table 
  545.      * ----------------
  546.      */
  547.     ExecClearTuple((Pointer) get_cs_ResultTupleSlot((CommonState)nlstate));
  548.     
  549.     NL1_printf("ExecEndNestLoop: %s\n",
  550.            "node processing ended");
  551. }
  552.