home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / planner / plan / createplan.c next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  30.0 KB  |  1,168 lines
  1. /*     
  2.  *      FILE
  3.  *         createplan
  4.  *     
  5.  *      DESCRIPTION
  6.  *         Routines to create the desired plan for processing a query
  7.  *     
  8.  */
  9.  
  10. /* RcsId("$Header: /private/postgres/src/planner/plan/RCS/createplan.c,v 1.54 1992/07/23 15:13:34 joey Exp $"); */
  11.  
  12. /*     
  13.  *      EXPORTS
  14.  *             create_plan
  15.  */
  16.  
  17. #include "tmp/c.h"
  18.  
  19. #include "nodes/execnodes.h"
  20. #include "nodes/plannodes.h"
  21. #include "nodes/plannodes.a.h"
  22. #include "nodes/relation.h"
  23. #include "nodes/relation.a.h"
  24. #include "nodes/primnodes.h"
  25. #include "nodes/primnodes.a.h"
  26.  
  27. #include "utils/log.h"
  28. #include "utils/lsyscache.h"
  29.  
  30. #include "planner/internal.h"
  31. #include "planner/clause.h"
  32. #include "planner/clauseinfo.h"
  33. #include "planner/clauses.h"
  34. #include "planner/createplan.h"
  35. #include "planner/setrefs.h"
  36. #include "planner/tlist.h"
  37. #include "planner/planner.h"
  38. #include "planner/xfunc.h"
  39.  
  40. #include "lib/lisplist.h"
  41. #include "lib/lispsort.h"
  42.  
  43. #define TEMP_SORT    1
  44. #define TEMP_MATERIAL    2
  45. /* "Print out the total cost at each query processing operator"  */
  46.  
  47. /*        ================
  48.  *        GENERIC ROUTINES
  49.  *        ================
  50.  */
  51.  
  52. /*    
  53.  *        create_plan
  54.  *    
  55.  *        Creates the access plan for a query by tracing backwards through the
  56.  *        desired chain of pathnodes, starting at the node 'best-path'.  For
  57.  *        every pathnode found:
  58.  *        (1) Create a corresponding plan node containing appropriate id,
  59.  *            target list, and qualification information.
  60.  *        (2) Modify ALL clauses so that attributes are referenced using
  61.  *            relative values.
  62.  *        (3) Target lists are not modified, but will be in another routine.
  63.  *    
  64.  *        'best-path' is the best access path
  65.  *    
  66.  *        Returns the optimal(?) access plan.
  67.  *    
  68.  */
  69.  
  70. /*  .. create_join_node, subplanner    */
  71.  
  72. Plan
  73. create_plan(best_path)
  74.      Path best_path;
  75. {
  76.      List tlist;
  77.      Plan plan_node = (Plan)NULL;
  78.      Plan sorted_plan_node = (Plan)NULL;
  79.      Rel parent_rel;
  80.      Count size;
  81.      Count width;
  82.      Count pages;
  83.      Count tuples;
  84.  
  85.      parent_rel = get_parent(best_path);
  86.      tlist = get_actual_tlist(get_targetlist(parent_rel));
  87.      size = get_size(parent_rel);
  88.      width = get_width(parent_rel);
  89.      pages = get_pages(parent_rel);
  90.      tuples = get_tuples(parent_rel);
  91.  
  92.      switch(get_pathtype(best_path)) {
  93.     case T_IndexScan : 
  94.     case T_SeqScan :
  95.       plan_node = (Plan)create_scan_node(best_path,tlist);
  96.       break;
  97.     case T_HashJoin :
  98.     case T_MergeJoin : 
  99.     case T_NestLoop:
  100.       plan_node = (Plan)create_join_node((JoinPath)best_path, tlist);
  101.       break;
  102.     default: /* do nothing */
  103.       break;
  104.      } 
  105.  
  106.      set_plan_size(plan_node, size);
  107.      set_plan_width(plan_node, width);
  108.      if (pages == 0) pages = 1;
  109.      set_plan_tupperpage(plan_node, tuples/pages);
  110.      set_fragment(plan_node, 0);
  111.  
  112.      /* sort clauses by cost/(1-selectivity) -- JMH 2/26/92 */
  113.      if (XfuncMode != XFUNC_OFF)
  114.       {
  115.       set_qpqual((Plan) plan_node, 
  116.              lisp_qsort((LispValue) get_qpqual((Plan) plan_node), 
  117.                 xfunc_clause_compare));
  118.       if (XfuncMode != XFUNC_NOR)
  119.         /* sort the disjuncts within each clause by cost -- JMH 3/4/92 */
  120.         xfunc_disjunct_sort(plan_node->qpqual);
  121.       }
  122.  
  123.      /*    Attach a SORT node to the path if a sort path is specified. */
  124.  
  125. #if 0
  126.      /* this piece of code has been long dead -- Wei */
  127.      if (get_pathsortkey(best_path) &&
  128.     (_query_max_level_ == 1)) {
  129.       set_qptargetlist(plan_node,
  130.                 (List)fix_targetlist(origtlist,
  131.                        get_qptargetlist(plan_node)));
  132.       sorted_plan_node = (Plan)sort_level_result(plan_node,
  133.                     length(get_varkeys(
  134.                         get_pathsortkey(best_path))));
  135.      }
  136.      else 
  137. #endif
  138.        if(get_pathsortkey(best_path)) {
  139.         sorted_plan_node = (Plan)make_temp(tlist,
  140.                       get_varkeys(get_pathsortkey(best_path)),
  141.                       get_sortorder(get_pathsortkey(best_path)),
  142.                       plan_node,TEMP_SORT);
  143.  
  144.        } 
  145.  
  146.      if(sorted_plan_node) {
  147.       plan_node = sorted_plan_node;
  148.       
  149.      }
  150.  
  151.      return(plan_node);
  152.  
  153. } /* function end */
  154.  
  155. /*    
  156.  *        create_scan_node
  157.  *    
  158.  *        Create a scan path for the parent relation of 'best-path'.
  159.  *    
  160.  *        'tlist' is the targetlist for the base relation scanned by 'best-path'
  161.  *    
  162.  *        Returns the scan node.
  163.  *    
  164.  */
  165.  
  166. /*  .. create_plan    */
  167.  
  168. Scan
  169. create_scan_node(best_path,tlist)
  170.      Path best_path;
  171.      List tlist ;
  172. {
  173.      /*Extract the relevant clauses from the parent relation and replace the */
  174.      /* operator OIDs with the corresponding regproc ids. */
  175.  
  176.     /*
  177.     ** CHANGE: now that local predicate clauses are copied into paths 
  178.     ** in find_rel_paths() and then (possibly) pulled up in xfunc_trypullup(),
  179.     ** we get the relevant clauses from the path itself, not its parent
  180.     ** relation.   --- JMH, 6/15/92
  181.     */
  182.  
  183.      Scan node;
  184.  
  185. /*  Old version (pre 6/15/92)
  186. **   LispValue scan_clauses = fix_opids(get_actual_clauses
  187. **                    (get_clauseinfo 
  188. **                     (get_parent
  189. **                      (best_path))));
  190. */
  191.      /* New version (6/15/92) */
  192.      LispValue scan_clauses = fix_opids(get_actual_clauses
  193.                     (get_locclauseinfo(best_path)));
  194.  
  195.      switch(get_pathtype(best_path)) {
  196.  
  197.     case T_SeqScan : 
  198.       node = (Scan)create_seqscan_node(best_path,tlist,scan_clauses);
  199.       break;
  200.  
  201.     case T_IndexScan:
  202.       node = (Scan)create_indexscan_node((IndexPath)best_path,
  203.                          tlist,scan_clauses);
  204.       break;
  205.       
  206.       default :
  207.         elog(WARN,"create_scan_node: unknown node type",
  208.              get_pathtype(best_path));
  209.       break;
  210.      }
  211.      set_parallel((Plan)node, 1);
  212.      return node;
  213.  
  214. }  /* function end  */
  215.  
  216. /*    
  217.  *        create_join_node
  218.  *    
  219.  *        Create a join path for 'best-path' and(recursively) paths for its
  220.  *        inner and outer paths.
  221.  *    
  222.  *        'tlist' is the targetlist for the join relation corresponding to
  223.  *            'best-path'
  224.  *    
  225.  *        Returns the join node.
  226.  *    
  227.  */
  228.  
  229. /*  .. create_plan    */
  230.  
  231. Join
  232. create_join_node(best_path,tlist)
  233.      JoinPath best_path;
  234.      List tlist ;
  235. {
  236.      Plan     outer_node;
  237.      LispValue     outer_tlist;
  238.      Plan     inner_node;
  239.      List     inner_tlist;
  240.      LispValue     clauses;
  241.      Join     retval;
  242.  
  243.      outer_node = create_plan((Path)get_outerjoinpath(best_path));
  244.      outer_tlist  = get_qptargetlist(outer_node);
  245.  
  246.      inner_node = create_plan((Path)get_innerjoinpath(best_path));
  247.      inner_tlist = get_qptargetlist(inner_node);
  248.  
  249.      clauses = get_actual_clauses(get_pathclauseinfo(best_path));
  250.      
  251.      switch(get_pathtype((Path)best_path)) {
  252.      
  253.        case T_MergeJoin : 
  254.      retval = (Join)create_mergejoin_node((MergePath)best_path,
  255.                            tlist,clauses,
  256.                            outer_node,outer_tlist,
  257.                            inner_node,inner_tlist);
  258.      break;
  259.        case T_HashJoin : 
  260.      retval = (Join)create_hashjoin_node((HashPath)best_path,tlist,
  261.                           clauses,outer_node,outer_tlist,
  262.                           inner_node,inner_tlist);
  263.      break;
  264.        case T_NestLoop : 
  265.      retval = (Join)create_nestloop_node((JoinPath)best_path,tlist,
  266.                           clauses,outer_node,outer_tlist,
  267.                           inner_node,inner_tlist);
  268.      set_parallel(inner_node, 0);
  269.      break;
  270.        default: /* do nothing */
  271.       elog(WARN,"create_join_node: unknown node type",
  272.         get_pathtype((Path)best_path));
  273.      } 
  274.  
  275.      /*
  276.      ** Expensive function pullups may have pulled local predicates
  277.      ** into this path node.  Put them in the qpqual of the plan node.
  278.      **        -- JMH, 6/15/92
  279.      */
  280.      if (get_locclauseinfo(best_path) != LispNil)
  281.        set_qpqual((Plan)retval,
  282.           nconc(get_qpqual((Plan) retval), 
  283.             fix_opids(get_actual_clauses
  284.                   (get_locclauseinfo(best_path)))));
  285.  
  286.      set_parallel((Plan)retval, 1);
  287.      return(retval);
  288.  
  289. }  /* function end  */
  290.  
  291. /*        ==========================
  292.  *        BASE-RELATION SCAN METHODS
  293.  *        ==========================
  294.  */
  295.  
  296. /*    
  297.  *        create_seqscan_node
  298.  *    
  299.  *        Returns a seqscan node for the base relation scanned by 'best-path'
  300.  *        with restriction clauses 'scan-clauses' and targetlist 'tlist'.
  301.  *    
  302.  */
  303.  
  304. /*  .. create_scan_node    */
  305.  
  306. SeqScan
  307. create_seqscan_node(best_path,tlist,scan_clauses)
  308.      Path best_path;
  309.      List tlist;
  310.      LispValue scan_clauses ;
  311. {
  312.     SeqScan scan_node = (SeqScan)NULL;
  313.     Index scan_relid = -1;
  314.     LispValue temp;
  315.  
  316.     temp = get_relids(get_parent(best_path));
  317.     if(null(temp))
  318.       elog(WARN,"scanrelid is empty");
  319.     else
  320.       scan_relid = (Index)CInteger(CAR(temp));
  321.     scan_node = make_seqscan(tlist,
  322.                   scan_clauses,
  323.                   scan_relid,
  324.                   (Plan)NULL);
  325.     
  326.     set_cost((Plan)scan_node,get_path_cost(best_path));
  327.     
  328.     return(scan_node);
  329.  
  330. } /* function end  */
  331.  
  332. /*    
  333.  *        create_indexscan_node
  334.  *    
  335.  *        Returns a indexscan node for the base relation scanned by 'best-path'
  336.  *        with restriction clauses 'scan-clauses' and targetlist 'tlist'.
  337.  *    
  338.  */
  339.  
  340. /*  .. create_scan_node    */
  341.  
  342. IndexScan
  343. create_indexscan_node(best_path,tlist,scan_clauses)
  344.      IndexPath best_path;
  345.      List tlist;
  346.      List scan_clauses ;
  347. {
  348.     /* Extract the(first if conjunct, only if disjunct) clause from the */
  349.     /* clauseinfo list. */
  350.      Expr     index_clause = (Expr)NULL;
  351.      List     indxqual = LispNil;
  352.      List     qpqual = LispNil;
  353.      List     fixed_indxqual = LispNil;
  354.      IndexScan     scan_node = (IndexScan)NULL;
  355.  
  356.      /*    If an 'or' clause is to be used with this index, the indxqual */
  357.      /*    field will contain a list of the 'or' clause arguments, e.g., the */
  358.      /*    clause(OR a b c) will generate: ((a) (b) (c)).  Otherwise, the */
  359.      /*   indxqual will simply contain one conjunctive qualification: ((a)). */
  360.     
  361.      if(!null(get_indexqual(best_path)))
  362.        /* added call to fix_opids, JMH 6/23/92 */
  363.        index_clause = (Expr)
  364.      CAR(fix_opids
  365.          (get_actual_clauses((LispValue)get_indexqual(best_path))));
  366.  
  367.  
  368.      if(or_clause_p((LispValue)index_clause)) {
  369.       LispValue temp = LispNil;
  370.     
  371.       foreach(temp,get_orclauseargs((LispValue)index_clause)) 
  372.         indxqual = nappend1(indxqual,lispCons(CAR(temp),LispNil));
  373.       } 
  374.      else {
  375.      indxqual = lispCons(get_actual_clauses(get_indexqual(best_path)),
  376.                  LispNil);
  377.      } 
  378.      /*    The qpqual field contains all restrictions except the indxqual. */
  379.  
  380.      if(or_clause((LispValue)index_clause))
  381.        qpqual = set_difference(scan_clauses,
  382.                 lispCons((LispValue)index_clause,LispNil));
  383.      else 
  384.        qpqual = set_difference(scan_clauses, CAR(indxqual));
  385.      
  386.      /*  XXX
  387.      fixed_indxqual = fix_indxqual_references(indxqual,best_path);
  388.      */
  389.      fixed_indxqual = indxqual;
  390.      scan_node = make_indexscan(tlist,
  391.                  qpqual,
  392.                  CInteger(CAR(get_relids 
  393.                           (get_parent((Path)best_path)))),
  394.                  get_indexid(best_path),
  395.                  fixed_indxqual);
  396.      
  397.      set_cost((Plan)scan_node,get_path_cost((Path)best_path));
  398.  
  399.      return(scan_node);
  400.  
  401. }  /* function end  */
  402.  
  403. /*  .. create_indexscan_node, fix-indxqual-references    */
  404.  
  405. LispValue
  406. fix_indxqual_references(clause,index_path)
  407.      LispValue clause;
  408.      Path index_path ;
  409. {
  410.     LispValue newclause;
  411.     if(IsA(clause,Var) && 
  412.        CInteger(CAR(get_relids(get_parent(index_path)))) ==
  413.        get_varno((Var)clause)) {
  414.     int pos = 0;
  415.     LispValue x = LispNil;
  416.     int varatt = get_varattno((Var)clause);
  417.     foreach(x,get_indexkeys(get_parent(index_path))) {
  418.         int att = CInteger(CAR(x));
  419.         if(varatt == att) {
  420.            break;
  421.         }
  422.         pos++;
  423.     }
  424.     newclause = (LispValue)CopyObject(clause);
  425.     set_varattno((Var)newclause, pos + 1);
  426.     return(newclause);
  427.     } 
  428.     else 
  429.       if(IsA(clause,Const))
  430.     return(clause);
  431.     else 
  432.       if(is_opclause(clause) && 
  433.       is_funcclause((LispValue)get_leftop(clause)) && 
  434.       get_funcisindex((Func)get_function((LispValue)get_leftop(clause)))) {
  435.  
  436.       /*      (set_opno(get_op clause) 
  437.        *   (get_funcisindex(get_function(get_leftop clause))))
  438.        *      (make_opclause(replace_opid(get_op clause))
  439.        */
  440.       return(make_opclause((Oper)get_op(clause),
  441.                    MakeVar((Index)CInteger(CAR(get_relids
  442.                        (get_parent(index_path)))),
  443.                        1, /* func indices have one key */
  444.                        get_functype((Func)get_function(clause)),
  445.                        LispNil, (Pointer)NULL),
  446.                    get_rightop(clause)));
  447.  
  448.       } 
  449.       else {
  450.       LispValue type = clause_type(clause);
  451.       LispValue new_subclauses = LispNil; 
  452.       LispValue subclause = LispNil;
  453.       LispValue i = LispNil;
  454.  
  455.       foreach(i,clause_subclauses(type,clause)) {
  456.           subclause = CAR(i);
  457.           if(subclause)
  458.         new_subclauses = nappend1(new_subclauses,
  459.                       fix_indxqual_references(subclause,
  460.                                   index_path));
  461.  
  462.  
  463.       }
  464.  
  465.       /* XXX new_subclauses should be a list of the form:
  466.        * ( (var var) (var const) ...) ?
  467.        */
  468.       
  469.       if( consp(new_subclauses) ) {
  470.           /* XXX was apply function  */
  471.           LispValue i = LispNil;
  472.           LispValue newclause = LispNil;
  473.           LispValue newclauses = LispNil;
  474.  
  475.           newclause = make_clause(type,new_subclauses);
  476.           return(newclause);
  477.  
  478.       } 
  479.       else {
  480.           return(clause);
  481.       } 
  482.       }
  483. }  /* function end  */
  484.  
  485.  
  486. /*        ============
  487.  *        JOIN METHODS
  488.  *        ============
  489.  */
  490.  
  491. /*    
  492.  *        create_nestloop_node
  493.  *    
  494.  *        Returns a new nestloop node.
  495.  *    
  496.  */
  497.  
  498. /*  .. create_join_node     */
  499.  
  500. NestLoop
  501. create_nestloop_node(best_path,tlist,clauses,
  502.               outer_node,outer_tlist,inner_node,inner_tlist)
  503.      JoinPath best_path;
  504.      List tlist,clauses;
  505.      Plan outer_node;
  506.      List outer_tlist;
  507.      Plan inner_node;
  508.      List inner_tlist ;
  509. {
  510.     NestLoop join_node = (NestLoop)NULL;
  511.  
  512.     if( IsA(inner_node,IndexScan)) {
  513.  
  514.     /*  An index is being used to reduce the number of tuples scanned in 
  515.      *    the inner relation.
  516.      * There will never be more than one index used in the inner 
  517.      * scan path, so we need only consider the first set of 
  518.      *    qualifications in indxqual. 
  519.      */
  520.  
  521.     List inner_indxqual = CAR(get_indxqual((IndexScan)inner_node));
  522.     List inner_qual = (inner_indxqual == LispNil)? LispNil:CAR(inner_indxqual);
  523.  
  524.     /* If we have in fact found a join index qualification, remove these
  525.      * index clauses from the nestloop's join clauses and reset the 
  526.      * inner(index) scan's qualification so that the var nodes refer to
  527.      * the proper outer join relation attributes.
  528.      */
  529.  
  530.     if  (!(qual_clause_p(inner_qual))) {
  531.         LispValue new_inner_qual = LispNil;
  532.         
  533.         clauses = set_difference(clauses,inner_indxqual);
  534.         new_inner_qual = index_outerjoin_references(inner_indxqual,
  535.                              get_qptargetlist 
  536.                              (outer_node),
  537.                              get_scanrelid 
  538.                              ((Scan)inner_node));
  539.         set_indxqual((IndexScan)inner_node,lispCons(new_inner_qual,LispNil));
  540.       }
  541.       }
  542.     else if (IsA(inner_node,Join)) {
  543.     inner_node = (Plan)make_temp(inner_tlist, LispNil, LispNil, 
  544.                          inner_node, TEMP_MATERIAL);
  545.       }
  546.     join_node = make_nestloop(tlist,
  547.                    join_references(clauses,
  548.                         outer_tlist,
  549.                         inner_tlist),
  550.                    outer_node,
  551.                    inner_node);
  552.  
  553.     set_cost((Plan)join_node,get_path_cost((Path)best_path));
  554.  
  555.     return(join_node);
  556.  
  557. }  /* function end  */
  558.  
  559.  
  560. /*    
  561.  *        create_mergejoin_node
  562.  *    
  563.  *        Returns a new mergejoin node.
  564.  *    
  565.  */
  566.  
  567. /*  .. create_join_node     */
  568.  
  569.  
  570. MergeJoin
  571. create_mergejoin_node(best_path,tlist,clauses,
  572.                outer_node,outer_tlist,
  573.                inner_node,inner_tlist)
  574.      MergePath best_path;
  575.      List tlist,clauses;
  576.      Plan outer_node;
  577.      List outer_tlist;
  578.      Plan inner_node;
  579.      List inner_tlist ;
  580. {
  581.      /*    Separate the mergeclauses from the other join qualification 
  582.       *    clauses and set those clauses to contain references to lower 
  583.       *    attributes. 
  584.       */
  585.  
  586.      LispValue qpqual = 
  587.        join_references(set_difference(clauses,
  588.                     get_path_mergeclauses(best_path)),
  589.             outer_tlist,
  590.             inner_tlist);
  591.  
  592.      /*    Now set the references in the mergeclauses and rearrange them so 
  593.       *    that the outer variable is always on the left. 
  594.       */
  595.      
  596.      LispValue mergeclauses = 
  597.        switch_outer(join_references(get_path_mergeclauses(best_path),
  598.                       outer_tlist,
  599.                       inner_tlist));
  600.      RegProcedure opcode = 
  601.      get_opcode(get_join_operator((MergeOrder)get_p_ordering((Path)best_path)));
  602.      
  603.      LispValue outer_order =
  604.     lispCons((LispValue) get_left_operator( (MergeOrder)
  605.                     get_p_ordering( (Path) best_path)),
  606.          LispNil);
  607.      
  608.      LispValue inner_order = 
  609.        lispCons( (LispValue) get_right_operator( (MergeOrder)
  610.                     get_p_ordering( (Path) best_path)),
  611.         LispNil);
  612.      
  613.      MergeJoin join_node;
  614.      
  615.      /*    Create explicit sort paths for the outer and inner join paths if 
  616.       *    necessary.  The sort cost was already accounted for in the path. 
  617.       */
  618.      if( get_outersortkeys(best_path)) {
  619.      Temp sorted_outer_node = make_temp(outer_tlist,
  620.                          get_outersortkeys 
  621.                          (best_path),
  622.                          outer_order,
  623.                          outer_node,
  624.                          TEMP_SORT);
  625.      set_cost((Plan)sorted_outer_node,get_cost(outer_node));
  626.      outer_node = (Plan)sorted_outer_node;
  627.      }
  628.  
  629.      if( get_innersortkeys(best_path)) {
  630.       Temp sorted_inner_node = make_temp(inner_tlist,
  631.                            get_innersortkeys 
  632.                            (best_path),
  633.                            inner_order,
  634.                            inner_node,TEMP_SORT);
  635.       set_cost((Plan)sorted_inner_node,get_cost(inner_node));
  636.       inner_node = (Plan)sorted_inner_node;
  637.      }
  638.  
  639.      join_node = make_mergesort(tlist,
  640.                 qpqual,
  641.                 mergeclauses,
  642.                 opcode,
  643.                 inner_order,
  644.                 outer_order, 
  645.                 inner_node,
  646.                 outer_node);
  647.      set_cost((Plan)join_node,get_path_cost((Path)best_path));
  648.      return(join_node);
  649.  
  650. } /* function end  */
  651.  
  652. /*    
  653.  *        switch_outer
  654.  *    
  655.  *        Given a list of merge clauses, rearranges the elements within the
  656.  *        clauses so the outer join variable is on the left and the inner is on
  657.  *        the right.
  658.  *    
  659.  *      Returns the rearranged list ?
  660.  *        XXX Shouldn't the operator be commuted?!
  661.  *    
  662.  */
  663.  
  664. /*  .. create_hashjoin_node, create_mergejoin_node    */
  665.  
  666. LispValue
  667. switch_outer(clauses)
  668.      LispValue clauses ;
  669. {
  670.     LispValue t_list = LispNil;
  671.     LispValue clause = LispNil;
  672.     LispValue temp = LispNil;
  673.     LispValue i = LispNil;
  674.  
  675.     foreach(i,clauses) {
  676.     clause = CAR(i);
  677.     if(var_is_outer(get_rightop(clause))) {
  678.         temp = make_clause((LispValue)get_op(clause),
  679.                 lispCons((LispValue)get_rightop(clause),
  680.                      lispCons((LispValue)get_leftop(clause),
  681.                           LispNil)));
  682.         t_list = nappend1(t_list,temp);
  683.     } 
  684.     else 
  685.       t_list = nappend1(t_list,clause);
  686.     
  687.     } 
  688.     return(t_list);
  689. }  /* function end   */
  690.  
  691. /*    
  692.  *        create_hashjoin_node            XXX HASH
  693.  *    
  694.  *        Returns a new hashjoin node.
  695.  *    
  696.  *        XXX hash join ops are totally bogus -- how the hell do we choose
  697.  *            these??  at runtime?  what about a hash index?
  698.  *    
  699.  */
  700.  
  701. /*  .. create_join_node     */
  702.  
  703. HashJoin
  704. create_hashjoin_node(best_path,tlist,clauses,outer_node,outer_tlist,
  705.               inner_node,inner_tlist)
  706.      HashPath best_path;
  707.      List tlist,clauses;
  708.      Plan outer_node;
  709.      List outer_tlist;
  710.      Plan inner_node;
  711.      List inner_tlist ;
  712. {
  713.     LispValue qpqual = 
  714.       /*    Separate the hashclauses from the other join qualification clauses
  715.        *    and set those clauses to contain references to lower attributes. 
  716.        */
  717.       join_references(set_difference(clauses,
  718.                        get_path_hashclauses(best_path)),
  719.                outer_tlist,
  720.                inner_tlist);
  721.     LispValue hashclauses = 
  722.       /*    Now set the references in the hashclauses and rearrange them so 
  723.        *    that the outer variable is always on the left. 
  724.        */
  725.       switch_outer(join_references(get_path_hashclauses(best_path),
  726.                      outer_tlist,
  727.                      inner_tlist));
  728.     HashJoin join_node;
  729.     Hash hash_node;
  730.     Var innerhashkey;
  731.  
  732.     innerhashkey = get_rightop(CAR(hashclauses));
  733.  
  734.     hash_node = make_hash(inner_tlist, innerhashkey, inner_node);
  735.     join_node = make_hashjoin(tlist,
  736.                    qpqual,
  737.                    hashclauses,
  738.                    outer_node,
  739.                    (Plan)hash_node);
  740.     set_cost((Plan)join_node,get_path_cost((Path)best_path));
  741.     return(join_node);
  742.     
  743. } /* function end  */
  744.  
  745. /*        ===================
  746.  *        UTILITIES FOR TEMPS
  747.  *        ===================
  748.  */
  749.  
  750. /*    
  751.  *        make_temp
  752.  *    
  753.  *        Create plan nodes to sort or materialize relations into temporaries. The
  754.  *        result returned for a sort will look like (SEQSCAN(SORT(plan-node)))
  755.  *    or (SEQSCAN(MATERIAL(plan-node)))
  756.  *    
  757.  *        'tlist' is the target list of the scan to be sorted or hashed
  758.  *        'keys' is the list of keys which the sort or hash will be done on
  759.  *        'operators' is the operators with which the sort or hash is to be done
  760.  *            (a list of operator OIDs)
  761.  *        'plan-node' is the node which yields tuples for the sort
  762.  *        'temptype' indicates which operation(sort or hash) to perform
  763.  *    
  764.  */
  765.  
  766. /*  .. create_hashjoin_node, create_mergejoin_node, create_plan    */
  767.  
  768. Temp
  769. make_temp(tlist,keys,operators,plan_node,temptype)
  770.      List tlist;
  771.      List keys;
  772.      List operators;
  773.      Plan plan_node;
  774.      int temptype ;
  775. {
  776.      /*    Create a new target list for the temporary, with keys set. */
  777.     List temp_tlist = set_temp_tlist_operators(new_unsorted_tlist(tlist),
  778.                            keys,
  779.                            operators);
  780.      Temp retval;
  781.  
  782.      switch(temptype) {
  783.        case TEMP_SORT : 
  784.      retval = (Temp)make_seqscan(tlist,
  785.                      LispNil,
  786.                      _TEMP_RELATION_ID_,
  787.                      (Plan)make_sort(temp_tlist,
  788.                              _TEMP_RELATION_ID_,
  789.                              plan_node,
  790.                              length(keys)));
  791.      break;
  792.      
  793.        case TEMP_MATERIAL : 
  794.      retval = (Temp)make_seqscan(tlist,
  795.                      LispNil,
  796.                      _TEMP_RELATION_ID_,
  797.                      (Plan)make_material(temp_tlist,
  798.                                  _TEMP_RELATION_ID_,
  799.                                  plan_node,
  800.                                  length(keys)));
  801.      break;
  802.      
  803.        default: 
  804.      elog(WARN,"make_temp: unknown temp type",temptype);
  805.      
  806.      }
  807.      return(retval);
  808.  
  809. }  /* function end  */
  810.           
  811.  
  812. /*    
  813.  *        set-temp-tlist-operators
  814.  *    
  815.  *        Sets the key and keyop fields of resdom nodes in a target list.
  816.  *    
  817.  *        'tlist' is the target list
  818.  *        'pathkeys' is a list of N keys in the form((key1) (key2)...(keyn)),
  819.  *            corresponding to vars in the target list that are to
  820.  *            be sorted or hashed
  821.  *        'operators' is the corresponding list of N sort or hash operators
  822.  *        'keyno' is the first key number 
  823.  *    XXX - keyno ? doesn't exist - jeff
  824.  *    
  825.  *        Returns the modified target list.
  826.  *    
  827.  */
  828.  
  829. /*  .. make_temp    */
  830.  
  831. List
  832. set_temp_tlist_operators(tlist,pathkeys,operators)
  833.      List tlist;
  834.      List pathkeys;
  835.      List operators ;
  836. {
  837.      LispValue     keys = LispNil;
  838.      List     ops = operators;
  839.      int     keyno = 1;
  840.      Resdom     resdom = (Resdom)NULL ;
  841.      LispValue i = LispNil;
  842.  
  843.      foreach(i,pathkeys) {
  844.      keys = CAR(CAR(i));
  845.      resdom = tlist_member((Var)keys,
  846.                 tlist);
  847.      if( resdom) {
  848.  
  849.          /* Order the resdom keys and replace the operator OID for each 
  850.           *    key with the regproc OID. 
  851.           */
  852.          set_reskey(resdom,keyno);
  853.          set_reskeyop(resdom,(OperatorTupleForm)get_opcode((ObjectId)CAR(ops))); /* XXX */
  854.      }
  855.      keyno += 1;
  856.      /*
  857.      ops = CDR(ops);
  858.      */
  859.      }
  860.      return(tlist);
  861. } /* function end  */
  862.  
  863. SeqScan
  864. make_seqscan(qptlist,qpqual,scanrelid,lefttree)
  865.      List qptlist;
  866.      List qpqual;
  867.      Index scanrelid;
  868.      Plan lefttree;
  869. {
  870.     SeqScan node = RMakeSeqScan();
  871.     
  872.     if(!null(lefttree))
  873.       Assert(IsA(lefttree,Plan));
  874.  
  875.     set_cost((Plan)node , 0.0 );
  876.     set_fragment((Plan)node, 0 );
  877.     set_state((Plan)node, (EStatePtr)NULL);
  878.     set_qptargetlist((Plan)node, qptlist);
  879.     set_qpqual((Plan)node , qpqual);
  880.     set_lefttree((Plan)node, (PlanPtr)lefttree);
  881.     set_righttree((Plan)node , (PlanPtr) NULL);
  882.     set_scanrelid((Scan)node , scanrelid);
  883.     set_scanstate((Scan)node, (ScanState)NULL);
  884.  
  885.     return(node);
  886. }
  887.  
  888. IndexScan
  889. make_indexscan(qptlist, qpqual, scanrelid,indxid,indxqual)
  890.      List qptlist,qpqual;
  891.      Index scanrelid;
  892.      List indxid, indxqual;
  893.  
  894. {
  895.     IndexScan node = RMakeIndexScan();
  896.  
  897.     set_cost((Plan)node , 0.0 );
  898.     set_fragment((Plan)node, 0 );
  899.     set_state((Plan)node, (EStatePtr)NULL);
  900.     set_qptargetlist((Plan)node, qptlist);
  901.     set_qpqual((Plan)node , qpqual);
  902.     set_lefttree((Plan)node,(PlanPtr)NULL);
  903.     set_righttree((Plan)node,(PlanPtr)NULL);
  904.     set_scanrelid((Scan)node,scanrelid);
  905.     set_indxid(node,indxid);
  906.     set_indxqual(node,indxqual);
  907.     set_scanstate((Scan)node, (ScanState)NULL);
  908.  
  909.     return(node);
  910. }
  911.  
  912.  
  913. NestLoop
  914. make_nestloop(qptlist,qpqual,lefttree,righttree)
  915.      List qptlist;
  916.      List qpqual;
  917.      Plan lefttree;
  918.      Plan righttree;
  919. {
  920.     NestLoop node = RMakeNestLoop();
  921.  
  922.     set_cost((Plan)node , 0.0 );
  923.     set_fragment((Plan)node, 0 );
  924.     set_state((Plan)node, (EStatePtr)NULL);
  925.     set_qptargetlist((Plan)node, qptlist);
  926.     set_qpqual((Plan)node , qpqual);
  927.     set_lefttree((Plan)node, (PlanPtr)lefttree);
  928.     set_righttree((Plan)node , (PlanPtr)righttree);
  929.     set_nlstate((NestLoop)node, (NestLoopState)NULL);
  930.     set_ruleinfo((Join)node, (JoinRuleInfoPtr)NULL);
  931.  
  932.     return(node);
  933. }
  934.  
  935. HashJoin
  936. make_hashjoin(tlist,qpqual,hashclauses,lefttree,righttree)
  937.      LispValue tlist, qpqual,hashclauses;
  938.      Plan righttree,lefttree;
  939. {
  940.     HashJoin node = RMakeHashJoin();
  941.     
  942.     set_cost((Plan)node , 0.0 );
  943.     set_fragment((Plan)node, 0 );
  944.     set_state((Plan)node, (EStatePtr)NULL);
  945.     set_qpqual((Plan)node,qpqual);
  946.     set_qptargetlist((Plan)node,tlist);
  947.     set_lefttree((Plan)node,(PlanPtr)lefttree);
  948.     set_righttree((Plan)node,(PlanPtr)righttree);
  949.     set_ruleinfo((Join)node, (JoinRuleInfoPtr) NULL);
  950.     set_hashclauses(node,hashclauses);
  951.     set_hashjointable(node, NULL);
  952.     set_hashjointablekey(node, 0);
  953.     set_hashjointablesize(node, 0);
  954.     set_hashdone(node, false);
  955.  
  956.     return(node);
  957. }
  958.  
  959. Hash
  960. make_hash(tlist, hashkey, lefttree)
  961.      LispValue tlist;
  962.      Var hashkey;
  963.      Plan lefttree;
  964. {
  965.     Hash node = RMakeHash();
  966.  
  967.     set_cost((Plan)node , 0.0 );
  968.     set_fragment((Plan)node, 0 );
  969.     set_parallel((Plan)node, 1);
  970.     set_state((Plan)node, (EStatePtr)NULL);
  971.     set_qpqual((Plan)node,LispNil);
  972.     set_qptargetlist((Plan)node,tlist);
  973.     set_lefttree((Plan)node,(PlanPtr)lefttree);
  974.     set_righttree((Plan)node,(PlanPtr)NULL);
  975.     set_hashkey(node, hashkey);
  976.     set_hashtable(node, NULL);
  977.     set_hashtablekey(node, 0);
  978.     set_hashtablesize(node, 0);
  979.  
  980.     return(node);
  981. }
  982.  
  983. MergeJoin
  984. make_mergesort(tlist, qpqual, mergeclauses, opcode, rightorder, leftorder,
  985.            righttree, lefttree)
  986.      LispValue tlist, qpqual,mergeclauses;
  987.      ObjectId opcode;
  988.      LispValue rightorder, leftorder;
  989.      Plan righttree,lefttree;
  990. {
  991.     MergeJoin node = RMakeMergeJoin();
  992.     
  993.     set_cost((Plan)node , 0.0 );
  994.     set_fragment((Plan)node, 0 );
  995.     set_state((Plan)node, (EStatePtr)NULL);
  996.     set_qpqual((Plan)node,qpqual);
  997.     set_qptargetlist((Plan)node,tlist);
  998.     set_lefttree((Plan)node,(PlanPtr)lefttree);
  999.     set_righttree((Plan)node,(PlanPtr)righttree);
  1000.     set_ruleinfo((Join)node, (JoinRuleInfoPtr) NULL);
  1001.     set_mergeclauses(node,mergeclauses);
  1002.     set_mergesortop(node,opcode);
  1003.     set_mergerightorder(node, rightorder);
  1004.     set_mergeleftorder(node, leftorder);
  1005.  
  1006.     return(node);
  1007.  
  1008. }
  1009.  
  1010. Sort
  1011. make_sort(tlist,tempid,lefttree, keycount)
  1012.      LispValue tlist;
  1013.      Count keycount;
  1014.      Plan lefttree;
  1015.      ObjectId tempid;
  1016. {
  1017.     Sort node = RMakeSort();
  1018.  
  1019.     set_cost((Plan)node , 0.0 );
  1020.     set_fragment((Plan)node, 0 );
  1021.     set_parallel((Plan)node, 1);
  1022.     set_state((Plan)node, (EStatePtr)NULL);
  1023.     set_qpqual((Plan)node,LispNil);
  1024.     set_qptargetlist((Plan)node,tlist);
  1025.     set_lefttree((Plan)node,(PlanPtr)lefttree);
  1026.     set_righttree((Plan)node,(PlanPtr)NULL);
  1027.     set_tempid((Temp)node,tempid);
  1028.     set_keycount((Temp)node,keycount);
  1029.  
  1030.     return(node);
  1031. }
  1032.  
  1033. Material
  1034. make_material(tlist,tempid,lefttree, keycount)
  1035.      LispValue tlist;
  1036.      Count keycount;
  1037.      Plan lefttree;
  1038.      ObjectId tempid;
  1039. {
  1040.     Material node = RMakeMaterial(); 
  1041.  
  1042.     set_cost((Plan)node , 0.0 );
  1043.     set_fragment((Plan)node, 0 );
  1044.     set_parallel((Plan)node, 1);
  1045.     set_state((Plan)node, (EStatePtr)NULL);
  1046.     set_qpqual((Plan)node,LispNil);
  1047.     set_qptargetlist((Plan)node,tlist);
  1048.     set_lefttree((Plan)node,(PlanPtr)lefttree);
  1049.     set_righttree((Plan)node,(PlanPtr)NULL);
  1050.     set_tempid((Temp)node,tempid);
  1051.     set_keycount((Temp)node,keycount);
  1052.  
  1053.     return(node);
  1054. }
  1055.  
  1056. Agg
  1057. make_agg(arglist, aggidnum)
  1058.      List arglist;
  1059.      ObjectId aggidnum;
  1060. {
  1061.      /* arglist is(Resnode((interesting stuff), NULL)) */
  1062.      Agg node = RMakeAgg();
  1063.      Resdom resdom = (Resdom)CAR(arglist);
  1064.      String aggname = NULL; 
  1065.      LispValue query = LispNil;
  1066.      List varnode = LispNil;
  1067.      arglist = CADR(arglist);
  1068.      aggname = CString(CAR(arglist));
  1069.      arglist = CDR(arglist);
  1070.      query = CAR(arglist);
  1071.      arglist = CDR(arglist);
  1072.      varnode = CAR(arglist);
  1073.      set_cost((Plan)node, 0.0);
  1074.      set_fragment((Plan)node, 0);
  1075.      set_parallel((Plan)node, 1);
  1076.      set_state((Plan)node, (EStatePtr)NULL);
  1077.      set_qpqual((Plan)node, LispNil);
  1078.      set_qptargetlist((Plan)node, 
  1079.               lispCons(MakeList((LispValue)resdom, 
  1080.                     varnode,
  1081.                     -1),
  1082.                    LispNil));
  1083.      set_lefttree((Plan)node, (PlanPtr)planner(query));
  1084.      set_righttree((Plan)node, (PlanPtr)NULL);
  1085.      set_tempid((Temp)node, aggidnum);
  1086.      set_aggname(node, aggname);
  1087.      return(node);
  1088. }
  1089.  
  1090. /*
  1091.  *  A unique node always has a SORT node in the lefttree.
  1092.  */
  1093.  
  1094. Unique
  1095. make_unique(tlist,lefttree)
  1096.      List tlist;
  1097.      Plan lefttree;
  1098. {
  1099.     Unique node = RMakeUnique();
  1100.  
  1101.     set_cost((Plan)node , 0.0 );
  1102.     set_fragment((Plan)node, 0 );
  1103.     set_parallel((Plan)node, 1);
  1104.     set_state((Plan)node, (EStatePtr)NULL);
  1105.     set_qpqual((Plan)node,LispNil);
  1106.     set_qptargetlist((Plan)node,tlist);
  1107.     set_lefttree((Plan)node,(PlanPtr)lefttree);
  1108.     set_righttree((Plan)node,(PlanPtr)NULL);
  1109.     set_tempid((Temp)node,-1);
  1110.     set_keycount((Temp)node,0);
  1111.  
  1112.     return(node);
  1113. }
  1114.  
  1115. List
  1116. generate_fjoin(tlist)
  1117.     List tlist;
  1118. {
  1119.     List tlistP;
  1120.     List newTlist = LispNil;
  1121.     List fjoinList = LispNil;
  1122.     int  nIters = 0;
  1123.  
  1124.     /*
  1125.      * Break the target list into elements with Iter nodes,
  1126.      * and those without them.
  1127.      */
  1128.     foreach(tlistP, tlist)
  1129.     {
  1130.     List tlistElem;
  1131.  
  1132.     tlistElem = CAR(tlistP);
  1133.     if ( IsA(CADR(tlistElem),Iter) )
  1134.     {
  1135.         nIters++;
  1136.         fjoinList = nappend1(fjoinList, tlistElem);
  1137.     }
  1138.     else
  1139.     {
  1140.         newTlist = nappend1(newTlist, tlistElem);
  1141.     }
  1142.     }
  1143.  
  1144.     /*
  1145.      * if we have an Iter node then we need to flatten.
  1146.      */
  1147.     if (nIters > 0)
  1148.     {
  1149.     LispValue inner;
  1150.     List      tempList;
  1151.     Fjoin     fjoinNode;
  1152.     DatumPtr  results = (DatumPtr)palloc(nIters*sizeof(Datum));
  1153.     BoolPtr   alwaysDone = (BoolPtr)palloc(nIters*sizeof(bool));
  1154.  
  1155.     inner = CAR(fjoinList);
  1156.     fjoinList = CDR(fjoinList);
  1157.     fjoinNode = (Fjoin)MakeFjoin(false,
  1158.                      nIters,
  1159.                      inner,
  1160.                      results,
  1161.                      alwaysDone);
  1162.     tempList = lispCons((LispValue)fjoinNode, LispNil);
  1163.     tempList = nconc(tempList, fjoinList);
  1164.     newTlist = nappend1(newTlist, tempList);
  1165.     }
  1166.     return newTlist;
  1167. }
  1168.