home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / planner / path / joinrels.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  14.9 KB  |  549 lines
  1.  
  2. /*     
  3.  *      FILE
  4.  *         joinrels
  5.  *     
  6.  *      DESCRIPTION
  7.  *         Routines to determine which relations should be joined
  8.  *     
  9.  */
  10.  
  11. /*  RcsId("$Header: /private/postgres/src/planner/path/RCS/joinrels.c,v 1.16 1992/07/23 15:33:07 joey Exp $");  */
  12.  
  13. /*     
  14.  *      EXPORTS
  15.  *             find-join-rels
  16.  */
  17.  
  18. #include "nodes/pg_lisp.h"
  19. #include "nodes/relation.h"
  20. #include "nodes/relation.a.h"
  21.  
  22. #include "planner/internal.h"
  23. #include "planner/joinrels.h"
  24. #include "planner/joininfo.h"
  25. #include "planner/relnode.h"
  26.  
  27. /*    
  28.  *        find-join-rels
  29.  *    
  30.  *        Find all possible joins for each of the outer join relations in
  31.  *        'outer-rels'.  A rel node is created for each possible join relation,
  32.  *        and the resulting list of nodes is returned.  If at all possible, only
  33.  *        those relations for which join clauses exist are considered.  If none
  34.  *        of these exist for a given relation, all remaining possibilities are
  35.  *        considered.
  36.  *    
  37.  *        'outer-rels' is the list of rel nodes
  38.  *    
  39.  *        Returns a list of rel nodes corresponding to the new join relations.
  40.  *    
  41.  */
  42.  
  43. /*  .. find-join-paths    */
  44.  
  45. LispValue
  46. find_join_rels(outer_rels)
  47.      LispValue outer_rels ;
  48. {
  49.     Rel outer_rel;
  50.     LispValue temp = LispNil;
  51.     LispValue t_list = LispNil;
  52.     LispValue i = LispNil;
  53.  
  54.     foreach(i,outer_rels) {
  55.     outer_rel = (Rel)CAR(i);
  56.     if(!(temp = find_clause_joins(outer_rel,get_joininfo(outer_rel))))
  57.       if (BushyPlanFlag)
  58.           temp = find_clauseless_joins(outer_rel,outer_rels);
  59.       else
  60.           temp = find_clauseless_joins(outer_rel,_base_relation_list_);
  61.     t_list = nconc(t_list,temp);
  62.     }
  63.     return(t_list);
  64.  
  65. }  /* function end  */
  66.  
  67. /*    
  68.  *        find-clause-joins
  69.  *    
  70.  *        Determines whether joins can be performed between an outer relation
  71.  *        'outer-rel' and those relations within 'outer-rel's joininfo nodes
  72.  *        (i.e., relations that participate in join clauses that 'outer-rel'
  73.  *        participates in).  This is possible if all but one of the relations
  74.  *        contained within the join clauses of the joininfo node are already
  75.  *        contained within 'outer-rel'.
  76.  *    
  77.  *        'outer-rel' is the relation entry for the outer relation
  78.  *        'joininfo-list' is a list of join clauses which 'outer-rel' 
  79.  *            participates in
  80.  *    
  81.  *        Returns a list of new join relations.
  82.  *    
  83.  */
  84.  
  85. /*  .. find-join-rels    */
  86.  
  87. LispValue
  88. find_clause_joins(outer_rel,joininfo_list)
  89.      Rel outer_rel;
  90.      List joininfo_list ;
  91. {
  92.      LispValue temp_node = LispNil;
  93.      LispValue t_list = LispNil;
  94.      LispValue i = LispNil;
  95.      
  96.      foreach(i,joininfo_list) {
  97.      JInfo joininfo = (JInfo)CAR(i);
  98.          if(!joininfo_inactive(joininfo)) {
  99.                LispValue other_rels = get_otherrels(joininfo);
  100.                if(!null(other_rels)) {
  101.                   if(length(other_rels) == 1)
  102.                      temp_node = lispCons((LispValue)init_join_rel(outer_rel,
  103.                                                        get_rel(CAR(other_rels)),
  104.                                                        joininfo),
  105.                                           LispNil);
  106.                   else
  107.                      temp_node = lispCons((LispValue)init_join_rel(outer_rel,
  108.                                                         get_rel(other_rels),
  109.                                                          joininfo),
  110.                                           LispNil);
  111.                 t_list = nconc(t_list,temp_node);
  112.  
  113.               }
  114.            }
  115.        }
  116.      return(t_list);
  117.  
  118. }  /* function end  */
  119.  
  120. /*    
  121.  *        find-clauseless-joins
  122.  *    
  123.  *        Given an outer relation 'outer-rel' and a list of inner relations
  124.  *        'inner-rels', create a join relation between 'outer-rel' and each
  125.  *        member of 'inner-rels' that isn't already included in 'outer-rel'.
  126.  *    
  127.  *        Returns a list of new join relations.
  128.  *    
  129.  */
  130.  
  131. /*  .. find-join-rels    */
  132.  
  133. LispValue
  134. find_clauseless_joins(outer_rel,inner_rels)
  135.      Rel outer_rel;
  136.      List inner_rels ;
  137. {
  138.      /*  XXX was mapcan   */
  139.      Rel inner_rel;
  140.      LispValue t_list = LispNil;
  141.      LispValue temp_node = LispNil;
  142.      LispValue i = LispNil;
  143.  
  144.      foreach(i,inner_rels) {
  145.      inner_rel = (Rel)CAR(i);
  146.          if(nonoverlap_rels(inner_rel,outer_rel)) {
  147.          temp_node = lispCons((LispValue)init_join_rel(outer_rel, 
  148.                                inner_rel,
  149.                                (JInfo)NULL),
  150.                    LispNil);
  151.          t_list = nconc(t_list,temp_node);
  152.      } 
  153.      }
  154.      return(t_list);
  155.  
  156. }  /*  function end   */
  157.  
  158. /*    
  159.  *        init-join-rel
  160.  *    
  161.  *        Creates and initializes a new join relation.
  162.  *    
  163.  *        'outer-rel' and 'inner-rel' are relation nodes for the relations to be
  164.  *            joined
  165.  *        'joininfo' is the joininfo node(join clause) containing both
  166.  *            'outer-rel' and 'inner-rel', if any exists
  167.  *    
  168.  *        Returns the new join relation node.
  169.  *    
  170.  */
  171.  
  172. /*  .. find-clause-joins, find-clauseless-joins   */
  173.  
  174. Rel
  175. init_join_rel(outer_rel,inner_rel,joininfo)
  176.      Rel outer_rel,inner_rel;
  177.      JInfo joininfo ;
  178. {
  179.     Rel joinrel = RMakeRel();
  180.     LispValue joinrel_joininfo_list = LispNil;
  181.     
  182.     /*    Create a new tlist by removing irrelevant elements from both */
  183.     /*    tlists of the outer and inner join relations and then merging */
  184.     /*    the results together. */
  185.  
  186.     LispValue new_outer_tlist = 
  187.       new_join_tlist(get_targetlist(outer_rel)   /*   XXX 1-based attnos */
  188.               ,get_relids(inner_rel),1);
  189.     LispValue new_inner_tlist = 
  190.       new_join_tlist(get_targetlist  (inner_rel)    /*   XXX 1-based attnos */
  191.               ,get_relids(outer_rel),
  192.               length(new_outer_tlist) + 1);
  193.      
  194.      
  195.     set_relids(joinrel, LispNil);
  196.     set_indexed(joinrel,false);
  197.     set_pages(joinrel, 0);
  198.     set_tuples(joinrel,0);
  199.     set_width(joinrel,0);
  200.     set_targetlist(joinrel,LispNil);
  201.     set_pathlist(joinrel,LispNil);
  202.     set_unorderedpath(joinrel,(PathPtr)NULL);
  203.     set_cheapestpath(joinrel,(PathPtr)NULL);
  204.     set_classlist(joinrel,(List)NULL);
  205.     set_ordering(joinrel,LispNil);
  206.     set_clauseinfo(joinrel,LispNil);
  207.     set_joininfo(joinrel,LispNil);
  208.     set_innerjoin(joinrel,LispNil);
  209.     set_superrels(joinrel,LispNil);
  210.     
  211.     set_relids(joinrel,lispCons(get_relids(outer_rel),
  212.                 lispCons(get_relids(inner_rel),
  213.                       LispNil)));
  214.     new_outer_tlist = nconc(new_outer_tlist,new_inner_tlist);
  215.     set_targetlist(joinrel,new_outer_tlist);
  216.     
  217.     if( joininfo) {
  218.     set_clauseinfo(joinrel,get_jinfoclauseinfo(joininfo));
  219.     if (BushyPlanFlag) deactivate_joininfo(joininfo);
  220.     }
  221.     
  222.     
  223.     joinrel_joininfo_list = 
  224.       new_joininfo_list(append(get_joininfo(outer_rel),get_joininfo(inner_rel)),
  225.                         append(get_relids(outer_rel), get_relids(inner_rel)));
  226.  
  227.     set_joininfo(joinrel,joinrel_joininfo_list);
  228.  
  229.     return(joinrel);
  230.  
  231. }  /* function end  */
  232.  
  233. /*    
  234.  *        new-join-tlist
  235.  *    
  236.  *        Builds a join relations's target list by keeping those elements that 
  237.  *        will be in the final target list and any other elements that are still 
  238.  *        needed for future joins.  For a target list entry to still be needed 
  239.  *        for future joins, its 'joinlist' field must not be empty after removal 
  240.  *        of all relids in 'other-relids'.
  241.  *    
  242.  *        'tlist' is the target list of one of the join relations
  243.  *        'other-relids' is a list of relids contained within the other
  244.  *            join relation
  245.  *        'first-resdomno' is the resdom number to use for the first created
  246.  *            target list entry
  247.  *    
  248.  *        Returns the new target list.
  249.  *    
  250.  */
  251.  
  252. /*  .. init-join-rel    */
  253.  
  254. LispValue
  255. new_join_tlist(tlist,other_relids,first_resdomno)
  256.      LispValue tlist,other_relids;
  257.      int first_resdomno ;
  258. {
  259.     int resdomno = first_resdomno - 1;
  260.     LispValue xtl = LispNil;
  261.     LispValue temp_node = LispNil;
  262.     LispValue t_list = LispNil;
  263.     LispValue i = LispNil;
  264.     LispValue join_list = LispNil;
  265.     bool in_final_tlist =false;
  266.     LispValue future_join_list = LispNil;
  267.     
  268.  
  269.     foreach(i,tlist) {
  270.     xtl= CAR(i);
  271.     join_list = get_joinlist(xtl);
  272.     in_final_tlist = null(join_list);
  273.     if( join_list ) 
  274.       future_join_list = set_difference(join_list,other_relids);
  275.     else
  276.       future_join_list = LispNil;
  277.     if( in_final_tlist || future_join_list)  {
  278.         resdomno += 1;
  279.         temp_node = 
  280.           lispCons((LispValue)create_tl_element(get_expr(get_entry(xtl)),
  281.                        resdomno,
  282.                        future_join_list),
  283.             LispNil);
  284.         t_list = nconc(t_list,temp_node);
  285.     } 
  286.     }
  287.     return(t_list);
  288. }
  289.  
  290. /*    
  291.  *        new-joininfo-list
  292.  *    
  293.  *        Builds a join relation's joininfo list by checking for join clauses
  294.  *        which still need to used in future joins involving this relation.  A
  295.  *        join clause is still needed if there are still relations in the clause
  296.  *        not contained in the list of relations comprising this join relation.
  297.  *        New joininfo nodes are only created and added to
  298.  *        'current-joininfo-list' if a node for a particular join hasn't already
  299.  *        been created.
  300.  *    
  301.  *        'current-joininfo-list' contains a list of those joininfo nodes that 
  302.  *            have already been built 
  303.  *        'joininfo-list' is the list of join clauses involving this relation
  304.  *        'join-relids' is a list of relids corresponding to the relations 
  305.  *            currently being joined
  306.  *    
  307.  *        Returns a list of joininfo nodes, new and old.
  308.  *    
  309.  */
  310.  
  311. /*  .. init-join-rel    */
  312.  
  313. LispValue
  314. new_joininfo_list(joininfo_list,join_relids)
  315.      LispValue joininfo_list,join_relids ;
  316. {
  317.    LispValue current_joininfo_list = LispNil;
  318.    LispValue new_otherrels = LispNil;
  319.    JInfo other_joininfo = (JInfo)NULL;
  320.    LispValue xjoininfo = LispNil;
  321.  
  322.    foreach(xjoininfo, joininfo_list) {
  323.       JInfo joininfo = (JInfo)CAR(xjoininfo);
  324.       new_otherrels = get_otherrels(joininfo);
  325.       if (nonoverlap_sets(new_otherrels,join_relids)) {
  326.          other_joininfo = joininfo_member(new_otherrels,current_joininfo_list);
  327.          if(other_joininfo)
  328.      {
  329.             set_jinfoclauseinfo(other_joininfo, LispUnion((LispValue)get_jinfoclauseinfo(joininfo), (LispValue)get_jinfoclauseinfo(other_joininfo)));
  330.      }
  331.          else {
  332.             other_joininfo = MakeJInfo(get_otherrels(joininfo),
  333.                                         get_jinfoclauseinfo(joininfo),
  334.                                         get_mergesortable(joininfo),
  335.                                         get_hashjoinable(joininfo),
  336.                     false);
  337.             current_joininfo_list = push((LispValue)other_joininfo,
  338.                      current_joininfo_list);
  339.          }
  340.        }
  341.     }
  342.     return(current_joininfo_list);
  343. } /* function end  */
  344.  
  345. /*
  346.  *      add-new-joininfos
  347.  *
  348.  *      For each new join relation, create new joininfos that
  349.  *      use the join relation as inner relation, and add
  350.  *      the new joininfos to those rel nodes that still
  351.  *      have joins with the join relation.
  352.  *
  353.  *      'joinrels' is a list of join relations.
  354.  *
  355.  *      Modifies the joininfo field of appropriate rel nodes.
  356.  *
  357.  */
  358.  
  359. /*  .. find-join-paths
  360.  */
  361. LispValue
  362. add_new_joininfos(joinrels,outerrels)
  363. LispValue joinrels,outerrels ;
  364. {
  365.     LispValue xjoinrel = LispNil;
  366.     LispValue xrelid = LispNil;
  367.     LispValue xrel = LispNil;
  368.     LispValue xjoininfo = LispNil;
  369.  
  370.     foreach(xjoinrel, joinrels) {
  371.     Rel joinrel = (Rel)CAR(xjoinrel);
  372.         foreach(xrelid, get_relids(joinrel)) {
  373.         Relid relid = (Relid)CAR(xrelid);
  374.         Rel rel = get_rel(relid);
  375.         add_superrels(rel,joinrel);
  376.     }
  377.     }
  378.     foreach(xjoinrel, joinrels) {
  379.     Rel joinrel = (Rel)CAR(xjoinrel);
  380.     foreach(xjoininfo, get_joininfo(joinrel)) {
  381.         JInfo joininfo = (JInfo)CAR(xjoininfo);
  382.         LispValue other_rels = get_otherrels(joininfo);
  383.         LispValue clause_info = get_jinfoclauseinfo(joininfo);
  384.         bool mergesortable = get_mergesortable(joininfo);
  385.         bool hashjoinable = get_hashjoinable(joininfo);
  386.         foreach(xrelid, other_rels) {
  387.         Relid relid = (Relid)CAR(xrelid);
  388.         Rel rel = get_rel(relid);
  389.         List super_rels = get_superrels(rel);
  390.         LispValue xsuper_rel = LispNil;
  391.         JInfo new_joininfo = MakeJInfo(get_relids(joinrel),
  392.                             clause_info,
  393.                             mergesortable,
  394.                             hashjoinable,
  395.                             false);
  396.             set_joininfo(rel,nappend1(get_joininfo(rel), (LispValue)new_joininfo));
  397.         foreach(xsuper_rel, super_rels) {
  398.             Rel super_rel = (Rel)CAR(xsuper_rel);
  399.             if( nonoverlap_rels(super_rel,joinrel) ) {
  400.             LispValue new_relids = get_relids(super_rel);
  401.             JInfo other_joininfo = 
  402.                   joininfo_member(new_relids,
  403.                            get_joininfo(joinrel));
  404.             if( other_joininfo ) {
  405.                 set_jinfoclauseinfo(other_joininfo, LispUnion(clause_info, get_jinfoclauseinfo(other_joininfo)));
  406.             } else {
  407.                 JInfo new_joininfo = MakeJInfo(new_relids,
  408.                                 clause_info,
  409.                                 mergesortable,
  410.                                 hashjoinable,
  411.                                 false);
  412.                 set_joininfo(joinrel, nappend1 (get_joininfo(joinrel), (LispValue)new_joininfo));
  413.             }
  414.             }
  415.         }
  416.          }
  417.      }
  418.     }
  419.     foreach(xrel, outerrels)  {
  420.     Rel rel = (Rel)CAR(xrel);
  421.     set_superrels(rel,LispNil);
  422.     }
  423. }
  424.  
  425. /*
  426.  *      final-join-rels
  427.  *
  428.  *      Find the join relation that includes all the original
  429.  *      relations, i.e. the final join result.
  430.  *
  431.  *      'join-rel-list' is a list of join relations.
  432.  *
  433.  *      Returns the list of final join relations.
  434.  *
  435.  */
  436.  
  437. /*  .. find-join-paths
  438.  */
  439. LispValue
  440. final_join_rels(join_rel_list)
  441. LispValue join_rel_list ;
  442. {
  443.     LispValue xrel = LispNil;
  444.     LispValue temp = LispNil;
  445.     LispValue t_list = LispNil;
  446.  
  447. /*    find the relations that has no further joins, */
  448. /*    i.e., its joininfos all have otherrels nil. */
  449.     foreach(xrel,join_rel_list)  {
  450.     Rel rel = (Rel)CAR(xrel);
  451.     LispValue xjoininfo = LispNil;
  452.     bool final = true;
  453.     foreach (xjoininfo,get_joininfo(rel)) {
  454.         JInfo joininfo = (JInfo)CAR(xjoininfo);
  455.         if(get_otherrels(joininfo) != LispNil)  {
  456.            final = false;
  457.            break;
  458.         }
  459.     }
  460.     if(final)  {
  461.        temp = lispCons((LispValue)rel,LispNil);
  462.        t_list = nconc(t_list, temp);
  463.     }
  464.     }
  465.     return(t_list);
  466. }  /* function end */
  467.  
  468. /*
  469.  *      add_superrels
  470.  *
  471.  *      add rel to the temporary property list superrels.
  472.  *
  473.  *      'rel' a rel node
  474.  *      'super-rel' rel node of a join relation that includes rel
  475.  *
  476.  *      Modifies the superrels field of rel
  477.  *
  478.  */
  479.  
  480. /*  .. init-join-rel
  481.  */
  482. void
  483. add_superrels(rel,super_rel)
  484. Rel rel,super_rel ;
  485. {
  486.     set_superrels(rel, nappend1(get_superrels(rel), (LispValue)super_rel));
  487. }
  488.  
  489. /*
  490.  *      nonoverlap-rels
  491.  *
  492.  *      test if two join relations overlap, i.e., includes the same
  493.  *      relation.
  494.  *
  495.  *      'rel1' and 'rel2' are two join relations
  496.  *
  497.  *      Returns non-nil if rel1 and rel2 do not overlap.
  498.  *
  499.  */
  500.  
  501. /*  .. add-new-joininfos
  502.  */
  503. bool
  504. nonoverlap_rels(rel1,rel2)
  505. Rel rel1,rel2 ;
  506. {
  507.     return(nonoverlap_sets(get_relids(rel1),get_relids(rel2)));
  508. }
  509.  
  510. bool
  511. nonoverlap_sets(s1,s2)
  512. LispValue s1,s2 ;
  513. {
  514.     LispValue x = LispNil;
  515.  
  516.     foreach(x,s1)  {
  517.        LispValue e = CAR(x);
  518.        if(member(e,s2))
  519.       return(false);
  520.     }
  521.     return(true);
  522. }
  523.  
  524. /*
  525.  *    cleanup-joininfos
  526.  *
  527.  *      after a round of find-join-paths, clear the JoinInfos that
  528.  *      have already been considered.
  529.  *
  530.  *      'outer-rels' is a list of rel nodes
  531.  *
  532.  *      Modifies JoinInfo fields.
  533.  *
  534.  */
  535.  
  536. /* .. add-new-joininfos
  537. */
  538. void
  539. cleanup_joininfos(outer_rels)
  540. LispValue outer_rels;
  541. {
  542.     LispValue xrel = LispNil;
  543.  
  544.     foreach(xrel,outer_rels)  {
  545.     Rel rel = (Rel)CAR(xrel);
  546.     set_joininfo(rel,LispNil);
  547.     }
  548. }
  549.