home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / planner / path / clausesel.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  9.6 KB  |  366 lines
  1. /* 
  2.  * FILE
  3.  *     clausesel 
  4.  * 
  5.  * DESCRIPTION 
  6.  *     Routines to compute and set clause selectivities 
  7.  * 
  8.  */ 
  9.  
  10. /* RcsId ("$Header: /private/postgres/src/planner/path/RCS/clausesel.c,v 1.25 1992/08/21 05:45:05 mer Exp $"); */
  11.  
  12. /*     
  13.  *      EXPORTS
  14.  *             set_clause_selectivities
  15.  *             product_selec
  16.  *             set_rest_relselec
  17.  *             compute_clause_selec
  18.  */
  19.  
  20. #include "nodes/pg_lisp.h"
  21. #include "nodes/relation.h"
  22. #include "nodes/relation.a.h"
  23. #include "nodes/primnodes.h"
  24. #include "nodes/primnodes.a.h"
  25.  
  26. #include "planner/internal.h"
  27. #include "planner/clause.h"
  28. #include "planner/clauses.h"
  29. #include "planner/clausesel.h"
  30. #include "planner/plancat.h"
  31. #include "parser/parsetree.h"
  32.  
  33. #include "catalog/pg_proc.h"
  34. #include "catalog/pg_operator.h"
  35.  
  36. /*             ----  ROUTINES TO SET CLAUSE SELECTIVITIES  ----   */
  37.  
  38.  
  39. /*    
  40.  *        set_clause_selectivities
  41.  *    
  42.  *        Sets the selectivity field for each of clause in 'clauseinfo-list'
  43.  *        to 'new-selectivity'.  If the selectivity has already been set, reset 
  44.  *        it only if the new one is better.
  45.  *    
  46.  *        Returns nothing of interest.
  47.  *
  48.  */
  49.  
  50. /*  .. create_index_path
  51.  */
  52. void
  53. set_clause_selectivities (clauseinfo_list,new_selectivity)
  54.      LispValue clauseinfo_list; 
  55.      Cost new_selectivity ;
  56. {
  57.     LispValue temp;
  58.     CInfo clausenode;
  59.     Cost cost_clause;
  60.  
  61.     foreach (temp,clauseinfo_list) {
  62.     clausenode = (CInfo)CAR(temp);
  63.     cost_clause = get_selectivity(clausenode);
  64.     if ( FLOAT_IS_ZERO(cost_clause) || new_selectivity < cost_clause) {
  65.         set_selectivity (clausenode,new_selectivity);
  66.     }
  67.     }
  68. } /* end set_clause_selectivities */
  69.  
  70. /*    
  71.  *        product_selec
  72.  *    
  73.  *        Multiplies the selectivities of each clause in 'clauseinfo-list'.
  74.  *    
  75.  *        Returns a flonum corresponding to the selectivity of 'clauseinfo-list'.
  76.  *    
  77.  */
  78.  
  79. /*  .. compute-joinrel-size, compute-rel-size     */
  80.  
  81. Cost
  82. product_selec (clauseinfo_list)
  83.      LispValue clauseinfo_list ;
  84. {
  85.      Cost result = 1.0;
  86.      if ( consp (clauseinfo_list) ) {
  87.       LispValue xclausenode = LispNil;
  88.       Cost temp;
  89.  
  90.       foreach(xclausenode,clauseinfo_list) {
  91.            temp = get_selectivity((CInfo)CAR(xclausenode));
  92.            result = result * temp;
  93.       }
  94.      }
  95.      return(result);
  96. } /* end product_selec */
  97.  
  98. /*    
  99.  *        set_rest_relselec
  100.  *    
  101.  *        Scans through clauses on each relation and assigns a selectivity to
  102.  *        those clauses that haven't been assigned a selectivity by an index.
  103.  *    
  104.  *        Returns nothing of interest.
  105.  *       MODIFIES: selectivities of the various rel's clauseinfo
  106.  *          slots. 
  107.  */
  108.  
  109. /*  .. find-paths    */
  110.  
  111. void
  112. set_rest_relselec (rel_list)
  113.      LispValue rel_list ;
  114. {
  115.      Rel rel;
  116.      LispValue x;
  117.      foreach (x,rel_list) {
  118.      rel = (Rel)CAR(x);
  119.      set_rest_selec(get_clauseinfo(rel));
  120.      }
  121. }
  122.  
  123. /*    
  124.  *        set_rest_selec
  125.  *    
  126.  *        Sets the selectivity fields for those clauses within a single
  127.  *        relation's 'clauseinfo-list' that haven't already been set.
  128.  *    
  129.  *        Returns nothing of interest.
  130.  *    
  131.  */
  132.  
  133. /*  .. set_rest_relselec    */
  134.  
  135. void
  136. set_rest_selec (clauseinfo_list)
  137. LispValue clauseinfo_list ;
  138. {
  139.     LispValue temp = LispNil;
  140.     CInfo clausenode = (CInfo)NULL;
  141.     Cost cost_clause;
  142.     
  143.     foreach (temp,clauseinfo_list) {
  144.     clausenode = (CInfo)CAR(temp);
  145.     cost_clause = get_selectivity(clausenode);
  146.  
  147.     /*    Check to see if the selectivity of this clause or any 'or' */
  148.     /*    subclauses (if any) haven't been set yet. */
  149.  
  150.     if (valid_or_clause(clausenode) || FLOAT_IS_ZERO(cost_clause)) {
  151.         set_selectivity (clausenode,
  152.                  compute_clause_selec((List)get_clause(clausenode),
  153.                           lispCons(lispFloat(cost_clause), 
  154.             /* XXX this bogus */            LispNil)));
  155.     }
  156.     }
  157. } /* end set_rest_selec */
  158.  
  159. /*            ----  ROUTINES TO COMPUTE SELECTIVITIES  ----
  160.  */
  161.  
  162. /*    
  163.  *        compute_clause_selec
  164.  *    
  165.  *        Given a clause, this routine will compute the selectivity of the
  166.  *        clause by calling 'compute_selec' with the appropriate parameters
  167.  *        and possibly use that return value to compute the real selectivity
  168.  *        of a clause.
  169.  *    
  170.  *        'or-selectivities' are selectivities that have already been assigned
  171.  *            to subclauses of an 'or' clause.
  172.  *    
  173.  *        Returns a flonum corresponding to the clause selectivity.
  174.  *    
  175.  */
  176.  
  177. /*  .. add-clause-to-rels, set_rest_selec    */
  178.  
  179. Cost
  180. compute_clause_selec (clause,or_selectivities)
  181.      LispValue clause,or_selectivities ;
  182. {
  183. /*    if (!is_clause (clause)) {  NO!!! THIS IS A BUG.  -- JMH 3/9/92 */
  184.       if (is_clause (clause)) {
  185.     /* Boolean variables get a selectivity of 1/2. */
  186.     return(0.5);
  187.     } 
  188.     else if (not_clause (clause)) {
  189.     /* 'not' gets "1.0 - selectivity-of-inner-clause". */
  190.     return (1.000000 - compute_selec (lispCons(get_notclausearg (clause),
  191.                            LispNil),
  192.                       or_selectivities));
  193.     }
  194.     else if (or_clause (clause)) {
  195.     /* Both 'or' and 'and' clauses are evaluated as described in 
  196.      *    (compute_selec). 
  197.      */
  198.     return (compute_selec (get_orclauseargs (clause),or_selectivities));
  199.     } 
  200.     else {
  201.     return(compute_selec (lispCons(clause,LispNil),or_selectivities));
  202.     } 
  203. }
  204.  
  205. /*    
  206.  *        compute_selec
  207.  *    
  208.  *        Computes the selectivity of a clause.
  209.  *    
  210.  *        If there is more than one clause in the argument 'clauses', then the
  211.  *        desired selectivity is that of an 'or' clause.  Selectivities for an
  212.  *        'or' clause such as (OR a b) are computed by finding the selectivity
  213.  *        of a (s1) and b (s2) and computing s1+s2 - s1*s2.
  214.  *    
  215.  *        In addition, if the clause is an 'or' clause, individual selectivities
  216.  *        may have already been assigned by indices to subclauses.  These values
  217.  *        are contained in the list 'or-selectivities'.
  218.  *    
  219.  *        Returns the clause selectivity as a flonum.
  220.  *    
  221.  */
  222.  
  223. /*  .. compute_clause_selec, compute_selec   */
  224.  
  225. Cost
  226. compute_selec (clauses,or_selectivities)
  227.      LispValue clauses,or_selectivities ;
  228. {
  229.     Cost s1 = 0;
  230.     LispValue clause = CAR (clauses);
  231.  
  232.     if(null (clauses)) 
  233.      {
  234.      s1 = 1.0;
  235.      }
  236.     else if (IsA(clause,Const))
  237.      {
  238.      s1 = ((bool)get_constvalue((Const)clause)) ? 1.0 : 0.0;
  239.      }
  240.     else if (IsA(clause,Var))
  241.      {
  242.      ObjectId relid;
  243.  
  244.      relid = (ObjectId)
  245.         CInteger(translate_relid(CAR(get_varid((Var)clause))));
  246.      /*
  247.       * we have a bool Var.  This is exactly equivalent to the clause:
  248.       *    reln.attribute = 't'
  249.       * so we compute the selectivity as if that is what we have. The
  250.       * magic #define constants are a hack.  I didn't want to have to
  251.       * do system cache look ups to find out all of that info.
  252.       */
  253.      s1 = restriction_selectivity(EqualSelectivityProcedure,
  254.                       BooleanEqualOperator,
  255.                       relid,
  256.                       CInteger(CADR(get_varid((Var)clause))),
  257.                       (Datum) 't',
  258.                       _SELEC_CONSTANT_RIGHT_);
  259.  
  260.      }
  261.     /* If s1 has already been assigned by an index, use that value. */ 
  262.     else if (or_selectivities)
  263.      {
  264.      s1 = (int) CAR (or_selectivities);
  265.      } 
  266.     else if (IsA(CAR(clause),Func))  /* this isn't an Oper, it's a Func!! */
  267.      {
  268.      /*
  269.      ** This is not an operator, so we guess at the selectivity.  
  270.      ** THIS IS A HACK TO GET V4 OUT THE DOOR.  FUNCS SHOULD BE
  271.      ** ABLE TO HAVE SELECTIVITIES THEMSELVES.
  272.      **     -- JMH 7/9/92
  273.      */
  274.        s1 = 0.1;
  275.      }
  276.     else if (1 == NumRelids ((Expr)clause)) {
  277.  
  278.     /* ...otherwise, calculate s1 from 'clauses'. 
  279.      *    The clause is not a join clause, since there is 
  280.      *    only one relid in the clause.  The clause 
  281.      *    selectivity will be based on the operator 
  282.      *    selectivity and operand values. 
  283.      */
  284.  
  285.     LispValue relattvals = get_relattval (clause);
  286.     ObjectId opno = get_opno ((Oper)get_op (clause));
  287.     RegProcedure oprrest = get_oprrest (opno);
  288.     LispValue relid = LispNil;
  289.     
  290.     if (translate_relid (CAR(relattvals)))
  291.       relid = translate_relid(CAR(relattvals));
  292.     else
  293.       relid = lispInteger(_SELEC_VALUE_UNKNOWN_);
  294.     
  295.     s1 = (Cost)restriction_selectivity (oprrest,
  296.                           opno,
  297.                           CInteger(relid),
  298.                           CInteger(CADR (relattvals)),
  299.                           (char*)CInteger((CADDR(relattvals))),
  300.                           CInteger(CADDR 
  301.                                (CDR(relattvals))));
  302.     }
  303.      else {
  304.      
  305.      /*    The clause must be a join clause.  The clause 
  306.       *    selectivity will be based on the relations to be 
  307.       *    scanned and the attributes they are to be joined 
  308.       *    on. 
  309.       */
  310.      LispValue relsatts = get_relsatts (clause);
  311.      ObjectId opno = get_opno((Oper)get_op (clause));
  312.      RegProcedure oprjoin = get_oprjoin (opno);
  313.      LispValue relid1 = LispNil;
  314.      LispValue relid2 = LispNil;
  315.      
  316.      if(translate_relid (CAR(relsatts)))
  317.        relid1 = translate_relid(CAR(relsatts));
  318.      else
  319.        relid1 =  lispInteger(_SELEC_VALUE_UNKNOWN_);
  320.      if (translate_relid (CADDR (relsatts)))
  321.         relid2 = translate_relid(CADDR(relsatts));
  322.      else
  323.        relid2 =  lispInteger(_SELEC_VALUE_UNKNOWN_);
  324.      s1 = (Cost)join_selectivity (oprjoin,
  325.                     opno,
  326.                     CInteger(relid1),
  327.                     CInteger(CADR (relsatts)),
  328.                     CInteger(relid2),
  329.                     CInteger(CADDR (CDR (relsatts))));
  330.      }
  331.     
  332.     /*    A null clause list eliminates no tuples, so return a selectivity 
  333.      *    of 1.0.  If there is only one clause, the selectivity is not 
  334.      *    that of an 'or' clause, but rather that of the single clause.
  335.      */
  336.     
  337.     if (length (clauses) < 2) {
  338.     return(s1);
  339.     } 
  340.     else {
  341.     /* Compute selectivity of the 'or'ed subclauses. */
  342.     /* Added check for taking CDR(LispNil).  -- JMH 3/9/92 */
  343.       Cost s2;
  344.       if (or_selectivities != LispNil)
  345.         s2 = compute_selec (CDR (clauses),CDR (or_selectivities));
  346.       else
  347.         s2 = compute_selec (CDR (clauses), LispNil);
  348.       return (s1 + s2 - s1*s2);
  349.       }
  350. } /* end compute_selec */
  351.  
  352. /*  .. compute_selec */
  353.  
  354. LispValue
  355. translate_relid(relid)
  356.     LispValue relid;
  357. {
  358.     if (integerp(relid))
  359.     return
  360.         getrelid(CInteger(relid),_query_range_table_);
  361.     
  362.     return
  363.     lispInteger(0);
  364. }
  365.  
  366.