home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / planner / path / joinpath.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-05  |  22.1 KB  |  792 lines
  1. /*     
  2.  *      FILE
  3.  *         joinpath
  4.  *     
  5.  *      DESCRIPTION
  6.  *         Routines to find all possible paths for processing a set of joins
  7.  *     
  8.  */
  9. /*  RcsId("$Header: /private/postgres/src/planner/path/RCS/joinpath.c,v 1.28 1992/08/19 01:12:02 mer Exp $");  */
  10.  
  11. /*     
  12.  *      EXPORTS
  13.  *             find-all-join-paths
  14.  */
  15.  
  16. /*
  17.  * This was a real bug of postgres (missing #include <math.h>) (kai)
  18.  */
  19. #include <math.h>
  20.  
  21. #include "nodes/pg_lisp.h"
  22. #include "nodes/relation.h"
  23. #include "nodes/relation.a.h"
  24. #include "nodes/plannodes.h"
  25. #include "nodes/plannodes.a.h"
  26.  
  27. #include "planner/internal.h"
  28. #include "planner/joinpath.h"
  29. #include "planner/relnode.h"
  30. #include "planner/mergeutils.h"
  31. #include "planner/hashutils.h"
  32. #include "planner/pathnode.h"
  33. #include "planner/joinutils.h"
  34. #include "planner/keys.h"
  35. #include "planner/costsize.h"
  36.  
  37. extern bool _enable_hashjoin_;
  38. extern bool _enable_mergesort_;
  39. extern int testFlag;
  40.  
  41.  
  42.  
  43. /*    
  44.  *        find-all-join-paths
  45.  *    
  46.  *        Creates all possible ways to process joins for each of the join
  47.  *        relations in the list 'joinrels.'  Each unique path will be included
  48.  *        in the join relation's 'pathlist' field.
  49.  *    
  50.  *        In postgres, n-way joins are handled left-only(permuting clauseless
  51.  *        joins doesn't usually win much).
  52.  *    
  53.  *    if BushyPlanFlag is true, bushy tree plans will be generated
  54.  *
  55.  *        'joinrels' is the list of relation entries to be joined
  56.  *        'previous-level-rels' is the list of(outer) relation entries from
  57.  *            the previous join processing level
  58.  *        'nest-level' is the current attribute nesting level
  59.  *    
  60.  *        Modifies the pathlist field of the appropriate rel node to contain
  61.  *        the unique join paths.
  62.  *    If bushy trees are considered, may modify the relid field of the
  63.  *    join rel nodes to flatten the lists.
  64.  *   
  65.  *      Returns nothing of interest. (?) 
  66.  *      It does a destructive modification.
  67.  */
  68.  
  69. /*  .. find-all-join-paths, find-join-paths    */
  70.  
  71. void
  72. find_all_join_paths(joinrels,previous_level_rels,nest_level)
  73.      LispValue joinrels,previous_level_rels;
  74.      int nest_level;
  75. {
  76.      LispValue mergeinfo_list = LispNil;
  77.      LispValue hashinfo_list = LispNil;
  78.      LispValue temp_list = LispNil;
  79.      LispValue path = LispNil;
  80.      LispValue form_relid();
  81.  
  82.      if( consp(joinrels) ) {
  83.       Rel joinrel = (Rel)CAR(joinrels);
  84.       List innerrelids;
  85.       List outerrelids;
  86.       LispValue innerrelid;
  87.       LispValue outerrelid;
  88.       Rel innerrel;
  89.       Rel outerrel;
  90.       Path bestinnerjoin;
  91.       LispValue pathlist = LispNil;
  92.  
  93.       innerrelids = CADR(get_relids(joinrel));
  94.       outerrelids = CAR(get_relids(joinrel));
  95.       innerrelid = form_relid(innerrelids);
  96.       outerrelid = form_relid(outerrelids);
  97.       innerrel = get_rel(innerrelid);
  98.       outerrel = get_rel(outerrelid);
  99.  
  100.       bestinnerjoin = best_innerjoin(get_innerjoin(innerrel),
  101.                      get_relids(outerrel));
  102.       if( _enable_mergesort_ ) {
  103.            mergeinfo_list = 
  104.          group_clauses_by_order(get_clauseinfo(joinrel),
  105.                      CAR(get_relids(innerrel)));
  106.       } 
  107.       
  108.       if( _enable_hashjoin_ ) {
  109.           hashinfo_list = 
  110.         group_clauses_by_hashop(get_clauseinfo(joinrel),
  111.                     CAR(get_relids(innerrel)));
  112.       } 
  113.       
  114.       /* need to flatten the relids list */
  115.       set_relids(joinrel, append(outerrelids,innerrelids));
  116.  
  117. /*
  118.  *    1. Consider mergesort paths where both relations must be explicitly 
  119.  *       sorted. 
  120.  */
  121.       if(!testFlag) {
  122.           pathlist = sort_inner_and_outer(joinrel,outerrel,
  123.                           innerrel,mergeinfo_list);
  124.         }
  125.       
  126. /*    2. Consider paths where the outer relation need not be explicitly  
  127.  *       sorted.  This may include either nestloops and mergesorts where 
  128.  *       the outer path is already ordered. 
  129.  */
  130.  
  131.       pathlist = add_pathlist(joinrel,pathlist,
  132.                   match_unsorted_outer(joinrel,
  133.                                outerrel,
  134.                                innerrel,
  135.                                get_pathlist(outerrel),
  136.                                (Path)get_cheapestpath 
  137.                                           (innerrel),
  138.                                bestinnerjoin,
  139.                                mergeinfo_list));
  140.  
  141. /*    3. Consider paths where the inner relation need not be explicitly  
  142.  *       sorted.  This may include nestloops and mergesorts  the actual
  143.  *       nestloop nodes were constructed in(match-unsorted-outer). 
  144.  *       Thus, this call is unnecessary for higher attribute nesting
  145.  *       levels since index scans can't be used(all scans are on 
  146.  *       temporaries).
  147.  */
  148.  
  149.       if( 1 == nest_level) {
  150.            pathlist = 
  151.          add_pathlist(joinrel,pathlist,
  152.                    match_unsorted_inner(joinrel,outerrel,
  153.                             innerrel,
  154.                             get_pathlist(innerrel),
  155.                             mergeinfo_list));
  156.       }
  157.  
  158. /*    4. Consider paths where both outer and inner relations must be 
  159.  *       hashed before being joined.
  160.  */
  161.  
  162.       pathlist = 
  163.         add_pathlist(joinrel,pathlist,
  164.               hash_inner_and_outer(joinrel,outerrel,
  165.                            innerrel,hashinfo_list));
  166.  
  167.       set_pathlist(joinrel,pathlist);
  168.  
  169. /*    'OuterJoinCost is only valid when calling(match-unsorted-inner) 
  170.  *    with the same arguments as the previous invokation of 
  171.  *    (match-unsorted-outer), so clear the field before going on. 
  172.  */
  173.       temp_list = get_pathlist(innerrel);
  174.       foreach(path, temp_list) {
  175.  
  176. /*
  177.  * XXX
  178.  * 
  179.  * This gross hack is to get around an apparent optimizer bug on Sparc
  180.  * (or maybe it is a bug of ours?) that causes really wierd behavior.
  181.  */
  182.  
  183.           if(IsA(path,JoinPath))
  184. #ifndef sparc
  185.                  set_outerjoincost((Path)CAR(path), (Cost) 0);
  186. #else
  187.                  /* DO NOT PROTOTYPE ME !!! */
  188.                  sparc_bug_set_outerjoincost((Path)CAR(path), 0);
  189. #endif
  190.  
  191.           /* do it iff it is a join path, which is not always
  192.          true, esp since the base level */
  193.       }
  194.       find_all_join_paths(CDR(joinrels),
  195.                    previous_level_rels,nest_level);
  196.      }
  197. }  /* function end */
  198.  
  199. /*    
  200.  *        best-innerjoin
  201.  *    
  202.  *        Find the cheapest index path that has already been identified by
  203.  *        (indexable_joinclauses) as being a possible inner path for the given
  204.  *        outer relation in a nestloop join.
  205.  *    
  206.  *        'join-paths' is a list of join nodes
  207.  *        'outer-relid' is the relid of the outer join relation
  208.  *    
  209.  *        Returns the pathnode of the selected path.
  210.  *    
  211.  */
  212.  
  213. /*  .. find-all-join-paths    */
  214.  
  215. Path
  216. best_innerjoin(join_paths,outer_relid)
  217.      LispValue join_paths,outer_relid ;
  218. {
  219.     Path cheapest = (Path)NULL;
  220.     LispValue join_path = LispNil;
  221.     
  222.     foreach(join_path, join_paths) {
  223.     if (member(CAR(get_joinid((Path)CAR(join_path))),outer_relid)
  224.        && ((null(cheapest) || path_is_cheaper((Path)CAR(join_path),cheapest)))) {
  225.         cheapest = (Path)CAR(join_path);
  226.     }
  227.     }
  228.     return(cheapest);
  229.  
  230. }  /*  function end   */
  231.  
  232. /*    
  233.  *        sort-inner-and-outer
  234.  *    
  235.  *        Create mergesort join paths by explicitly sorting both the outer and
  236.  *        inner join relations on each available merge ordering.
  237.  *    
  238.  *        'joinrel' is the join relation
  239.  *        'outerrel' is the outer join relation
  240.  *        'innerrel' is the inner join relation
  241.  *        'mergeinfo-list' is a list of nodes containing info on(mergesortable)
  242.  *            clauses for joining the relations
  243.  *        
  244.  *        Returns a list of mergesort paths.
  245.  *    
  246.  */
  247.  
  248. /*  .. find-all-join-paths     */
  249.  
  250. LispValue
  251. sort_inner_and_outer(joinrel,outerrel,innerrel,mergeinfo_list)
  252.      Rel joinrel,outerrel,innerrel;
  253.      List mergeinfo_list ;
  254. {
  255.      LispValue ms_list = LispNil;
  256.      MInfo xmergeinfo = (MInfo)NULL;
  257.      MergePath temp_node = (MergePath)NULL;
  258.      LispValue i = LispNil;
  259.      LispValue outerkeys = LispNil;
  260.      LispValue innerkeys = LispNil;
  261.      LispValue merge_pathkeys = LispNil;
  262.      
  263.      foreach(i,mergeinfo_list) {
  264.      xmergeinfo = (MInfo)CAR(i);
  265.  
  266.      outerkeys = 
  267.        extract_path_keys(joinmethod_keys((JoinMethod)xmergeinfo),
  268.                   get_targetlist(outerrel),
  269.                   OUTER);
  270.  
  271.      innerkeys = 
  272.        extract_path_keys(joinmethod_keys((JoinMethod)xmergeinfo),
  273.                   get_targetlist(innerrel),
  274.                   INNER);
  275.  
  276.      merge_pathkeys = 
  277.        new_join_pathkeys(outerkeys,get_targetlist(joinrel),
  278.                   joinmethod_clauses((JoinMethod)xmergeinfo));
  279.      
  280.      if(testFlag) {
  281.          LispValue x, y;
  282.          foreach(x, get_pathlist(outerrel)) {
  283.          foreach(y, get_pathlist(innerrel)) {
  284.          temp_node = create_mergesort_path(joinrel,
  285.                          get_size(outerrel),
  286.                          get_size(innerrel),
  287.                          get_width(outerrel),
  288.                          get_width(innerrel),
  289.                          (Path)CAR(x),
  290.                          (Path)CAR(y),
  291.                          merge_pathkeys,
  292.                          (List)get_m_ordering(xmergeinfo),
  293.                          joinmethod_clauses((JoinMethod)xmergeinfo),
  294.                          outerkeys,innerkeys);
  295.  
  296.           ms_list = nappend1(ms_list,(LispValue)temp_node);
  297.            }
  298.         }
  299.      }
  300.     else {
  301.      temp_node = create_mergesort_path(joinrel,
  302.                         get_size(outerrel),
  303.                         get_size(innerrel),
  304.                         get_width(outerrel),
  305.                         get_width(innerrel),
  306.                         (Path)get_cheapestpath(outerrel),
  307.                         (Path)get_cheapestpath(innerrel),
  308.                         merge_pathkeys,
  309.                         (List)get_m_ordering(xmergeinfo),
  310.                         joinmethod_clauses((JoinMethod)xmergeinfo),
  311.                         outerkeys,innerkeys);
  312.  
  313.       ms_list = nappend1(ms_list,(LispValue)temp_node);
  314.     }
  315.      }
  316.      return(ms_list);
  317.  
  318. }  /*  function end */
  319.  
  320. /*    
  321.  *        match-unsorted-outer
  322.  *    
  323.  *        Creates possible join paths for processing a single join relation
  324.  *        'joinrel' by employing either iterative substitution or
  325.  *        mergesorting on each of its possible outer paths(assuming that the
  326.  *        outer relation need not be explicitly sorted).
  327.  *    
  328.  *        1. The inner path is the cheapest available inner path.
  329.  *        2. Mergesort wherever possible.  Mergesorts are considered if there
  330.  *           are mergesortable join clauses between the outer and inner join
  331.  *           relations such that the outer path is keyed on the variables
  332.  *           appearing in the clauses.  The corresponding inner merge path is
  333.  *           either a path whose keys match those of the outer path(if such a
  334.  *           path is available) or an explicit sort on the appropriate inner
  335.  *           join keys, whichever is cheaper.
  336.  *    
  337.  *        'joinrel' is the join relation
  338.  *        'outerrel' is the outer join relation
  339.  *        'innerrel' is the inner join relation
  340.  *        'outerpath-list' is the list of possible outer paths
  341.  *        'cheapest-inner' is the cheapest inner path
  342.  *        'best-innerjoin' is the best inner index path(if any)
  343.  *        'mergeinfo-list' is a list of nodes containing info on mergesortable
  344.  *            clauses
  345.  *    
  346.  *        Returns a list of possible join path nodes.
  347.  *    
  348.  */
  349.  
  350. /*  .. find-all-join-paths     */
  351.  
  352. List
  353. match_unsorted_outer(joinrel,outerrel,innerrel,outerpath_list,
  354.               cheapest_inner,best_innerjoin,mergeinfo_list)
  355.      Rel joinrel,outerrel,innerrel;
  356.      List outerpath_list;
  357.      Path cheapest_inner,best_innerjoin;
  358.      List mergeinfo_list ;
  359. {
  360.     Path outerpath = (Path)NULL;
  361.     LispValue jp_list = LispNil;
  362.     LispValue temp_node = LispNil;
  363.     LispValue merge_pathkeys = LispNil;
  364.     Path nestinnerpath =(Path)NULL;
  365.     LispValue paths = LispNil;
  366.     LispValue i = LispNil;
  367.     LispValue outerpath_ordering = LispNil;
  368.  
  369.     foreach(i,outerpath_list) {
  370.     List clauses = LispNil;
  371.     LispValue keyquals = LispNil;
  372.         MInfo xmergeinfo = (MInfo)NULL;
  373.     outerpath = (Path)CAR(i);
  374.     outerpath_ordering = get_p_ordering(outerpath);
  375.     
  376.     if( outerpath_ordering ) {
  377.         xmergeinfo = 
  378.           match_order_mergeinfo((MergeOrder)outerpath_ordering,mergeinfo_list);
  379.     } 
  380.     
  381.     if(xmergeinfo ) {
  382.         clauses = get_clauses((JoinMethod)xmergeinfo);
  383.     } 
  384.  
  385.     if( clauses ) {
  386.         keyquals = 
  387.           match_pathkeys_joinkeys(get_keys(outerpath),
  388.                        joinmethod_keys((JoinMethod)xmergeinfo),
  389.                        joinmethod_clauses((JoinMethod)xmergeinfo),
  390.                        OUTER);
  391.         merge_pathkeys = 
  392.           new_join_pathkeys(get_keys(outerpath),
  393.                  get_targetlist(joinrel),clauses);
  394.     } 
  395.     else {
  396.         merge_pathkeys = get_keys(outerpath);
  397.     } 
  398.     
  399.     if(best_innerjoin &&
  400.         path_is_cheaper(best_innerjoin,cheapest_inner)) {
  401.         nestinnerpath = best_innerjoin;
  402.     } 
  403.     else {
  404.         nestinnerpath = cheapest_inner;
  405.     } 
  406.     
  407.     if(testFlag && best_innerjoin)
  408.         nestinnerpath = best_innerjoin;
  409.  
  410.     if (testFlag) {
  411.       LispValue x;
  412.       Path innerpath;
  413.       List outer_relid = get_relids(outerrel);
  414.       paths = LispNil;
  415.       if (length(get_relids(innerrel)) > 1) {
  416.           /* if join, then */
  417.           foreach (x, get_pathlist(innerrel)) {
  418.           innerpath = (Path)CAR(x);
  419.           paths = lispCons((LispValue)create_nestloop_path(joinrel, outerrel,
  420.                             outerpath, innerpath,
  421.                             merge_pathkeys),
  422.                    paths);
  423.            }
  424.         }
  425.       else {
  426.           /* if base relation, then */
  427.           foreach (x, get_innerjoin(innerrel)) {
  428.               innerpath = (Path)CAR(x);
  429.               if (member(CAR(get_joinid(innerpath)),outer_relid)) {
  430.                   paths = lispCons((LispValue)create_nestloop_path(joinrel, outerrel,
  431.                                     outerpath, innerpath,
  432.                                     merge_pathkeys),
  433.                            paths);
  434.             }
  435.             }
  436.         }
  437.       }
  438.     else {
  439.       paths = lispCons((LispValue)create_nestloop_path(joinrel,outerrel,
  440.                             outerpath,nestinnerpath,
  441.                             merge_pathkeys),
  442.                    LispNil);
  443.       }
  444.     
  445.     if( clauses && keyquals) {
  446.         bool path_is_cheaper_than_sort;
  447.         LispValue varkeys = LispNil;
  448.         
  449.         Path mergeinnerpath = 
  450.           match_paths_joinkeys(nth(0,keyquals),
  451.                     outerpath_ordering,
  452.                     get_pathlist(innerrel),
  453.                     INNER);
  454.         path_is_cheaper_than_sort = 
  455.           (bool) (mergeinnerpath && 
  456.               (get_path_cost(mergeinnerpath) < 
  457.                (get_path_cost(cheapest_inner) +
  458.             cost_sort(nth(0,keyquals)
  459.                    ,get_size(innerrel),
  460.                    get_width(innerrel),
  461.                    false))));
  462.         if(!path_is_cheaper_than_sort || testFlag)  {
  463.         varkeys = 
  464.           extract_path_keys(nth(0,keyquals),
  465.                      get_targetlist(innerrel),
  466.                      INNER);
  467.         } 
  468.         
  469.         
  470.         /*    Keep track of the cost of the outer path used with 
  471.          *    this ordered inner path for later processing in 
  472.          *    (match-unsorted-inner), since it isn't a sort and 
  473.          *    thus wouldn't otherwise be considered. 
  474.          */
  475.         
  476.         if(path_is_cheaper_than_sort || testFlag) {
  477.         set_outerjoincost(mergeinnerpath,
  478.                    get_path_cost(outerpath));
  479.         } 
  480.         else {
  481.         mergeinnerpath = cheapest_inner;
  482.         } 
  483.         
  484.         if(testFlag) {
  485.         LispValue x;
  486.         if(mergeinnerpath)
  487.             temp_node = lispCons((LispValue)create_mergesort_path(joinrel,
  488.                            get_size(outerrel),
  489.                            get_size(innerrel),
  490.                            get_width(outerrel),
  491.                            get_width(innerrel),
  492.                            outerpath,
  493.                            mergeinnerpath,
  494.                            merge_pathkeys,
  495.                            (List)get_m_ordering(xmergeinfo),
  496.                            nth(1,keyquals),
  497.                            LispNil,LispNil),
  498.                      paths);
  499.            /* to reduce path space: any path involving explicit sort 
  500.           is ditched
  501.         foreach(x, get_pathlist(innerrel)) { 
  502.             temp_node = lispCons(create_mergesort_path(joinrel,
  503.                              get_size(outerrel),
  504.                              get_size(innerrel),
  505.                              get_width(outerrel),
  506.                              get_width(innerrel),
  507.                              outerpath,
  508.                              CAR(x),
  509.                              merge_pathkeys,
  510.                              get_m_ordering(xmergeinfo),
  511.                              nth(1,keyquals),
  512.                               LispNil,varkeys),
  513.                      temp_node);
  514.            }
  515.              */
  516.            }
  517.         else {
  518.         temp_node = lispCons((LispValue)create_mergesort_path(joinrel,
  519.                                get_size(outerrel),
  520.                                get_size(innerrel),
  521.                                get_width(outerrel),
  522.                                get_width(innerrel),
  523.                                outerpath,
  524.                                mergeinnerpath,
  525.                                merge_pathkeys,
  526.                              (List)get_m_ordering(xmergeinfo),
  527.                                nth(1,keyquals),
  528.                                LispNil,varkeys),
  529.                  paths);
  530.           }
  531.         
  532.     } 
  533.     else {
  534.         temp_node = paths;
  535.     } 
  536.     jp_list = nconc(jp_list,temp_node);
  537.     }
  538.     return(jp_list);
  539.  
  540. }  /* function end  */
  541.  
  542. /*    
  543.  *        match-unsorted-inner 
  544.  *    
  545.  *        Find the cheapest ordered join path for a given(ordered, unsorted)
  546.  *        inner join path.
  547.  *    
  548.  *        Scans through each path available on an inner join relation and tries
  549.  *        matching its ordering keys against those of mergejoin clauses.
  550.  *        If 1. an appropriately-ordered inner path and matching mergeclause are
  551.  *              found, and
  552.  *           2. sorting the cheapest outer path is cheaper than using an ordered
  553.  *              but unsorted outer path(as was considered in
  554.  *              (match-unsorted-outer)),
  555.  *        then this merge path is considered.
  556.  *    
  557.  *        'joinrel' is the join result relation
  558.  *        'outerrel' is the outer join relation
  559.  *        'innerrel' is the inner join relation
  560.  *        'innerpath-list' is the list of possible inner join paths
  561.  *        'mergeinfo-list' is a list of nodes containing info on mergesortable
  562.  *            clauses
  563.  *    
  564.  *        Returns a list of possible merge paths.
  565.  *    
  566.  */
  567.  
  568. /*  .. find-all-join-paths    */
  569.  
  570. LispValue
  571. match_unsorted_inner(joinrel,outerrel,innerrel,innerpath_list,mergeinfo_list)
  572.      Rel joinrel,outerrel,innerrel;
  573.      List innerpath_list,mergeinfo_list ;
  574. {
  575.      
  576.     Path innerpath = (Path)NULL;
  577.     LispValue mp_list = LispNil;
  578.     LispValue temp_node = LispNil;
  579.     LispValue innerpath_ordering = LispNil;
  580.     Cost temp1  = 0.0;
  581.     bool temp2 = false;
  582.     LispValue i = LispNil;
  583.  
  584.     
  585.     foreach(i,innerpath_list) {
  586.         MInfo xmergeinfo = (MInfo)NULL;
  587.         List clauses = LispNil;
  588.         LispValue keyquals = LispNil;
  589.     innerpath = (Path)CAR(i);
  590.     innerpath_ordering = get_p_ordering(innerpath);
  591.     if( innerpath_ordering ) {
  592.         xmergeinfo = 
  593.           match_order_mergeinfo((MergeOrder)innerpath_ordering,mergeinfo_list);
  594.     } 
  595.     
  596.     if( xmergeinfo ) {
  597.         clauses = get_clauses((JoinMethod)xmergeinfo);
  598.     } 
  599.     
  600.     if( clauses ) {
  601.         keyquals = 
  602.           match_pathkeys_joinkeys(get_keys(innerpath),
  603.                        joinmethod_keys((JoinMethod)xmergeinfo),
  604.                        joinmethod_clauses((JoinMethod)xmergeinfo),
  605.                        INNER);
  606.     } 
  607.     
  608.     /*    (match-unsorted-outer) if it is applicable. */
  609.     /*    'OuterJoinCost was set above in  */
  610.     if( clauses && keyquals) {
  611.         temp1 = get_path_cost((Path)get_cheapestpath(outerrel)) + 
  612.           cost_sort(nth(0,keyquals), get_size(outerrel),
  613.             get_width(outerrel), false);
  614.         
  615.         temp2 = (bool) (FLOAT_IS_ZERO(get_outerjoincost(innerpath))
  616.                 || (get_outerjoincost(innerpath) > temp1));
  617.     
  618.         if(temp2 || testFlag) {
  619.         
  620.         LispValue outerkeys = 
  621.           extract_path_keys(nth(0,keyquals),
  622.                     get_targetlist(outerrel),
  623.                     OUTER);
  624.         LispValue merge_pathkeys = 
  625.           new_join_pathkeys(outerkeys,get_targetlist(joinrel),clauses);
  626.         
  627.         if(testFlag) {
  628.             LispValue x;
  629.             /* to reduce path space, all paths involving explicit sort
  630.                is ditched.
  631.             foreach(x, get_pathlist(outerrel)) {
  632.             temp_node = lispCons(create_mergesort_path(joinrel,
  633.                            get_size(outerrel),
  634.                            get_size(innerrel),
  635.                            get_width(outerrel),
  636.                            get_width(innerrel),
  637.                            CAR(x),
  638.                            innerpath,merge_pathkeys,
  639.                                get_m_ordering(xmergeinfo),
  640.                            nth(1,keyquals),
  641.                            outerkeys,LispNil),
  642.                          LispNil);
  643.             
  644.             mp_list = nconc(mp_list,temp_node);
  645.               }
  646.              */
  647.            }
  648.         else {
  649.         temp_node = lispCons((LispValue)create_mergesort_path(joinrel,
  650.                                get_size(outerrel),
  651.                                get_size(innerrel),
  652.                                get_width(outerrel),
  653.                                get_width(innerrel),
  654.                                (Path)get_cheapestpath (outerrel),
  655.                                innerpath,merge_pathkeys,
  656.                              (List)get_m_ordering(xmergeinfo),
  657.                                nth(1,keyquals),
  658.                                outerkeys,LispNil),
  659.                      LispNil);
  660.         
  661.         mp_list = nconc(mp_list,temp_node);
  662.         }
  663.  
  664.         } /* if temp2 */
  665.     } /* if clauses */
  666.     }
  667.     return(mp_list);
  668.     
  669. }  /* function end  */
  670.     
  671. bool
  672. EnoughMemoryForHashjoin(hashrel)
  673. Rel hashrel;
  674. {
  675.     int ntuples;
  676.     int tupsize;
  677.     int pages;
  678.  
  679.     ntuples = get_size(hashrel);
  680.     if (ntuples == 0) ntuples = 1000;
  681.     tupsize = get_width(hashrel) + sizeof(HeapTupleData);
  682.     pages = page_size(ntuples, tupsize);
  683.     /*
  684.      * if amount of buffer space below hashjoin threshold,
  685.      * return false
  686.      */
  687.     if (ceil(sqrt((double)pages)) > NBuffers)
  688.        return false;
  689.     return true;
  690. }
  691.  
  692. /*    
  693.  *        hash-inner-and-outer        XXX HASH
  694.  *    
  695.  *        Create hashjoin join paths by explicitly hashing both the outer and
  696.  *        inner join relations on each available hash op.
  697.  *    
  698.  *        'joinrel' is the join relation
  699.  *        'outerrel' is the outer join relation
  700.  *        'innerrel' is the inner join relation
  701.  *        'hashinfo-list' is a list of nodes containing info on(hashjoinable)
  702.  *            clauses for joining the relations
  703.  *        
  704.  *        Returns a list of hashjoin paths.
  705.  *    
  706.  */
  707.  
  708. /*  .. find-all-join-paths      */
  709.  
  710. LispValue
  711. hash_inner_and_outer(joinrel,outerrel,innerrel,hashinfo_list)
  712.      Rel joinrel,outerrel,innerrel;
  713.      LispValue hashinfo_list ;
  714. {
  715.     /* XXX  was mapCAR  */
  716.     
  717.     HInfo xhashinfo = (HInfo)NULL;
  718.     LispValue hjoin_list = LispNil;
  719.     HashPath temp_node = (HashPath)NULL;
  720.     LispValue i = LispNil;
  721.     LispValue outerkeys = LispNil;
  722.     LispValue innerkeys = LispNil;
  723.     LispValue hash_pathkeys = LispNil;
  724.     
  725.     foreach(i,hashinfo_list) {
  726.     xhashinfo = (HInfo)CAR(i);
  727.     outerkeys = 
  728.       extract_path_keys(get_jmkeys((JoinMethod)xhashinfo),
  729.                  get_targetlist(outerrel),OUTER);
  730.     innerkeys = 
  731.       extract_path_keys(get_jmkeys((JoinMethod)xhashinfo),
  732.                  get_targetlist(innerrel),INNER);
  733.     hash_pathkeys = 
  734.       new_join_pathkeys(outerkeys,
  735.                 get_targetlist(joinrel),
  736.                 get_clauses((JoinMethod)xhashinfo));
  737.     
  738.     if(testFlag) {
  739.         LispValue x, y;
  740.         foreach(x, get_pathlist(outerrel)) {
  741.         foreach(y, get_pathlist(innerrel)) {
  742.             temp_node = create_hashjoin_path(joinrel,
  743.                              get_size(outerrel),
  744.                              get_size(innerrel),
  745.                              get_width(outerrel),
  746.                              get_width(innerrel),
  747.                              (Path)CAR(x),
  748.                              (Path)CAR(y),
  749.                              hash_pathkeys,
  750.                              get_hashop(xhashinfo),
  751.                              get_clauses((JoinMethod)xhashinfo),
  752.                              outerkeys,innerkeys);
  753.             hjoin_list = nappend1(hjoin_list,(LispValue)temp_node);
  754.           }
  755.         }
  756.         }
  757.     else if (EnoughMemoryForHashjoin(innerrel)) {
  758.     temp_node = create_hashjoin_path(joinrel,
  759.                      get_size(outerrel),
  760.                      get_size(innerrel),
  761.                      get_width(outerrel),
  762.                      get_width(innerrel),
  763.                      (Path)get_cheapestpath(outerrel),
  764.                      (Path)get_cheapestpath(innerrel),
  765.                      hash_pathkeys,
  766.                      get_hashop(xhashinfo),
  767.                      get_clauses((JoinMethod)xhashinfo),
  768.                      outerkeys,innerkeys);
  769.     hjoin_list = nappend1(hjoin_list,(LispValue)temp_node);
  770.     }
  771.     }
  772.     return(hjoin_list);
  773.     
  774. }   /* function end  */
  775.  
  776. /*
  777.  *      form_relid
  778.  *
  779.  *    correctly form a relid: if it is a base relation relid is a
  780.  *    integer, if it is a join relation relid is a list of integers
  781.  */
  782.  
  783. LispValue
  784. form_relid(relids)
  785.         LispValue relids;
  786. {
  787.   if(length(relids) == 1)
  788.     return(CAR(relids));
  789.   else
  790.     return(relids);
  791. }
  792.