home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / planner / path / allpaths.c next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  11.7 KB  |  429 lines
  1. /*     
  2.  *      FILE
  3.  *         path
  4.  *     
  5.  *      DESCRIPTION
  6.  *         Routines to find possible search paths for processing a query
  7.  *     
  8.  */
  9. /* RcsId("$Header: /private/postgres/src/planner/path/RCS/allpaths.c,v 1.28 1992/07/23 15:15:17 joey Exp $"); */
  10.  
  11. /*     
  12.  *      EXPORTS
  13.  *             find-paths
  14.  */
  15.  
  16. #include <strings.h>
  17.  
  18. #include "nodes/pg_lisp.h"
  19. #include "nodes/relation.h"
  20. #include "nodes/relation.a.h"
  21. #include "nodes/primnodes.h"
  22. #include "nodes/primnodes.a.h"
  23.  
  24. #include "planner/allpaths.h"
  25. #include "planner/internal.h"
  26. #include "planner/indxpath.h"
  27. #include "planner/orindxpath.h"
  28. #include "planner/joinrels.h"
  29. #include "planner/prune.h"
  30. #include "planner/indexnode.h"
  31. #include "planner/pathnode.h"
  32. #include "planner/clauses.h"
  33. #include "planner/xfunc.h"
  34. #include "tcop/creatinh.h"
  35. #include "lib/copyfuncs.h"
  36.  
  37. /*    
  38.  *        find-paths
  39.  *    
  40.  *        Finds all possible access paths for executing a query, returning the
  41.  *        top level list of relation entries.  
  42.  *    
  43.  *        'rels' is the list of single relation entries appearing in the query
  44.  *        'nest-level' is the current attribute nesting level being processed
  45.  *        'sortkeys' contains info on sorting of the result
  46.  *    
  47.  */
  48.  
  49. /*  .. subplanner   */
  50.  
  51. LispValue
  52. find_paths(rels,nest_level,sortkeys)
  53.      LispValue rels,sortkeys ;
  54.      int nest_level;
  55. {
  56.     if( length(rels) > 0 && nest_level > 0 ) {
  57.     /* Set the number of join(not nesting) levels yet to be processed. */
  58.     
  59.     int levels_left = length(rels);
  60.  
  61.     /* Find the base relation paths. */
  62.     find_rel_paths(rels,nest_level,sortkeys);
  63.     
  64.     if( !sortkeys && (levels_left <= 1)) {
  65.         /* Unsorted single relation, no more processing is required. */
  66.         return(rels);   
  67.     } 
  68.     else {
  69.         /* 
  70.          * this means that joins or sorts are required.
  71.          * set selectivities of clauses that have not been set
  72.          * by an index.
  73.          */
  74.         set_rest_relselec(rels);
  75.         if(levels_left <= 1) {
  76.         return(rels); 
  77.           } 
  78.         else {
  79.         return(find_join_paths(rels,levels_left - 1,nest_level));
  80.           }
  81.       }
  82.       }
  83.     return(NULL);
  84. }  /* end find_paths */
  85.  
  86. /*    
  87.  *        find-rel-paths
  88.  *    
  89.  *        Finds all paths available for scanning each relation entry in 
  90.  *        'rels'.  Sequential scan and any available indices are considered
  91.  *        if possible(indices are not considered for lower nesting levels).
  92.  *        All unique paths are attached to the relation's 'pathlist' field.
  93.  *    
  94.  *        'level' is the current attribute nesting level, where 1 is the first.
  95.  *        'sortkeys' contains sort result info.
  96.  *    
  97.  *        RETURNS:  'rels'.
  98.  *    MODIFIES: rels
  99.  *    
  100.  */
  101.  
  102. /*  .. find-paths      */
  103.  
  104. LispValue
  105. find_rel_paths(rels,level,sortkeys)
  106.      LispValue rels,sortkeys ;
  107.      int level;
  108. {
  109.      LispValue temp;
  110.      Rel rel;
  111.      
  112.      foreach(temp,rels) {
  113.       LispValue sequential_scan_list;
  114.  
  115.       rel = (Rel)CAR(temp);
  116.       sequential_scan_list = lispCons((LispValue)create_seqscan_path(rel),
  117.                       LispNil);
  118.  
  119.       if(level > 1) {
  120.            set_pathlist(rel,sequential_scan_list);
  121.            /* XXX casting a list to a Path */
  122.            set_unorderedpath(rel, (PathPtr)sequential_scan_list);
  123.            set_cheapestpath(rel, (PathPtr)sequential_scan_list);
  124.         } 
  125.       else {
  126.            LispValue rel_index_scan_list = 
  127.          find_index_paths(rel,find_relation_indices(rel),
  128.                    get_clauseinfo(rel),
  129.                    get_joininfo(rel),sortkeys);
  130.            LispValue or_index_scan_list = 
  131.          create_or_index_paths(rel,get_clauseinfo(rel));
  132.  
  133.            set_pathlist(rel,add_pathlist(rel,sequential_scan_list,
  134.                            append(rel_index_scan_list,
  135.                                or_index_scan_list)));
  136.         } 
  137.     
  138.       /* The unordered path is always the last in the list.  
  139.        * If it is not the cheapest path, prune it.
  140.        */
  141.       prune_rel_path(rel, (Path)last_element(get_pathlist(rel))); 
  142.        }
  143.      foreach(temp, rels) {
  144.      rel = (Rel)CAR(temp);
  145.      set_size(rel, compute_rel_size(rel));
  146.      set_width(rel, compute_rel_width(rel));
  147.        }
  148.      return(rels);
  149.  
  150. }  /* end find_rel_path */
  151.  
  152. /*    
  153.  *        find-join-paths
  154.  *    
  155.  *        Find all possible joinpaths for a query by successively finding ways
  156.  *        to join single relations into join relations.  
  157.  *
  158.  *    if BushyPlanFlag is set, bushy tree plans will be generated:
  159.  *    Find all possible joinpaths(bushy trees) for a query by systematically
  160.  *    finding ways to join relations(both original and derived) together.
  161.  *    
  162.  *        'outer-rels' is    the current list of relations for which join paths 
  163.  *            are to be found, i.e., he current list of relations that 
  164.  *        have already been derived.
  165.  *        'levels-left' is the current join level being processed, where '1' is
  166.  *            the "last" level
  167.  *        'nest-level' is the current attribute nesting level
  168.  *    
  169.  *        Returns the final level of join relations, i.e., the relation that is
  170.  *    the result of joining all the original relations togehter.
  171.  *    
  172.  */
  173.  
  174. /*  .. find-join-paths, find-paths
  175.  */
  176. LispValue
  177. find_join_paths(outer_rels,levels_left,nest_level)
  178.      LispValue outer_rels;
  179.      int levels_left, nest_level;
  180. {
  181.     LispValue x;
  182.     Rel rel;
  183.  
  184.     /*
  185.     * Determine all possible pairs of relations to be joined at this level.
  186.     * Determine paths for joining these relation pairs and modify 'new-rels'
  187.     * accordingly, then eliminate redundant join relations.
  188.     */
  189.  
  190.     LispValue new_rels = find_join_rels(outer_rels);
  191.  
  192.     find_all_join_paths(new_rels, outer_rels, nest_level);
  193.  
  194.     new_rels = prune_joinrels(new_rels);
  195.  
  196.     /* 
  197.     ** for each expensive predicate in each path in each distinct rel, 
  198.     ** consider doing pullup  -- JMH 
  199.     */
  200.     if (XfuncMode != XFUNC_NOPULL && XfuncMode != XFUNC_OFF)
  201.       foreach(x, new_rels)
  202.     xfunc_trypullup((Rel)CAR(x));
  203.  
  204.     prune_rel_paths(new_rels);
  205.  
  206.     if(BushyPlanFlag) {
  207.       /*
  208.        * In case of bushy trees
  209.        * if there is still a join between a join relation and another
  210.        * relation, add a new joininfo that involves the join relation
  211.        * to the joininfo list of the other relation
  212.        */
  213.       add_new_joininfos(new_rels,outer_rels);
  214.     }
  215.  
  216.     foreach(x, new_rels) {
  217.        rel = (Rel)CAR(x);
  218.        set_size(rel, compute_rel_size(rel));
  219.        set_width(rel, compute_rel_width(rel));
  220.     }
  221.  
  222.     if(BushyPlanFlag) {
  223.       /* 
  224.        * prune rels that have been completely incorporated into
  225.        * new join rels
  226.        */
  227.       outer_rels = prune_oldrels(outer_rels);
  228.       /* 
  229.        * merge join rels if then contain the same list of base rels
  230.        */
  231.       outer_rels = merge_joinrels(new_rels,outer_rels);
  232.       _join_relation_list_ = outer_rels;
  233.     }
  234.    else {
  235.        _join_relation_list_ = new_rels;
  236.      }
  237.  
  238.     if(levels_left == 1) {
  239.       if(BushyPlanFlag)
  240.      return(final_join_rels(outer_rels));
  241.       else
  242.      return(new_rels);
  243.     } 
  244.     else {
  245.       if(BushyPlanFlag)
  246.       return(find_join_paths(outer_rels, levels_left - 1, nest_level));
  247.       else
  248.      return(find_join_paths(new_rels, levels_left - 1, nest_level));
  249.     } 
  250. }
  251.  
  252.  
  253. /*
  254.  * The following functions are solely for the purpose of debugging.
  255.  */
  256.  
  257. /*
  258.  * xStrcat --
  259.  *    Special strcat which returns concatenation into a static buffer.
  260.  */
  261. static
  262. char *xStrcat(s1, s2)
  263. char *s1, *s2;
  264. {
  265.     static char stringbuf[100];
  266.     sprintf(stringbuf, "%s%s",s1,s2);
  267.     return stringbuf;
  268. }
  269.  
  270. void
  271. printclauseinfo(ind,cl)
  272. char *ind;
  273. List cl;
  274. {
  275.     LispValue xc;
  276.     char indent[100];
  277.     strcpy(indent, ind);
  278.     foreach(xc,cl) {
  279.        CInfo c = (CInfo)CAR(xc);
  280.        if(c == (CInfo)NULL) continue;
  281.        printf("\n%sClauseInfo:    CInfo%lx",indent,(long)c);
  282.        printf("\n%sOp:        %u",indent,get_opno((Oper)get_op((List)get_clause(c))));
  283.        printf("\n%sLeftOp:    ",indent);
  284.        lispDisplay(get_varid(get_leftop((List)get_clause(c))));
  285.        printf("\n%sRightOp:    ",indent);
  286.        lispDisplay(get_varid(get_rightop((List)get_clause(c))));
  287.        printf("\n%sSelectivity:    %lg\n",indent,get_selectivity(c));
  288.     }
  289. }
  290.  
  291. void
  292. printjoininfo(ind,jl)
  293. char *ind;
  294. List jl;
  295. {
  296.     LispValue xj;
  297.     char indent[100];
  298.     strcpy(indent, ind);
  299.     foreach(xj,jl) {
  300.     JInfo j = (JInfo)CAR(xj);
  301.     if(joininfo_inactive(j)) continue;
  302.     printf("\n%sJoinInfo:    JInfo%lx",indent,(long)j);
  303.     printf("\n%sOtherRels:    ",indent);
  304.     lispDisplay(get_otherrels(j));
  305.     printf("\n%sClauseInfo:    ",indent);
  306.     printclauseinfo(xStrcat(indent, "    "),get_jinfoclauseinfo(j));
  307.     }
  308. }
  309.  
  310. void
  311. printpath(ind,p)
  312. char *ind;
  313. Path p;
  314. {
  315.     char indent[100];
  316.     strcpy(indent, ind);
  317.     if(p == (Path)NULL) return;
  318.     printf("%sPath:    0x%lx",indent,(long)p);
  319.     printf("\n%sParent:    ",indent);
  320.     lispDisplay(get_relids(get_parent(p)));
  321.     printf("\n%sPathType:    %ld",indent,get_pathtype(p));
  322.     printf("\n%sCost:    %lg",indent,get_path_cost(p));
  323.     switch(get_pathtype(p))  {
  324.     case T_NestLoop:
  325.         printf("\n%sClauseInfo:    \n",indent);
  326.         printclauseinfo(xStrcat(indent,"    "),get_pathclauseinfo((JoinPath)p));
  327.         printf("%sOuterJoinPath:    \n",indent);
  328.         printpath(xStrcat(indent,"    "),get_outerjoinpath((JoinPath)p));
  329.         printf("%sInnerJoinPath:    \n",indent);
  330.         printpath(xStrcat(indent,"    "),get_innerjoinpath((JoinPath)p));
  331.         printf("%sOuterJoinCost:    %lg",indent,get_outerjoincost(p));
  332.         printf("\n%sJoinId:    ",indent);
  333.         lispDisplay(get_joinid(p));
  334.         break;
  335.     case T_MergeJoin:
  336.         printf("\n%sClauseInfo: \n",indent);
  337.                 printclauseinfo(xStrcat(indent,"       "),get_pathclauseinfo((JoinPath)p));
  338.                 printf("%sOuterJoinPath:        \n",indent);
  339.                 printpath(xStrcat(indent," "),get_outerjoinpath((JoinPath)p));
  340.                 printf("%sInnerJoinPath:        \n",indent);
  341.                 printpath(xStrcat(indent," "),get_innerjoinpath((JoinPath)p));
  342.                 printf("%sOuterJoinCost:        %lg",indent,get_outerjoincost(p));
  343.                 printf("\n%sJoinId:     ",indent);
  344.                 lispDisplay(get_joinid(p));
  345.         printf("\n%sMergeClauses:    ",indent);
  346.         lispDisplay(get_path_mergeclauses((MergePath)p));
  347.         printf("\n%sOuterSortKeys:    ",indent);
  348.         lispDisplay(get_outersortkeys((MergePath)p));
  349.         printf("\n%sInnerSortKeys:    ",indent);
  350.         lispDisplay(get_innersortkeys((MergePath)p));
  351.         break;
  352.     case T_HashJoin:
  353.                 printf("\n%sClauseInfo: \n",indent);
  354.                 printclauseinfo(xStrcat(indent,"       "),get_pathclauseinfo((JoinPath)p));
  355.                 printf("%sOuterJoinPath:        \n",indent);
  356.                 printpath(xStrcat(indent," "),get_outerjoinpath((JoinPath)p));
  357.         printf("%sInnerJoinPath:        \n",indent);
  358.                 printpath(xStrcat(indent," "),get_innerjoinpath((JoinPath)p));
  359.                 printf("%sOuterJoinCost:        %lg",indent,get_outerjoincost(p));
  360.                 printf("\n%sJoinId:     ",indent);
  361.                 lispDisplay(get_joinid(p));
  362.         printf("\n%sHashClauses:    ",indent);
  363.         lispDisplay(get_path_hashclauses((HashPath)p));
  364.         printf("\n%sOuterHashKeys:    ",indent);
  365.         lispDisplay(get_outerhashkeys((HashPath)p));
  366.         printf("\n%sInnerHashKeys:    ",indent);
  367.         lispDisplay(get_innerhashkeys((HashPath)p));
  368.         break;
  369.     case T_IndexScan:
  370.         printf("\n%sIndexQual:    ",indent);
  371.         lispDisplay(get_indexqual((IndexPath)p));
  372.         break;
  373.     }
  374.     printf("\n");
  375. }
  376.  
  377. void
  378. printpathlist(ind, pl)
  379. char *ind;
  380. LispValue pl;
  381. {
  382.     LispValue xp;
  383.     char indent[100];
  384.     strcpy(indent,ind);
  385.     foreach(xp,pl) {
  386.     Path p = (Path)CAR(xp);
  387.     printpath(indent,p);
  388.     }
  389. }
  390.  
  391. void
  392. printrels(ind,rl)
  393. char *ind;
  394. List rl;
  395. {
  396.     LispValue xr;
  397.     char indent[100];
  398.     strcpy(indent,ind);
  399.     foreach(xr,rl) {
  400.     Rel r = (Rel)CAR(xr);
  401.     if(r == (Rel)NULL) continue;
  402.     printf("\n%sRel:    Rel%lx",indent,(long)r);
  403.     printf("\n%sRelid:    ",indent);
  404.     lispDisplay(get_relids(r));
  405.     printf("\n%sSize:    %u",indent,get_size(r));
  406.     printf("\n%sPathlist:    \n",indent);
  407.     printpathlist(xStrcat(indent,"    "),get_pathlist(r));
  408.     printf("%sClauseInfo:    \n",indent);
  409.     printclauseinfo(xStrcat(indent,"    "),get_clauseinfo(r));
  410.     printf("%sJoinInfo:    ",indent);
  411.     printjoininfo(xStrcat(indent,"    "),get_joininfo(r));
  412.      }
  413. }
  414.  
  415. void
  416. PrintRels(rl)
  417. List rl;
  418. {
  419.     printrels("",rl);
  420.     printf("\n");
  421. }
  422.  
  423. void
  424. PRel(r)
  425. Rel r;
  426. {
  427.     printrels("",lispCons((LispValue)r,LispNil));
  428. }
  429.