home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / planner / plan / recurplanner.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  35.9 KB  |  1,253 lines
  1. /***********************************************************************
  2.  ** *    Recursion Planner (recurplanner.c)                * **
  3.  ** *        Jimmy Bell                        * **
  4.  ** *                                    * **
  5.  ***********************************************************************
  6.  */
  7.  
  8. /* RcsId ("$Header: /private/postgres/src/planner/plan/RCS/recurplanner.c,v 1.4 1990/10/17 15:36:00 choi Exp $"); */
  9.  
  10. #include "planner/recurplanner.h"
  11. #include "parser/parsetree.h"
  12. #include "utils/log.h"
  13.  
  14. /* ----------------
  15.  *    Recursive creator declaration
  16.  * ----------------
  17.  */
  18. extern Recursive RMakeRecursive();
  19.  
  20.  
  21. /* JJJ -DEBUGing routine */
  22. void
  23. Jshow (msg, obj)
  24. char    *msg;
  25. LispValue    obj;
  26. {
  27. printf("\n *** JJJ : %s : ", msg);
  28. lispDisplay(obj,0);
  29. }
  30. /* JJJ */
  31.  
  32. /* JJJ -Message routine */
  33. void
  34. Jprint (msg)
  35. char  *msg;
  36. {
  37. printf("\n *** JJJ -- %s -- ",msg);
  38. }
  39. /* JJJ */
  40.  
  41.  
  42.  
  43.  
  44. Recursive        /* Recursive Node containing query plan */
  45. make_recursive (recursiveMethod, command, initPlans, loopPlans,
  46.         cleanupPlans, checkpoints, resultRelationName)
  47.     RecursiveMethod    recursiveMethod;
  48.     LispValue    command;
  49.     List        initPlans;
  50.     List        loopPlans;
  51.     List        cleanupPlans;
  52.     List        checkpoints;
  53.         LispValue    resultRelationName;
  54. {
  55.     Recursive node = RMakeRecursive();
  56.  
  57.     set_cost(node,0.0);
  58.     set_fragment(node,0);
  59.     set_state(node,(EState)NULL);
  60.     set_qptargetlist(node,(TargetList)NULL);
  61.     set_qpqual(node,LispNil);
  62.     set_lefttree(node,(Plan)NULL);
  63.     set_righttree(node,(Plan)NULL);
  64.  
  65.     set_recurMethod(node,recursiveMethod);
  66.     set_recurCommand(node,command);
  67.     set_recurInitPlans(node,initPlans);
  68.     set_recurLoopPlans(node,loopPlans);
  69.     set_recurCleanupPlans(node,cleanupPlans);
  70.     set_recurCheckpoints(node,checkpoints);
  71.     set_recurResultRelationName(node,resultRelationName);
  72.  
  73.     return(node);
  74. }
  75.  
  76. /****
  77.  *    functions to facilitate conversions between the internal
  78.  *    form of plans and utility requests (like create FOO) and
  79.  *    their list equivalents.
  80.  */
  81.  
  82. GeneralPlan        /* either a utility request or a plan */
  83. PlanOrUtilityToGeneralPlan (isUtility, planOrUtility)
  84.     bool        isUtility;    /* false indicates 'plan' */
  85.     PlanOrUtility    planOrUtility;
  86. {
  87.     GeneralPlan    generalPlan;
  88.  
  89.     generalPlan.isUtility = isUtility;
  90.     if (isUtility)
  91.         generalPlan.planOrUtility.utility =
  92.             lispString(planOrUtility.utility);
  93.     else
  94.         generalPlan.planOrUtility.plan = planOrUtility.plan;
  95.  
  96.     return generalPlan;
  97. }
  98.  
  99. List            /* List form of General Plan */
  100. GeneralPlanToList (generalPlan)
  101.     GeneralPlan    generalPlan;    /* general plan to be converted */
  102. {
  103.     if (generalPlan.isUtility)
  104.         return lispCons(lispInteger(generalPlan.isUtility),
  105.                 lispCons(generalPlan.planOrUtility.utility,
  106.                     LispNil));
  107.     else
  108.         return lispCons(lispInteger(generalPlan.isUtility),
  109.                                 lispCons(generalPlan.planOrUtility.plan,
  110.                                         LispNil));
  111. }
  112.  
  113. GeneralPlan        /* General Plan extracted from List form */
  114. ListToGeneralPlan (list)
  115.     List    list;    /* list being examined */
  116. {
  117.     GeneralPlan    generalPlan;
  118.  
  119.     if ( CInteger(CAR(list)) == 1 ) {
  120.         generalPlan.isUtility = true;
  121.         generalPlan.planOrUtility.utility = 
  122.             (UtilityRequest) CAR(CDR(list));
  123.     }
  124.     else {
  125.         generalPlan.isUtility = false;
  126.                 generalPlan.planOrUtility.plan = (Plan) CAR(CDR(list));
  127.     }
  128.     return generalPlan;
  129. }
  130.  
  131. GeneralPlan        /* containing utility request from string */
  132. StringToGeneralPlan(str)
  133.     String        str;
  134. {
  135.     GeneralPlan    generalPlan;
  136.  
  137.       generalPlan.isUtility = true;
  138.     generalPlan.planOrUtility.utility = lispString(str);
  139.  
  140.     return generalPlan;
  141. }
  142.  
  143. /*
  144.  *    end of conversion functions
  145.  *******
  146.  */
  147.  
  148. /*******
  149.  *    functions for checking linearity and verifying recursion
  150.  */
  151.  
  152. String            /* name of result  relation */
  153. ParseTreeGetResultRelationName(parseTree)
  154.     ParseTree    parseTree;
  155. {
  156.     LispValue    resultRelation;
  157.     RangeTable    rangeTable;
  158.     String        resultName;
  159.  
  160.     resultRelation = ParseTreeGetResultRelation( parseTree );
  161.     rangeTable = ParseTreeGetRangeTable( parseTree );
  162.  
  163.     if ( null(resultRelation) )
  164.       elog(WARN,"No result relation specified");
  165.     else if ( lispIntegerp(resultRelation) )
  166.       resultName = CString(rt_relname(
  167.                     nth (CInteger(resultRelation)-1,rangeTable)));
  168.     else
  169.       resultName = CString(CAR(CDR(resultRelation)));
  170.  
  171.     return resultName;
  172. }
  173.  
  174. /*
  175.  *    ParseTreeGetVariablesOnResultRelation --
  176.  *        Take short-cut to approximate the number of tuple
  177.  *        var's used to refer to result relation.  I count
  178.  *        occurrences of result's name string in range table.
  179.  */
  180.  
  181. int        /* number of tuple variables on result relation */
  182. ParseTreeGetVariablesOnResultRelation(parseTree)
  183.     ParseTree    parseTree;
  184. {
  185.     String        resultName;
  186.     RangeTable    rangeTable;
  187.     LispValue    element;
  188.     int        count;
  189.  
  190.     rangeTable = ParseTreeGetRangeTable( parseTree );
  191.     resultName = ParseTreeGetResultRelationName( parseTree );
  192.     count = 0;
  193.     foreach(element, rangeTable) {
  194.       if ( strcmp(CString(rt_relname(CAR(element))),resultName) == 0 )
  195.         count++;
  196.     }
  197.  
  198.     return count;
  199. }
  200.  
  201. /*
  202.  *    RecursiveQueryGetLinearity --
  203.  *        Returns the number of distinct tuple variables in the
  204.  *        query which reference the result relation.  If the user
  205.  *        has not wasted tuple variables, this will be the level
  206.  *        of recursion.  In delete and replace, a tuple variable
  207.  *        is automatically declared for the result relation.
  208.  *        Additional ones for any command are declared with the
  209.  *        "from" clause.
  210.  *
  211.  *    Append* is only recursive if an assignment in the target list or
  212.  *        part of the qualification is based a tuple variable of
  213.  *        the result relation.  If the user references the result
  214.  *        by name or declares tuple variables on it, assume recursive.
  215.  *
  216.  *    Retrieve* is similar.  We assume that the user has referenced
  217.  *        the result relation by name, so if any additional
  218.  *        tuple var's are declared for the result, we assume
  219.  *        non-linearity.
  220.  *
  221.  *    Delete* is recursive only if an aggregate function or rule is
  222.  *        used which is sensitive either to a decrease in the
  223.  *        number of tuples, or to the absence of particular tuples.
  224.  *        The not-in operator is also hole-sensitive.  If one of
  225.  *        these 3 references the result relation, it should be
  226.  *        assumed to be recursive (linear if exactly one tuple var).
  227.  *        We assume that since one provided it is used this way.
  228.  *        In the absence of not-in, this is not supported.
  229.  *
  230.  *    Replace* is assumed to be recursive since mere assignment from
  231.  *        other relations based on a tuples field values can
  232.  *        cause tuples to requalify on the nexxt iteration.  If
  233.  *        additional tuple var's are declared, assumed nonlinear.
  234.  *
  235.  *    Execute* not supported at all.
  236.  */
  237.  
  238. int            /* 0 if non-recursive, 1 if linear, 2+ if nonlinear */
  239. RecursiveQueryGetLinearity(parseTree)
  240.     ParseTree    parseTree;
  241. {
  242.     int    resultRelationVarCount;
  243.  
  244.     resultRelationVarCount = 
  245.       ParseTreeGetVariablesOnResultRelation(parseTree);
  246.     switch ((Command) CInteger(ParseTreeGetCommandType(parseTree))) {
  247.       case APPEND:
  248.       case RETRIEVE:
  249.       case DELETE:
  250.         return resultRelationVarCount;
  251.         break;
  252.       case REPLACE:
  253.         if ( resultRelationVarCount == 0 ) {
  254.           return 1;
  255.         }
  256.         return ( resultRelationVarCount );
  257.       case EXECUTE:
  258.         elog(WARN,
  259.              "RecursiveQueryGetLinearity: 'execute' not supported");
  260.       default:
  261.         elog(WARN,
  262.              "RecursiveQueryGetLinearity: command not recognized");
  263.     }
  264. }
  265.  
  266. /*
  267.  *    RecursiveMethodChoose -
  268.  *        Determines which evaluation method to use on a recursive
  269.  *        query.  Chooses between Naive and Seminaive based on a
  270.  *        simplified linearity check.  Signals that the query is
  271.  *        not recursive at all by returning RecursiveMethodNone,
  272.  *        in which case the standard planner will take over.
  273.  */
  274.  
  275. RecursiveMethod        /* the optimal evaluation method to use */
  276. RecursiveMethodChoose(parseTree)
  277.     ParseTree    parseTree;    /* parse tree of query in question */
  278. {
  279.     switch (RecursiveQueryGetLinearity(parseTree)) {
  280.       case 0:
  281.         return RecursiveMethodNone;
  282.         break;
  283.       case 1:
  284.         return RecursiveMethodSemiNaive;
  285.         break;
  286.       default:
  287.         return RecursiveMethodNaive;
  288.         break;
  289.     }
  290. }
  291.  
  292. /* JJJ - Needed for hacky delete, but don't worry */
  293.  
  294. /* assume clause has no subparts, since in cnf */
  295. bool        /* true iff clause references given range table entry */
  296. ClauseRefersTo( clause, rangeTableIdx )
  297.     List        clause;
  298.     LispValue    rangeTableIdx;
  299. {
  300. /* *** DONE *** */
  301.     List        variableList;
  302.  
  303.     foreach(variableList,pull_var_clause(clause)) {
  304.       if ( equal(rangeTableIdx,get_varno(CAR(variableList))) )
  305.         return true;
  306.     }
  307.  
  308.     return false;
  309. }
  310.  
  311. List        /* list of indexes to RT found in clause, except given one */
  312. ClauseGetOtherRefs ( clause, rangeTableIdx )
  313.     List        clause;
  314.     LispValue    rangeTableIdx;
  315. {
  316. /* *** DONE *** */
  317.     List        indexList;
  318.     LispValue    varNumber;
  319.     List        subList;
  320.  
  321.     indexList = lispList();
  322.  
  323.         foreach(subList,pull_var_clause(clause)) {
  324.       varNumber = (LispValue) get_varno(CAR(subList));
  325.       if (!equal(varNumber,rangeTableIdx) && !member(varNumber,indexList))
  326.         indexList = append1(indexList,varNumber);
  327.     }
  328.  
  329.     return indexList;
  330. }
  331.  
  332. List        /* list if RT indexes which only appear in one disjunct */
  333. BindingListGetSolos ( bindingList, conjunct )
  334.     List        bindingList;
  335.     List        conjunct;
  336. {
  337. /* *** DONE *** */
  338.     LispValue    index;
  339.     List        newBindingList;
  340.     List        list;
  341.     List        varList;
  342.  
  343.     newBindingList = lispList();
  344.     varList = pull_var_clause(conjunct);
  345.  
  346.     foreach( list, bindingList ) {
  347.       index = CAR(list);
  348.       if ( ! member(index,varList) )
  349.         newBindingList = append1(newBindingList,index);
  350.     }
  351.  
  352.     return newBindingList;
  353. }
  354.  
  355. /* JJJ  remove_duplicates(foo,test);
  356.     LispRemove(foo,bar); value bar;
  357.     LispDelete(val,list);  auto;
  358.     set_difference(source,sub); value;
  359.     push(this,onlist); value;
  360.     integerp(foo);bool;
  361.     findif;
  362.     lispList(); value;
  363. */
  364.     
  365.  
  366. /*************
  367.  *    Removes the disjuncts which refer to the given tuple variable,
  368.  *    and recursively removes occurrences of tuple variables
  369.  *    which only have meaning in the presence of the deleted disjunct.
  370.  *
  371.  *    Assumes qualification has already been preprocessed.
  372.  *************
  373.  */
  374. Qualification        /* qual without references to certain variables */
  375. QualificationYankReferences(qual,rangeTableIdx)
  376.     Qualification    qual;
  377.     LispValue    rangeTableIdx;
  378. {
  379.     Qualification    newQual;
  380.     LispValue    list;
  381.     LispValue    subList;
  382.     List        bindingList;
  383.     LispValue    bindingSubList;
  384.     List        andClauseArg;
  385.     List        newAndClauseArgs;
  386.     List        orClauseArg;
  387.     List        newOrClauseArgs;
  388.         LispValue    newRangeTableIdx;
  389.     bool        isANotClause;
  390.  
  391.     /* Needs to be extended to deal with functions, etc. */
  392.  
  393.     /* qual is already preprocessed */
  394.  
  395.     if ( null(qual) )
  396.       return qual;
  397.     else if ( and_clause(qual) ) {
  398.       newAndClauseArgs = lispList();
  399.       foreach(list,get_andclauseargs(qual)) {
  400.         andClauseArg = CAR(list);
  401.         if ( not_clause(andClauseArg) ) {
  402.           isANotClause = true;
  403.           andClauseArg = get_orclauseargs(andClauseArg);
  404.         }
  405.         else
  406.           isANotClause = false;
  407.  
  408. /* JJJ *** need another check for NOT clauses */
  409.  
  410.         if ( or_clause(andClauseArg) ) {
  411.           newOrClauseArgs = lispList();
  412.           foreach(subList,get_orclauseargs(andClauseArg)) {
  413.         orClauseArg = CAR(subList);
  414.         if ( ClauseRefersTo(orClauseArg,rangeTableIdx) ) {
  415.           /* omit it, and others (if this was necessary instance) */
  416.           bindingList = ClauseGetOtherRefs(orClauseArg,rangeTableIdx);
  417.           bindingList = BindingListGetSolos(bindingList,andClauseArg);
  418.           /* construct newQual */
  419.           newAndClauseArgs =
  420.             append( newAndClauseArgs, ((isANotClause) ?
  421.                  make_notclause( make_orclause(append(
  422.                          newOrClauseArgs,subList))) :
  423.                  make_orclause(append(newOrClauseArgs,subList))) );
  424.           newQual = make_andclause(append(newAndClauseArgs,
  425.                           list));
  426.           foreach(bindingSubList,bindingList) {
  427.             newQual = QualificationYankReferences(newQual,
  428.                               CAR(bindingSubList));
  429.           }
  430. /* JJJ */      /* to avoid reconstructing my variables ... this is slow */
  431.           return QualificationYankReferences(newQual,
  432.                               lispInteger(0));
  433.         }
  434.         else
  435.           newOrClauseArgs = append1( newOrClauseArgs, orClauseArg );
  436.           }
  437.           newAndClauseArgs = append( newAndClauseArgs,
  438.         ( (isANotClause) ? make_notclause(
  439.                     make_orclause(newOrClauseArgs)) :
  440.                    make_orclause(newOrClauseArgs)) );
  441.         }
  442.         else if ( is_clause(andClauseArg) ) {
  443.           /* assume it is a simple qualification */
  444.           if ( ! ClauseRefersTo(andClauseArg,rangeTableIdx) )
  445.         newAndClauseArgs = append1( newAndClauseArgs,
  446.                             ( (isANotClause) ?
  447.                          make_notclause(andClauseArg ) :
  448.                          andClauseArg) );
  449.         }
  450.         else
  451.           elog(WARN,"Bad And-Clause arg. in prep'd Qualification");
  452.       }
  453.       return make_andclause(newAndClauseArgs);
  454.     }
  455.     else if ( or_clause(qual) ) {
  456.       newOrClauseArgs = lispList();
  457.       foreach(list,get_orclauseargs(qual)) {
  458.         orClauseArg = CAR(list);
  459.         if ( ClauseRefersTo(orClauseArg,rangeTableIdx) ) {
  460.           /* omit it, and leave others ... */
  461.         }
  462.         else
  463.           newOrClauseArgs = append1( newOrClauseArgs, orClauseArg );
  464.       }
  465.       return make_orclause(newOrClauseArgs);
  466.       
  467.     }
  468.     else if ( is_funcclause(qual) ) {
  469.       elog(WARN,"Can't trim functions in recursion module");
  470.     }
  471.     else if ( not_clause(qual) ) {
  472.       return make_notclause(
  473.               QualificationYankReferences(get_notclausearg(qual),
  474.                           rangeTableIdx));
  475.     }
  476.     else if ( is_clause(qual) ) {
  477.       if ( ClauseRefersTo(qual,rangeTableIdx) )
  478.         return LispNil;
  479.       else
  480.         return qual;
  481.     }
  482.     else if ( single_node(qual) ) {
  483.       elog(WARN,"Can't deal with single node in qualification");
  484.     }
  485.     else
  486.       elog(WARN,"Unknown clause type in qualification");
  487.  
  488.  
  489.     return qual;
  490. }
  491.  
  492. /*
  493.  *    RetrieveRemoveRecursion --
  494.  *        Removes recursive traits from the qualification of the
  495.  *        query's parsetree.  Does not affect target list, since
  496.  *        the query as written is assumed to work in the absence
  497.  *        of the result relation for the first pass.  This view
  498.  *        of the command may change in the future.
  499.  * 
  500.  *        Does not change the range table, so hopefully the
  501.  *        most efficient plan will still be produced.  And
  502.  *        hopefully no code depend on all the relations in the
  503.  *        range table begin used.
  504.  */
  505.  
  506. ParseTree        /* parse tree of retrieve without self-reference */
  507. RetrieveRemoveRecursion (parseTree)
  508.     ParseTree    parseTree;
  509. {
  510.     Qualification    qual;
  511.     Qualification    newQual;
  512.  
  513.     qual = cnfify(ParseTreeGetQualification(parseTree),
  514.               ParseTreeGetTargetList(parseTree));
  515.            newQual = cnfify(QualificationYankReferences(qual,0),
  516.              ParseTreeGetTargetList(parseTree));
  517.  
  518.     return lispCons(ParseTreeGetRoot(parseTree),
  519.              lispCons(ParseTreeGetTargetList(parseTree),
  520.            lispCons(newQual, LispNil)));
  521. }
  522.  
  523. LispValue        /* new index into range table */
  524. RangeTableGetReplacementIndex(rangeTable,newRelationName,oldIndex)
  525.      RangeTable        rangeTable;
  526.      String        newRelationName;
  527.      LispValue        oldIndex;
  528. {
  529.   String        oldName;
  530.   int            countVarsWithOldName;
  531.   int            currentIndex;
  532.   List            list;
  533.   int            countVarsWithNewName;
  534.   int            i;
  535.  
  536.   oldName = CString(rt_relname(nth(CInteger(oldIndex)-1,rangeTable)));
  537.  
  538.   countVarsWithOldName = 0;
  539.   currentIndex = 0;
  540.   foreach( list, rangeTable ) {
  541.     currentIndex += 1;
  542.     if ( strcmp(CString(rt_relname(CAR(list))),oldName) == 0 ) {
  543.       countVarsWithOldName += 1;
  544.     if ( currentIndex == CInteger(oldIndex) )
  545.       break;
  546.     }
  547.   }
  548.  
  549.   countVarsWithNewName = 0;
  550.   currentIndex = 0;
  551.   foreach( list, rangeTable ) {
  552.     currentIndex += 1;
  553.     if ( strcmp(CString(rt_relname(CAR(list))),newRelationName) == 0 ) {
  554.       countVarsWithNewName += 1;
  555.       if ( countVarsWithNewName == countVarsWithOldName ) {
  556.     return lispInteger(currentIndex);
  557.       }
  558.     }
  559.   }
  560.  
  561.   /* not found, so create enough new entries */
  562.   for( i = 1; i <= (countVarsWithOldName - countVarsWithNewName); i++ ) {
  563.     nappend1(rangeTable,lispCons(lispString(newRelationName),
  564.             lispCons(lispInteger(0),
  565.             lispCons(lispInteger(0),
  566.             lispCons(LispNil,
  567.             lispCons(LispNil, LispNil))))) );
  568.  
  569.   }
  570.  
  571.   return 
  572.     lispInteger( currentIndex + countVarsWithOldName - countVarsWithNewName );
  573. }
  574.  
  575. void        /* doesn't assume cnf form */
  576. ClauseInstallTemps(clause,oldResultRelation,newChiefResultName,newExtraResultName,rangeTable)
  577.      List        clause;
  578.      LispValue        oldResultRelation;
  579.      String        newChiefResultName;    /* main var for result */
  580.      String        newExtraResultName;    /* others found in parse */
  581.      RangeTable        rangeTable;        /* to be changed, if needed */
  582. {
  583.   int            oldChiefResultIndex;
  584.   String        oldResultName;
  585.   LispValue        newRangeTableIndex;
  586.   List            list;
  587.  
  588. /* JJJ **** redo */
  589.   oldChiefResultIndex = CInteger(oldResultRelation);
  590.   oldResultName = CString(rt_relname(nth(oldChiefResultIndex-1,rangeTable)));
  591.  
  592.   if ( null(clause) )
  593.     return;
  594.   else if (IsA (clause,Var)) {
  595.     /* may need refining */
  596.     if ( ( newChiefResultName != NULL ) && 
  597.     ( CInteger(get_varno(clause)) == oldChiefResultIndex ) ) {
  598.       newRangeTableIndex = RangeTableGetReplacementIndex(rangeTable,
  599.                              newChiefResultName,
  600.                              get_varno(clause));
  601.       set_varno(clause, newRangeTableIndex);
  602.       CAR(get_varid(clause)) = newRangeTableIndex;
  603.     }
  604.     else if ( ( newExtraResultName != NULL ) &&
  605.          ( strcmp(CString(rt_relname(nth(CInteger(get_varno(clause))-1,
  606.                          rangeTable))),
  607.               oldResultName) == 0 ) ) {
  608.       newRangeTableIndex = RangeTableGetReplacementIndex(rangeTable,
  609.                              newExtraResultName,
  610.                              get_varno(clause));
  611.       set_varno(clause, newRangeTableIndex);
  612.       CAR(get_varid(clause)) = newRangeTableIndex;
  613.     }
  614.     else {
  615.       /* leave it alone */
  616.     }
  617.   }
  618.   else if ( single_node (clause) )
  619.     return;
  620.   else if ( and_clause(clause) ) {
  621.     foreach( list, get_andclauseargs(clause) ) {
  622.       ClauseInstallTemps(CAR(list),
  623.              oldResultRelation,
  624.              newChiefResultName,
  625.              newExtraResultName,
  626.              rangeTable);
  627.     }
  628.     return;
  629.   }
  630.   else if ( or_clause(clause) ) {
  631.     foreach( list, get_orclauseargs(clause) ) {
  632.       ClauseInstallTemps(CAR(list),
  633.              oldResultRelation,
  634.              newChiefResultName,
  635.              newExtraResultName,
  636.              rangeTable);
  637.     }
  638.     return;
  639.   }
  640.   else if ( is_funcclause(clause) ) {
  641.     foreach( list, get_funcargs(clause) ) {
  642.       ClauseInstallTemps(CAR(list),
  643.              oldResultRelation,
  644.              newChiefResultName,
  645.              newExtraResultName,
  646.              rangeTable);
  647.     }
  648.     return;
  649.   }
  650.   else if ( not_clause(clause) ) {
  651.     ClauseInstallTemps(get_notclausearg(clause),
  652.                oldResultRelation,
  653.                newChiefResultName,
  654.                newExtraResultName,
  655.                rangeTable);
  656.  
  657.     return;
  658.   }
  659.   else if ( is_clause(clause) ) {
  660.     ClauseInstallTemps(get_leftop(clause),
  661.                oldResultRelation,
  662.                newChiefResultName,
  663.                newExtraResultName,
  664.                rangeTable);
  665.     ClauseInstallTemps(get_rightop(clause),
  666.                oldResultRelation,
  667.                newChiefResultName,
  668.                newExtraResultName,
  669.                rangeTable);
  670.     return;
  671.   }
  672.   else
  673.     elog(WARN,"Can't install temporaries in this clause");
  674. }
  675.  
  676. void
  677. TargetListInstallTemps(targetList,
  678.                oldResultRelation,
  679.                newChiefResultName,
  680.                newExtraResultName,
  681.                rangeTable)
  682.      TargetList        targetList;        /* to be modified */
  683.      LispValue        oldResultRelation;
  684.      String        newChiefResultName;    /* main var for result */
  685.      String        newExtraResultName;    /* others found in parse */
  686.      RangeTable        rangeTable;        /* to be changed, if needed */
  687. {
  688.   int            oldChiefResultIndex;
  689.   String        oldResultName;
  690.   LispValue        newRangeTableIndex;
  691.   LispValue        resultNumber;
  692.   List            list;
  693.  
  694.   oldChiefResultIndex = CInteger(oldResultRelation);
  695.   oldResultName = CString(rt_relname(nth(oldChiefResultIndex-1,rangeTable)));
  696.  
  697.   foreach( list, targetList ) {
  698.     resultNumber = lispInteger(get_resno(tl_resdom(CAR(list))));
  699.     if ( CInteger(resultNumber) == oldChiefResultIndex ) {
  700.       if ( newChiefResultName != NULL ) {
  701. /*
  702.     newRangeTableIndex = RangeTableGetReplacementIndex(rangeTable,
  703.                                newChiefResultName,
  704.                                resultNumber);
  705.     set_resno(tl_resdom(CAR(list)), newRangeTableIndex);
  706. */
  707.     /* JJJ -- ask jeff how to recurse down expressions */
  708.       }
  709.     }
  710.     else if ( strcmp(CString(rt_relname(nth(CInteger(resultNumber)-1,
  711.                         rangeTable))),
  712.              oldResultName) == 0 ) {
  713.       if ( newExtraResultName != NULL ) {
  714. /*
  715.     newRangeTableIndex = RangeTableGetReplacementIndex(rangeTable,
  716.                                newExtraResultName,
  717.                                resultNumber);
  718.     set_resno(tl_resdom(CAR(list)), newRangeTableIndex);
  719. */
  720.     /* JJJ -- ask jeff how to recurse down expressions */
  721.       }
  722.     }
  723.     else {
  724.       /* leave it alone ??? */
  725.       /* JJJ -- ask jeff how to recurse down expressions */
  726.     }
  727.     
  728.   }
  729. }
  730.  
  731. Plan    /* plan for recursive query, with recursion node at root */
  732. RecursiveQueryPlan (parseTree)
  733.      ParseTree    parseTree;    /* parse tree of query in question */
  734. {
  735. /* JJJ * current */
  736.   ParseTree        preppedParseTree;
  737.   TargetList        preppedTargetList;
  738.   Qualification        preppedQualification;
  739.  
  740.   ParseTree        scratchParseTree;
  741.   RangeTable        scratchRangeTable;    /* don't change pointer */
  742.   Plan            scratchPlan;
  743.  
  744.   String        scratchString;
  745.  
  746.   List            initPlans;
  747.   List            loopPlans;
  748.   List            cleanupPlans;
  749.  
  750.   List            preppedResultRelation;
  751.   String        preppedResultRelationName;
  752.   LispValue        preppedCommandType;
  753.  
  754.   const String        tempRelationFakeNameA = "pg_temp_A";
  755.   const String        tempRelationFakeNameB = "pg_temp_B";
  756. /* ** */
  757.  
  758.  
  759.     ParseTree    pureRecursiveQuery;
  760.     ParseTree    newParseTree;
  761.     ParseTree    workParseTree;
  762.     LispValue    newCommandType;
  763.     List        newResultRelation;
  764.     List        newRoot;
  765.     Plan        stdPlan;
  766.     Plan            newPlan;
  767.     Plan            newPlan2;
  768.     Plan            newPlan3;
  769.     Plan        pureRecursivePlan;
  770.     RecursiveMethod    recursiveMethod;
  771.     List        checkpoints;
  772.     String        utility;
  773.     String        commandString;
  774.     String        commandString2;
  775.  
  776. Jprint("RecursiveQueryPlan");
  777.  
  778.     if ( null(ParseTreeGetResultRelation(parseTree)) ) {
  779.             elog(WARN,
  780.              "RecursiveQueryPlan: retrieve* to portal not supported");
  781.     }
  782.  
  783.      recursiveMethod = RecursiveMethodChoose(parseTree);
  784.     if ( recursiveMethod == RecursiveMethodNone )
  785.         return (Plan)NULL;
  786.  
  787. Jprint("passed recur. test");
  788.  
  789. /* JJJ *** current variables *** */
  790.   preppedParseTree = (ParseTree) lispCopy(parseTree);
  791.  
  792. Jshow("prepped parse tree",preppedParseTree);
  793.  
  794.   preppedResultRelation = ParseTreeGetResultRelation( preppedParseTree );
  795.   preppedResultRelationName =
  796.     ParseTreeGetResultRelationName( preppedParseTree );
  797.   preppedTargetList =
  798.     preprocess_targetlist(ParseTreeGetTargetList(preppedParseTree),
  799.               CInteger(ParseTreeGetCommandType(preppedParseTree)),
  800.               ParseTreeGetResultRelation(preppedParseTree),
  801.               ParseTreeGetRangeTable(preppedParseTree));
  802.   ParseTreeGetTargetList(preppedParseTree) = preppedTargetList;
  803.  
  804. Jshow("prepped parse tree after tl",preppedParseTree);
  805.  
  806.   preppedQualification = cnfify(ParseTreeGetQualification(preppedParseTree));
  807.  
  808. Jshow("qual after cnf",preppedQualification);
  809.  
  810.   ParseTreeGetQualification(preppedParseTree) = preppedQualification;
  811.  
  812. Jshow("prepped parse tree after q",preppedParseTree);
  813.  
  814.   preppedCommandType = ParseTreeGetCommandType(preppedParseTree);
  815.  
  816. /* scratch stuff */
  817.   scratchParseTree = (ParseTree) lispCopy(preppedParseTree);
  818.   scratchRangeTable = ParseTreeGetRangeTable(scratchParseTree);
  819. /* *** */
  820.  
  821.  
  822.  
  823. /* JJJ ****** check setf and == and = */
  824.  
  825.     switch (recursiveMethod) {
  826.       case RecursiveMethodNaive:
  827.  
  828. Jprint("Naive");
  829.  
  830.            switch ((Command) CInteger(preppedCommandType)) {
  831.           case APPEND:
  832. Jprint("Append");
  833. /* JJJ *** DONE *** */
  834. /* -------------------------
  835.  *  Example :  append* ANCESTOR( PARENT.name, PARENT.father )
  836.  *         where PARENT.name = "Jimmy"
  837.  *         or ANCESTOR.ancestor = PARENT.name
  838.  *
  839.  *  Goes to :
  840.  *    INIT -    append ANCESTOR( name = PARENT.name, ancestor = PARENT.father )
  841.  *          where PARENT.name = "Jimmy"
  842.  *          or ANCESTOR.ancestor = PARENT.name
  843.  *          
  844.  *    LOOP -    append ANCESTOR( name = PARENT.name, ancestor = PARENT.father )
  845.  *          where PARENT.name = "Jimmy"
  846.  *          or ANCESTOR.ancestor = PARENT.name
  847.  *          
  848.  *    CLEANUP -    (nothing)
  849.  * -------------------------
  850.  */
  851.  
  852. /* --------------
  853.  * INIT :
  854.  *  "append ANCESTOR( name = PARENT.name, ancestor = PARENT.father )
  855.  *          where PARENT.name = "Jimmy"
  856.  *          or ANCESTOR.ancestor = PARENT.name"
  857.  *    requires no changes in result variables, since no temps used.
  858.  *    It is the original query.
  859.  * --------------
  860.  */
  861.             stdPlan = planner(parseTree);
  862.                         loopPlans = lispCons(PlanToList(stdPlan),LispNil);
  863.             checkpoints = lispCons(lispInteger(1),LispNil);
  864.             return (Plan) make_recursive(recursiveMethod,
  865.                     preppedCommandType,
  866.                     LispNil,
  867.                     loopPlans,
  868.                     LispNil,
  869.                     checkpoints,
  870.                     lispString(preppedResultRelationName));
  871.             break;
  872.             case REPLACE:
  873. Jprint("replace");
  874. /* JJJ *** DONE *** */
  875.                         stdPlan = planner(parseTree);
  876.                         loopPlans = lispCons(PlanToList(stdPlan),LispNil);
  877.                         checkpoints = lispCons(lispInteger(1),LispNil);
  878.                         return (Plan) make_recursive(recursiveMethod,
  879.                                         preppedCommandType,
  880.                                         LispNil,
  881.                                         loopPlans,
  882.                                         LispNil,
  883.                                         checkpoints,
  884.                     lispString(preppedResultRelationName));
  885.                         break;
  886.                 case RETRIEVE:
  887.             /* only 'retrieve* into' supported */
  888. Jprint("retrieve");
  889.             /* same as 'append', but place retrieve in init */
  890.  
  891.             newParseTree = RetrieveRemoveRecursion(parseTree);
  892.                         stdPlan = planner(newParseTree);
  893.  
  894.             /* convert to 'append' */
  895.             newCommandType = lispAtom("append");
  896. /* JJJ - first check for actual resultName */
  897. /* JJJ - need dummy id */
  898.             newResultRelation = lispString("pg_temp_result");
  899.             /* hope target list and qual can remain same */
  900.  
  901.             initPlans = lispCons(UtilityToList(utility),LispNil);
  902.  
  903.             /* same as APPEND */
  904.  
  905.                         loopPlans = lispCons(PlanToList(stdPlan),LispNil);
  906.                         checkpoints = lispCons(lispInteger(1),LispNil);
  907.  
  908.             /* same as APPEND */
  909.  
  910.                         return (Plan) make_recursive(recursiveMethod,
  911.                                         preppedCommandType,
  912.                                         initPlans,
  913.                                         loopPlans,
  914.                                         LispNil,
  915.                                         checkpoints,
  916.                     lispString(preppedResultRelationName));
  917.             break;
  918.           case DELETE:
  919. Jprint("Delete");
  920. /* JJJ *** DONE *** */
  921.                         stdPlan = planner(parseTree);
  922.                         loopPlans = lispCons(PlanToList(stdPlan),LispNil);
  923.                         checkpoints = lispCons(lispInteger(1),LispNil);
  924.                         return (Plan) make_recursive(recursiveMethod,
  925.                                         preppedCommandType,
  926.                                         LispNil,
  927.                                         loopPlans,
  928.                                         LispNil,
  929.                                         checkpoints,
  930.                     lispString(preppedResultRelationName));
  931.             break;
  932.                 case EXECUTE:
  933.             /* JRB -- Not a part of my master's project */
  934.             elog(WARN,
  935.                  "RecursiveQueryPlan: 'execute' not supported");
  936.             break;
  937.                 default:
  938.             elog(WARN,"RecursiveQueryPlan: command not supported");
  939.             break;
  940.         }
  941.         case RecursiveMethodSemiNaive:
  942. Jprint("Seminaive");
  943.            switch ((Command) CInteger(preppedCommandType)) {
  944.                case APPEND:
  945. Jprint("append");
  946.             /** build initPlans **/
  947.             /* make 'retrieve' */
  948.             newCommandType = lispAtom("retrieve");
  949.             newResultRelation = lispCons(lispAtom("into"),
  950.                         lispCons(lispString("pg_temp_A"),
  951.                         LispNil));
  952.             /* should also do a "not-in <result>" check */
  953.                   newRoot = lispCons(ParseTreeGetNumLevels(parseTree),
  954.                  lispCons(newCommandType,
  955.                   lispCons(newResultRelation,
  956.                            CDR(CDR(CDR(CAR(parseTree)))))));
  957.             newParseTree = lispCons(newRoot,CDR(parseTree));
  958.             newPlan = planner(newParseTree);
  959.                         initPlans = lispCons(PlanToList(newPlan),LispNil);
  960.  
  961.             /* make 'append' */
  962.             commandString = (String) palloc(strlen(
  963.                                            "append foo ( pg_temp_A.all )")
  964.                        + RELATION_NAME_LENGTH );
  965.             sprintf(commandString,"append %s ( pg_temp_A.all )",
  966.                 preppedResultRelationName);
  967.                         initPlans = append1(initPlans,
  968.                         StringToList(commandString));
  969.                            
  970.             /** build loopPlans **/
  971.  
  972. /* JJJ */        /* convert new plan to refer to tempB and tempA */
  973.             loopPlans = lispCons(PlanToList(newPlan),LispNil);
  974.  
  975.             /* make 'append' */
  976.             sprintf(commandString,"append %s ( pg_temp_B.all )",
  977.                 preppedResultRelationName);
  978.                         loopPlans = append1(loopPlans,
  979.                         StringToList(commandString));
  980.  
  981.             /* make 'destroy' */
  982.             commandString2 = (String) palloc(strlen(
  983.                                            "destroy pg_temp_A" + 1));
  984.             sprintf(commandString2,"destroy pg_temp_A");
  985.                         loopPlans = append1(loopPlans,
  986.                         StringToList(commandString2));
  987. /* JJJ redo */        checkpoints = lispCons(lispInteger(1),LispNil);
  988.  
  989.             /** build cleanupPlans **/
  990.             /* make 'destroy' */
  991.             sprintf(commandString2,"destroy pg_temp_B");
  992.                         cleanupPlans = lispCons(StringToList(commandString2),
  993.                          LispNil);
  994.  
  995.             return (Plan) make_recursive(recursiveMethod,
  996.                     preppedCommandType,
  997.                     initPlans,
  998.                     loopPlans,
  999.                     cleanupPlans,
  1000.                     checkpoints,
  1001.                     lispString(preppedResultRelationName));
  1002.             break;
  1003.             case REPLACE:
  1004. Jprint("replace");
  1005. /*** JJJ - needs work ***/
  1006. /* -------------------------
  1007.  *  Example :  replace* FOO( name = P.father )
  1008.  *         where FOO.name = P.name
  1009.  *
  1010.  *  Goes to :
  1011.  *    INIT -    retrieve into tempA( name = P.father, ... , x = FOO.x )
  1012.  *          where FOO.name = P.name
  1013.  *        delete FOO
  1014.  *          where FOO.name = P.name
  1015.  *        append FOO( tempA.all )
  1016.  *          
  1017.  *    LOOP -    retrieve into tempB( name = P.father, ... , x = tempA.x )
  1018.  *          where tempA.name = P.name
  1019.  *        delete tempA
  1020.  *          where tempA.name = P.name
  1021.  *        delete FOO
  1022.  *          where FOO.name = P.name
  1023.  *        append FOO( tempA.all )
  1024.  *        destroy tempB
  1025.  *
  1026.  *    CLEANUP -    destroy tempA
  1027.  * -------------------------
  1028.  */
  1029.  
  1030. /* --------------
  1031.  * INIT :
  1032.  *  "retrieve into tempA( name = P.father, ... , x = FOO.x )
  1033.  *          where FOO.name = P.name"
  1034.  *    requires no changes in result variables
  1035.  * --------------
  1036.  */
  1037.             scratchParseTree =
  1038.               (ParseTree) lispCopy(preppedParseTree);
  1039.  
  1040.             ParseTreeGetCommandType(scratchParseTree) =
  1041.               lispAtom("retrieve");
  1042.             ParseTreeGetResultRelation(scratchParseTree) =
  1043.               lispCons(lispAtom("into"),
  1044.                    lispCons(lispString(tempRelationFakeNameA),
  1045.                         LispNil));
  1046.             /* ---------
  1047.              * We should insure that new tuple is not-in target
  1048.              * ---------
  1049.              */
  1050.  
  1051.             scratchPlan = planner(scratchParseTree);
  1052. /* JJJ following should reserve new copy */
  1053.             initPlans = lispCons(PlanToList(scratchPlan),LispNil);
  1054.  
  1055. /* --------------
  1056.  *  "delete FOO
  1057.  *        where FOO.name = P.name"
  1058.  *    its result variable is same as replace*
  1059.  * --------------
  1060.  */
  1061.             ParseTreeGetCommandType(scratchParseTree) =
  1062.               lispAtom("delete");
  1063.             ParseTreeGetResultRelation(scratchParseTree) =
  1064.               preppedResultRelation;
  1065.  
  1066.             scratchPlan = planner(scratchParseTree);
  1067. /* JJJ following should reserve new copy */
  1068.             initPlans = append1(initPlans,PlanToList(scratchPlan));
  1069.             
  1070. /* --------------
  1071.  *  "append FOO ( tempA.all )"
  1072.  *    is written as a utility string
  1073.  * --------------
  1074.  */
  1075.             scratchString = (String) palloc(strlen(
  1076.                                            "append foo ( pg_temp_A.all )")
  1077.                        + RELATION_NAME_LENGTH );
  1078.             sprintf(scratchString,"append %s ( pg_temp_A.all )",
  1079.                 preppedResultRelationName);
  1080.  
  1081.                         initPlans = append1(initPlans,
  1082.                         StringToList(scratchString));
  1083.  
  1084. /* --------------
  1085.  * LOOP:
  1086.  *  "retrieve into tempB( name = P.father, ... , x = tempA.x )
  1087.  *          where tempA.name = P.name"
  1088.  *    requires changing only the extra result var's to tempA,
  1089.  *    and the minor change of result relation string to tempB
  1090.  * --------------
  1091.  */
  1092.             ParseTreeGetCommandType(scratchParseTree) = 
  1093.               lispAtom("retrieve");
  1094.             ParseTreeGetResultRelation(scratchParseTree) =
  1095.               lispCons(lispAtom("into"),
  1096.                    lispCons(lispString(tempRelationFakeNameB),
  1097.                         LispNil));
  1098.             /* ---------
  1099.              * We should insure that new tuple is not-in target
  1100.              * ---------
  1101.              */
  1102.  
  1103.             ClauseInstallTemps(preppedQualification,
  1104.                        preppedResultRelation,
  1105.                        NULL,
  1106.                        tempRelationFakeNameA,
  1107.                        scratchRangeTable);
  1108.  
  1109.             TargetListInstallTemps(preppedTargetList,
  1110.                            preppedResultRelation,
  1111.                            NULL,
  1112.                            tempRelationFakeNameA,
  1113.                            scratchRangeTable);
  1114.                              
  1115.             scratchPlan = planner(scratchParseTree);
  1116. /* JJJ following should reserve new copy */
  1117.             loopPlans = lispCons(PlanToList(scratchPlan),LispNil);
  1118.             
  1119. /* --------------
  1120.  *  "delete tempA
  1121.  *          where tempA.name = P.name"
  1122.  *    change all references to result to be tempA
  1123.  * --------------
  1124.  */
  1125.             ParseTreeGetCommandType(scratchParseTree) =
  1126.               lispAtom("delete");
  1127.             ParseTreeGetResultRelation(scratchParseTree) =
  1128.               RangeTableGetReplacementIndex(scratchRangeTable,
  1129.                                 tempRelationFakeNameA,
  1130.                             preppedResultRelation);
  1131.  
  1132.             ClauseInstallTemps(preppedQualification,
  1133.                        preppedResultRelation,
  1134.                        NULL,
  1135.                        tempRelationFakeNameA,
  1136.                        scratchRangeTable);
  1137.  
  1138.             TargetListInstallTemps(preppedTargetList,
  1139.                            preppedResultRelation,
  1140.                            NULL,
  1141.                            tempRelationFakeNameA,
  1142.                            scratchRangeTable);
  1143.                              
  1144.             scratchPlan = planner(scratchParseTree);
  1145.             loopPlans = append1(loopPlans,PlanToList(scratchPlan));
  1146.  
  1147. /* --------------
  1148.  *  "delete FOO
  1149.  *        where FOO.name = P.name"
  1150.  *    its result variable is same as replace*
  1151.  * --------------
  1152.  */
  1153.             ParseTreeGetCommandType(scratchParseTree) =
  1154.               lispAtom("delete");
  1155.             ParseTreeGetResultRelation(scratchParseTree) =
  1156.               preppedResultRelation;
  1157.  
  1158.             scratchPlan = planner(scratchParseTree);
  1159. /* JJJ following should reserve new copy */
  1160.             loopPlans = append1(loopPlans,PlanToList(scratchPlan));
  1161.             
  1162. /* --------------
  1163.  *  "append FOO ( tempA.all )"
  1164.  *    is written as a utility string
  1165.  * --------------
  1166.  */
  1167.             scratchString = (String) palloc(strlen(
  1168.                                            "append foo ( pg_temp_A.all )")
  1169.                        + RELATION_NAME_LENGTH );
  1170.             sprintf(scratchString,"append %s ( pg_temp_A.all )",
  1171.                 preppedResultRelationName);
  1172.  
  1173.                         loopPlans = append1(loopPlans,
  1174.                         StringToList(scratchString));
  1175.  
  1176. /* --------------
  1177.  *  "destroy tempB"
  1178.  *    is written as a utility string
  1179.  * --------------
  1180.  */
  1181.             loopPlans = append1(loopPlans,
  1182.                         StringToList("destroy pg_temp_B"));
  1183.  
  1184. /* JJJ *** Remember checkpoints */
  1185.             checkpoints = lispCons(lispInteger(1),LispNil);
  1186.  
  1187. /* --------------
  1188.  * CLEANUP:
  1189.  *  "destroy tempA"
  1190.  * --------------
  1191.  */
  1192.             cleanupPlans = lispCons(
  1193.                      StringToList("destroy pg_temp_A"));
  1194.  
  1195.                         return (Plan) make_recursive(recursiveMethod,
  1196.                                         preppedCommandType,
  1197.                                         initPlans,
  1198.                                         loopPlans,
  1199.                                         cleanupPlans,
  1200.                                         checkpoints,
  1201.                     lispString(preppedResultRelationName));
  1202.                         break;
  1203.                 case RETRIEVE:
  1204.             /* only 'retrieve* into' supported */
  1205. Jprint("retrieve");
  1206.             sprintf(utility,"create %s",preppedResultRelationName);
  1207.  
  1208.             newParseTree = RetrieveRemoveRecursion(parseTree);
  1209.  
  1210.  
  1211. /* just create, and do append */
  1212.  
  1213.                         stdPlan = planner(newParseTree);
  1214.             initPlans = lispCons(StringToList(utility),LispNil);
  1215.                         loopPlans = lispCons(PlanToList(stdPlan),LispNil);
  1216.                         checkpoints = lispCons(lispInteger(1),LispNil);
  1217.                         return (Plan) make_recursive(recursiveMethod,
  1218.                                         preppedCommandType,
  1219.                                         initPlans,
  1220.                                         loopPlans,
  1221.                                         LispNil,
  1222.                                         checkpoints,
  1223.                     lispString(preppedResultRelationName));
  1224.             break;
  1225.                 case DELETE:
  1226. Jprint("delete");
  1227. /* change to retrieve into */
  1228.  
  1229. /* simple deletes */
  1230.  
  1231.                         stdPlan = planner(parseTree);
  1232.                         loopPlans = lispCons(PlanToList(stdPlan),LispNil);
  1233.                         checkpoints = lispCons(lispInteger(1),LispNil);
  1234.                         return (Plan) make_recursive(recursiveMethod,
  1235.                                         preppedCommandType,
  1236.                                         LispNil,
  1237.                                         loopPlans,
  1238.                                         LispNil,
  1239.                                         checkpoints,
  1240.                     lispString(preppedResultRelationName));
  1241.             break;
  1242.                 case EXECUTE:
  1243.             /* JRB -- Not a part of my master's project */
  1244.             elog(WARN,
  1245.                  "RecursiveQueryPlan: 'execute' not supported");
  1246.             break;
  1247.                 default:
  1248.             elog(WARN,"RecursiveQueryPlan: command not supported");
  1249.             break;
  1250.             }
  1251.       }
  1252. }
  1253.