home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / planner / path / joinutils.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  12.0 KB  |  436 lines
  1.  
  2. /*     
  3.  *      FILE
  4.  *         joinutils
  5.  *     
  6.  *      DESCRIPTION
  7.  *         Utilities for matching and building join and path keys
  8.  *     
  9.  */
  10.  
  11. /*  RcsId("$Header: /private/postgres/src/planner/path/RCS/joinutils.c,v 1.20 1992/07/04 04:03:42 mao Exp $");   */
  12.  
  13. /*     
  14.  *      EXPORTS
  15.  *             match-pathkeys-joinkeys
  16.  *             match-paths-joinkeys
  17.  *             extract-path-keys
  18.  *             new-join-pathkeys
  19.  */
  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/joinutils.h"
  29. #include "planner/var.h"
  30. #include "planner/keys.h"
  31. #include "planner/tlist.h"
  32. #include "planner/joininfo.h"
  33.  
  34.  
  35. /*         ===============
  36.  *         KEY COMPARISONS
  37.  *         ===============
  38.  */
  39.  
  40. /*    
  41.  *        match-pathkeys-joinkeys
  42.  *    
  43.  *        Attempts to match the keys of a path against the keys of join clauses.
  44.  *        This is done by looking for a matching join key in 'joinkeys' for
  45.  *        every path key in the list 'pathkeys'. If there is a matching join key
  46.  *        (not necessarily unique) for every path key, then the list of 
  47.  *        corresponding join keys and join clauses are returned in the order in 
  48.  *        which the keys matched the path keys.
  49.  *    
  50.  *        'pathkeys' is a list of path keys:
  51.  *            ( ( (var) (var) ... ) ( (var) ... ) )
  52.  *        'joinkeys' is a list of join keys:
  53.  *            ( (outer inner) (outer inner) ... )
  54.  *        'joinclauses' is a list of clauses corresponding to the join keys in
  55.  *            'joinkeys'
  56.  *        'which-subkey' is a flag that selects the desired subkey of a join key
  57.  *            in 'joinkeys'
  58.  *    
  59.  *        Returns the join keys and corresponding join clauses in a list if all
  60.  *        of the path keys were matched:
  61.  *            ( 
  62.  *             ( (outerkey0 innerkey0) ... (outerkeyN innerkeyN) )
  63.  *             ( clause0 ... clauseN ) 
  64.  *            )
  65.  *        and nil otherwise.
  66.  *    
  67.  */
  68.  
  69. /*  .. match-unsorted-inner, match-unsorted-outer    */
  70.  
  71. LispValue
  72. match_pathkeys_joinkeys(pathkeys,joinkeys,joinclauses,which_subkey)
  73.      LispValue pathkeys,joinkeys,joinclauses;
  74.      int which_subkey ;
  75. {
  76.      LispValue matched_joinkeys = LispNil;
  77.      LispValue matched_joinclauses = LispNil;
  78.      LispValue pathkey = LispNil;
  79.      LispValue t_list = LispNil;
  80.      LispValue i = LispNil;
  81.      int matched_joinkey_index = -1;
  82.  
  83.      foreach(i, pathkeys) {
  84.      pathkey = CAR(i);
  85.      matched_joinkey_index = 
  86.        match_pathkey_joinkeys(pathkey,joinkeys,which_subkey);
  87.      
  88.      if(matched_joinkey_index != -1 ) {
  89.          LispValue xjoinkey = nth(matched_joinkey_index,joinkeys);
  90.          LispValue joinclause = nth(matched_joinkey_index,joinclauses);
  91.  
  92.          /* XXX was "push" function */
  93.          
  94.          matched_joinkeys = nappend1(matched_joinkeys,xjoinkey);
  95.          matched_joinkeys = nreverse(matched_joinkeys);
  96.  
  97.          matched_joinclauses = nappend1(matched_joinclauses,joinclause);
  98.          matched_joinclauses = nreverse(matched_joinclauses);
  99.          joinkeys = LispRemove(xjoinkey,joinkeys);
  100.          
  101.      } 
  102.      else {
  103.          return(LispNil);
  104.      } 
  105.         
  106.      }
  107.      if(!lispNullp(matched_joinkeys) &&
  108.     length(matched_joinkeys) == length(pathkeys)) {
  109.      t_list = lispCons(nreverse(matched_joinkeys),
  110.                 lispCons(nreverse(matched_joinclauses),
  111.                      LispNil));
  112.      } 
  113.      return(t_list);
  114.  
  115. }  /* function end  */
  116.  
  117. /*    
  118.  *        match-pathkey-joinkeys
  119.  *    
  120.  *        Returns the 0-based index into 'joinkeys' of the first joinkey whose
  121.  *        outer or inner subkey matches any subkey of 'pathkey'.
  122.  *    
  123.  */
  124.  
  125. /*  .. match-pathkeys-joinkeys     */
  126.  
  127. int
  128. match_pathkey_joinkeys(pathkey,joinkeys,which_subkey)
  129.      LispValue pathkey,joinkeys;
  130.      int which_subkey ;
  131. {
  132.     Var path_subkey;
  133.     int pos;
  134.     LispValue i = LispNil;
  135.     LispValue x = LispNil;
  136.     JoinKey jk;
  137.  
  138.     foreach(i,pathkey) {
  139.     path_subkey = (Var)CAR(i);
  140.     pos = 0;
  141.     foreach(x,joinkeys) {
  142.         jk = (JoinKey)CAR(x);
  143.         if(var_equal((LispValue)path_subkey, (LispValue)extract_subkey(jk, which_subkey)))
  144.         return(pos);
  145.         pos++;
  146.     }
  147.     }
  148.     return(-1);    /* no index found   */
  149.  
  150. }  /* function end   */
  151.  
  152. /*    
  153.  *        match-paths-joinkeys
  154.  *    
  155.  *        Attempts to find a path in 'paths' whose keys match a set of join
  156.  *        keys 'joinkeys'.  To match,
  157.  *        1. the path node ordering must equal 'ordering'.
  158.  *        2. each subkey of a given path must match(i.e., be(var_equal) to) the
  159.  *           appropriate subkey of the corresponding join key in 'joinkeys',
  160.  *           i.e., the Nth path key must match its subkeys against the subkey of
  161.  *           the Nth join key in 'joinkeys'.
  162.  *    
  163.  *        'joinkeys' is the list of key pairs to which the path keys must be 
  164.  *            matched
  165.  *        'ordering' is the ordering of the(outer) path to which 'joinkeys'
  166.  *            must correspond
  167.  *        'paths' is a list of(inner) paths which are to be matched against
  168.  *            each join key in 'joinkeys'
  169.  *        'which-subkey' is a flag that selects the desired subkey of a join key
  170.  *            in 'joinkeys'
  171.  *    
  172.  *        Returns the matching path node if one exists, nil otherwise.
  173.  *    
  174.  */
  175.  
  176. /*  function used by match_paths_joinkeys */
  177. bool
  178. every_func(joinkeys, pathkey, which_subkey)
  179.      LispValue joinkeys, pathkey;
  180.      int which_subkey;
  181. {
  182.      JoinKey xjoinkey;
  183.      Var temp;
  184.      LispValue tempkey = LispNil;
  185.      bool found = false;
  186.      LispValue i = LispNil;
  187.      LispValue j = LispNil;
  188.  
  189.      foreach(i,joinkeys) {
  190.      xjoinkey = (JoinKey)CAR(i);
  191.      found = false;
  192.      foreach(j,pathkey) {
  193.          temp = (Var)CAR(CAR(j));
  194.          if(temp == NULL) continue;
  195.          tempkey = extract_subkey(xjoinkey,which_subkey);
  196.          if(var_equal((LispValue)tempkey,(LispValue)temp)) {
  197.          found = true;
  198.          break;
  199.          }
  200.      }
  201.      if(found == false)
  202.        return(false);
  203.      }
  204.      return(found);
  205. }
  206.  
  207. /*  .. match-unsorted-outer     */
  208.  
  209. Path
  210. match_paths_joinkeys(joinkeys,ordering,paths,which_subkey)
  211.      LispValue joinkeys,ordering,paths;
  212.      int which_subkey ;
  213. {
  214.     Path path = (Path)NULL ;
  215.     bool key_match = false;
  216.     LispValue i = LispNil;
  217.  
  218.     foreach(i,paths) {
  219.     path = (Path)CAR(i);
  220.     key_match = every_func(joinkeys,
  221.                    get_keys(path),
  222.                    which_subkey);
  223.  
  224.     if(equal_path_path_ordering(ordering,
  225.                       get_p_ordering(path)) &&
  226.         length(joinkeys) == length(get_keys(path)) &&
  227.         key_match) {
  228.         return(path);
  229.     }
  230.     }
  231.     return((Path) LispNil);
  232. }  /* function end  */
  233.  
  234.  
  235.  
  236. /*    
  237.  *        extract-path-keys
  238.  *    
  239.  *        Builds a subkey list for a path by pulling one of the subkeys from
  240.  *        a list of join keys 'joinkeys' and then finding the var node in the
  241.  *        target list 'tlist' that corresponds to that subkey.
  242.  *    
  243.  *        'joinkeys' is a list of join key pairs
  244.  *        'tlist' is a relation target list
  245.  *        'which-subkey' is a flag that selects the desired subkey of a join key
  246.  *            in 'joinkeys'
  247.  *    
  248.  *        Returns a list of pathkeys: ((tlvar1)(tlvar2)...(tlvarN)).
  249.  *    
  250.  */
  251.  
  252. /*  .. hash-inner-and-outer, match-unsorted-inner, match-unsorted-outer
  253.  *  .. sort-inner-and-outer
  254.  */
  255. LispValue
  256. extract_path_keys(joinkeys,tlist,which_subkey)
  257.      LispValue joinkeys,tlist;
  258.      int which_subkey ;
  259. {
  260.     JoinKey xjoinkey = (JoinKey)NULL;
  261.     LispValue t_list = LispNil;
  262.     LispValue temp_node = LispNil;
  263.     LispValue i = LispNil;
  264.  
  265.     foreach(i,joinkeys) {
  266.     xjoinkey = (JoinKey)CAR(i);
  267.     temp_node =
  268.       lispCons((LispValue)matching_tlvar((Var)extract_subkey(xjoinkey,
  269.                             which_subkey),tlist),
  270.             LispNil);
  271.     t_list = nappend1(t_list,temp_node);
  272.     }
  273.     return(t_list);
  274. } /* function end  */
  275.  
  276. /*         =====================
  277.  *         NEW PATHKEY FORMATION
  278.  *         =====================
  279.  */
  280.  
  281. /*    
  282.  *        new-join-pathkeys
  283.  *    
  284.  *        Find the path keys for a join relation by finding all vars in the list
  285.  *        of join clauses 'joinclauses' such that:
  286.  *            (1) the var corresponding to the outer join relation is a
  287.  *                key on the outer path
  288.  *            (2) the var appears in the target list of the join relation
  289.  *        In other words, add to each outer path key the inner path keys that
  290.  *        are required for qualification.
  291.  *    
  292.  *        'outer-pathkeys' is the list of the outer path's path keys
  293.  *        'join-rel-tlist' is the target list of the join relation
  294.  *        'joinclauses' is the list of restricting join clauses
  295.  *    
  296.  *        Returns the list of new path keys. 
  297.  *    
  298.  */
  299.  
  300. /*  .. hash-inner-and-outer, match-unsorted-inner, match-unsorted-outer
  301.  *  .. sort-inner-and-outer
  302.  */
  303. LispValue
  304. new_join_pathkeys(outer_pathkeys,join_rel_tlist,joinclauses)
  305.      LispValue outer_pathkeys,join_rel_tlist,joinclauses ;
  306. {
  307.     LispValue outer_pathkey = LispNil;
  308.     LispValue t_list = LispNil;
  309.     LispValue x;
  310.     LispValue temp_node = LispNil;
  311.     LispValue i = LispNil;
  312.  
  313.     foreach(i,outer_pathkeys) {
  314.     outer_pathkey = CAR(i);
  315.     x = new_join_pathkey(outer_pathkey, LispNil, 
  316.                   join_rel_tlist,joinclauses);
  317.     if(!lispNullp(x)) {
  318.         temp_node = lispCons(x, LispNil);
  319.         t_list = nconc(t_list,temp_node);
  320.       }
  321.       }
  322.     return(t_list);
  323. }
  324.  
  325. /*    
  326.  *        new-join-pathkey
  327.  *    
  328.  *        Finds new vars that become subkeys due to qualification clauses that
  329.  *        contain any previously considered subkeys.  These new subkeys plus the
  330.  *        subkeys from 'subkeys' form a new pathkey for the join relation.
  331.  *    
  332.  *        Note that each returned subkey is the var node found in
  333.  *        'join-rel-tlist' rather than the joinclause var node.
  334.  *    
  335.  *        'subkeys' is a list of subkeys for which matching subkeys are to be
  336.  *            found
  337.  *        'considered-subkeys' is the current list of all subkeys corresponding
  338.  *            to a given pathkey
  339.  *    
  340.  *        Returns a new pathkey(list of subkeys).
  341.  *    
  342.  */
  343.  
  344. /*  .. new-join-pathkeys       */
  345.  
  346. LispValue
  347. new_join_pathkey(subkeys,considered_subkeys,join_rel_tlist,joinclauses)
  348.      LispValue subkeys,considered_subkeys,join_rel_tlist,joinclauses ;
  349. {
  350.     LispValue t_list = LispNil;
  351.     Var subkey;
  352.     LispValue i = LispNil;
  353.     LispValue matched_subkeys = LispNil;
  354.     Expr tlist_key = (Expr)NULL;
  355.     LispValue newly_considered_subkeys = LispNil;
  356.  
  357.     foreach(i,subkeys) {
  358.     subkey = (Var)CAR(i);
  359.     if(subkey == NULL)
  360.       break;    /* XXX something is wrong */
  361.     matched_subkeys = 
  362.       new_matching_subkeys(subkey,considered_subkeys,
  363.                 join_rel_tlist,joinclauses);
  364.     tlist_key = matching_tlvar(subkey,join_rel_tlist);
  365.     newly_considered_subkeys = LispNil;
  366.  
  367.     if( tlist_key ) {
  368.         if(!member((LispValue)tlist_key,matched_subkeys))
  369.           newly_considered_subkeys = lispCons((LispValue)tlist_key,
  370.                           matched_subkeys);
  371.     } 
  372.     else {
  373.         newly_considered_subkeys = matched_subkeys;
  374.     } 
  375.     
  376.     considered_subkeys = 
  377.       append(considered_subkeys,newly_considered_subkeys);
  378.     t_list = nconc(t_list,newly_considered_subkeys);
  379.     }
  380.     return(t_list);
  381.     
  382. }  /* function end  */
  383.  
  384. /*    
  385.  *        new-matching-subkeys
  386.  *    
  387.  *        Returns a list of new subkeys:
  388.  *        (1) which are not listed in 'considered-subkeys'
  389.  *        (2) for which the "other" variable in some clause in 'joinclauses' is
  390.  *            'subkey'
  391.  *        (3) which are mentioned in 'join-rel-tlist'
  392.  *    
  393.  *        Note that each returned subkey is the var node found in
  394.  *        'join-rel-tlist' rather than the joinclause var node.
  395.  *    
  396.  *        'subkey' is the var node for which we are trying to find matching
  397.  *            clauses
  398.  *    
  399.  *        Returns a list of new subkeys.
  400.  *    
  401.  */
  402.  
  403. /*  .. new-join-pathkey */
  404.  
  405. LispValue
  406. new_matching_subkeys(subkey,considered_subkeys,join_rel_tlist,joinclauses)
  407.      LispValue considered_subkeys,join_rel_tlist,joinclauses ;
  408.      Var subkey;
  409. {
  410.      LispValue joinclause = LispNil;
  411.      LispValue t_list = LispNil;
  412.      LispValue temp = LispNil;
  413.      LispValue i = LispNil;
  414.      Expr tlist_other_var = (Expr)NULL;
  415.  
  416.      foreach(i,joinclauses) {
  417.      joinclause = CAR(i);
  418.      tlist_other_var = 
  419.        matching_tlvar(other_join_clause_var(subkey,joinclause),
  420.                join_rel_tlist);
  421.  
  422.      if(tlist_other_var && 
  423.         !(member((LispValue)tlist_other_var,considered_subkeys))) {
  424.          /* XXX was "push" function  */
  425.          considered_subkeys = nappend1(considered_subkeys,
  426.                        (LispValue)tlist_other_var);
  427.          /* considered_subkeys = nreverse(considered_subkeys); 
  428.         XXX -- I am not sure of this. */
  429.  
  430.          temp = lispCons((LispValue)tlist_other_var,LispNil);
  431.          t_list = nconc(t_list,temp);
  432.      } 
  433.      }
  434.      return(t_list);
  435.  }  /* function end  */
  436.