home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / planner / path / indxpath.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-05  |  23.7 KB  |  890 lines
  1.  
  2. /*     
  3.  *      FILE
  4.  *         indxpath
  5.  *     
  6.  *      DESCRIPTION
  7.  *         Routines to determine which indices are usable for 
  8.  *         scanning a given relation
  9.  *     
  10.  */
  11.  /* RcsId("$Header: /private/postgres/src/planner/path/RCS/indxpath.c,v 1.32 1992/07/12 10:57:31 joey Exp $"); */
  12.  
  13. /*     
  14.  *      EXPORTS
  15.  *             find-index-paths
  16.  */
  17. #include <math.h>
  18.  
  19. #include "tmp/postgres.h"
  20. #include "access/att.h"
  21.  
  22. #include "nodes/pg_lisp.h"
  23. #include "nodes/relation.h"
  24. #include "nodes/relation.a.h"
  25.  
  26. #include "utils/lsyscache.h"
  27.  
  28. #include "planner/internal.h"
  29. #include "planner/indxpath.h"
  30. #include "planner/clauses.h"
  31. #include "planner/clauseinfo.h"
  32. #include "planner/cfi.h"
  33. #include "planner/costsize.h"
  34. #include "planner/pathnode.h"
  35. #include "planner/xfunc.h"
  36.  
  37. /*    
  38.  *        find-index-paths
  39.  *    
  40.  *        Finds all possible index paths by determining which indices in the
  41.  *        list 'indices' are usable.
  42.  *    
  43.  *        To be usable, an index must match against either a set of 
  44.  *        restriction clauses or join clauses.
  45.  *    
  46.  *        Note that the current implementation requires that there exist
  47.  *        matching clauses for every key in the index (i.e., no partial
  48.  *        matches are allowed).
  49.  *    
  50.  *        If an index can't be used with restriction clauses, but its keys
  51.  *        match those of the result sort order (according to information stored
  52.  *        within 'sortkeys'), then the index is also considered. 
  53.  *    
  54.  *        'rel' is the relation entry to which these index paths correspond
  55.  *        'indices' is a list of possible index paths
  56.  *        'clauseinfo-list' is a list of restriction clauseinfo nodes for 'rel'
  57.  *        'joininfo-list' is a list of joininfo nodes for 'rel'
  58.  *        'sortkeys' is a node describing the result sort order (from
  59.  *            (find_sortkeys))
  60.  *    
  61.  *        Returns a list of index nodes.
  62.  *    
  63.  */
  64.  
  65. /*  .. find_index_paths, find_rel_paths */
  66.  
  67. LispValue
  68. find_index_paths (rel,indices,clauseinfo_list,joininfo_list,sortkeys)
  69.      Rel rel;
  70.      LispValue indices,clauseinfo_list,joininfo_list,sortkeys ;
  71.  
  72. {
  73.     LispValue scanclausegroups = LispNil;
  74.     LispValue scanpaths = LispNil;
  75.     Rel       index = (Rel)NULL;
  76.     LispValue joinclausegroups = LispNil;
  77.     LispValue joinpaths = LispNil;
  78.     LispValue sortpath = LispNil;
  79.     LispValue retval = LispNil;
  80.     LispValue temp = LispNil;
  81.     LispValue add_index_paths();
  82.     
  83.     if(!consp(indices))
  84.     return(NULL);
  85.     
  86.     index = (Rel)CAR (indices);
  87.  
  88.     /*  1. If this index has only one key, try matching it against 
  89.      * subclauses of an 'or' clause.  The fields of the clauseinfo
  90.      * nodes are marked with lists of the matching indices no path
  91.      * are actually created. 
  92.      *
  93.      * XXX NOTE:  Currently btrees dos not support indices with
  94.      * > 1 key, so the following test will always be true for
  95.      * now but we have decided not to support index-scans 
  96.      * on disjunction . -- lp
  97.      */
  98.  
  99.     if (SingleAttributeIndex(index)) 
  100.     {
  101.     match_index_orclauses (rel,
  102.                    index,
  103.                    CAR(get_indexkeys(index)),
  104.                    CAR(get_classlist(index)),
  105.                    clauseinfo_list);
  106.     }
  107.  
  108.     /* 2. If the keys of this index match any of the available
  109.      * restriction clauses, then create pathnodes corresponding
  110.      * to each group of usable clauses.
  111.      */
  112.  
  113.     scanclausegroups = group_clauses_by_indexkey (rel,
  114.                           index,
  115.                           get_indexkeys(index),
  116.                           get_classlist(index),
  117.                           clauseinfo_list,
  118.                           false);
  119.  
  120.     scanpaths = LispNil;
  121.     if (consp (scanclausegroups))
  122.     scanpaths = create_index_paths (rel,
  123.                     index,
  124.                     scanclausegroups,
  125.                     false);
  126.          
  127.     /* 3. If this index can be used with any join clause, then 
  128.      * create pathnodes for each group of usable clauses.  An 
  129.      * index can be used with a join clause if its ordering is 
  130.      * useful for a mergejoin, or if the index can possibly be 
  131.      * used for scanning the inner relation of a nestloop join. 
  132.      */
  133.          
  134.     joinclausegroups = indexable_joinclauses(rel,index,joininfo_list);
  135.     joinpaths = LispNil;
  136.  
  137.     if (consp (joinclausegroups))
  138.     {
  139.     LispValue new_join_paths = create_index_paths(rel,
  140.                               index,
  141.                               joinclausegroups, 
  142.                               true);
  143.     LispValue innerjoin_paths = index_innerjoin(rel,joinclausegroups,index);
  144.  
  145.     set_innerjoin (rel,nconc (get_innerjoin(rel), innerjoin_paths));
  146.     joinpaths = new_join_paths;
  147.     }
  148.          
  149.     /* 4. If this particular index hasn't already been used above,
  150.      *   then check to see if it can be used for ordering a  
  151.      *   user-specified sort.  If it can, add a pathnode for the 
  152.      *   sorting scan. 
  153.      */
  154.          
  155.     sortpath = LispNil;
  156.     if ( valid_sortkeys(sortkeys)
  157.      && null(scanclausegroups)
  158.      && null(joinclausegroups)
  159.      && (CInteger(get_relid((SortKey)sortkeys)) == 
  160.          CInteger(CAR(get_relids(rel))))
  161.      && equal_path_path_ordering(get_sortorder((SortKey)sortkeys),
  162.                      get_ordering(index))
  163.      && equal ((Node)get_sortkeys((SortKey)sortkeys),
  164.            (Node)get_indexkeys (index)) )
  165.     {
  166.     sortpath = lispCons((LispValue)create_index_path(rel,
  167.                           index,
  168.                           LispNil,
  169.                           false),
  170.                 LispNil);
  171.     }
  172.     
  173.     /*
  174.      *  Some sanity checks to make sure that
  175.      *  the indexpath is valid.
  176.      */
  177.     if (!null(scanpaths))
  178.     retval = add_index_paths(retval,scanpaths);
  179.     if ( !null(joinpaths) )
  180.     retval = add_index_paths(retval,joinpaths);
  181.     if (!null(sortpath))
  182.     retval = add_index_paths(retval,sortpath);
  183.     
  184.     if (!null((temp = find_index_paths (rel,
  185.                     CDR (indices),
  186.                     clauseinfo_list,
  187.                     joininfo_list,sortkeys))))
  188.     {
  189.       retval = append (retval,temp);
  190.     }
  191.  
  192.     return retval;
  193.  
  194. }  /* function end */
  195.  
  196.  
  197. /*            ----  ROUTINES TO MATCH 'OR' CLAUSES  ----   */
  198.  
  199.  
  200. /*    
  201.  *        match-index-orclauses
  202.  *    
  203.  *        Attempt to match an index against subclauses within 'or' clauses.
  204.  *        If the index does match, then the clause is marked with information
  205.  *        about the index.
  206.  *    
  207.  *        Essentially, this adds 'index' to the list of indices in the
  208.  *        ClauseInfo field of each of the clauses which it matches.
  209.  *    
  210.  *        'rel' is the node of the relation on which the index is defined.
  211.  *        'index' is the index node.
  212.  *        'indexkey' is the (single) key of the index
  213.  *        'class' is the class of the operator corresponding to 'indexkey'.
  214.  *        'clauseinfo-list' is the list of available restriction clauses.
  215.  *    
  216.  *        Returns nothing.
  217.  *    
  218.  */
  219.  
  220. /*  .. find-index-paths   */
  221.  
  222. void
  223. match_index_orclauses (rel,index,indexkey,xclass,clauseinfo_list)
  224. Rel rel,index;
  225. LispValue indexkey,xclass,clauseinfo_list ;
  226. {
  227.     CInfo clauseinfo = (CInfo)NULL;
  228.     LispValue i = LispNil;
  229.  
  230.     foreach (i, clauseinfo_list) {
  231.     clauseinfo = (CInfo)CAR(i);
  232.     if ( valid_or_clause((LispValue)clauseinfo)) {
  233.         
  234.         /* Mark the 'or' clause with a list of indices which 
  235.          * match each of its subclauses.  The list is
  236.          * generated by adding 'index' to the existing
  237.          * list where appropriate.
  238.          */
  239.         set_indexids (clauseinfo,
  240.               match_index_orclause (rel,index,indexkey,
  241.                         xclass,
  242.                         get_orclauseargs
  243.                         ((List)get_clause(clauseinfo)),
  244.                         get_indexids (clauseinfo)));
  245.     }
  246.    }
  247. }  /* function end */
  248.  
  249. /*
  250.  *    match_index_operand()
  251.  *
  252.  *    Generalize test for a match between an existing index's key
  253.  *    and the operand on the rhs of a restriction clause.  Now check
  254.  *    for functional indices as well.
  255.  */
  256. bool
  257. match_index_to_operand(indexkey, operand, rel, index)
  258.     LispValue indexkey;
  259.     LispValue operand;
  260.     Rel rel;
  261.     Rel index;
  262. {
  263.     /*
  264.      * Normal index.
  265.      */
  266.     if (index->indproc == InvalidObjectId)
  267.     return match_indexkey_operand(indexkey, operand, rel);
  268.  
  269.     /*
  270.      * functional index check
  271.      */
  272.     return (function_index_operand(operand, rel, index));
  273. }
  274. /*    
  275.  *        match-index-orclause
  276.  *    
  277.  *        Attempts to match an index against the subclauses of an 'or' clause.
  278.  *    
  279.  *        A match means that:
  280.  *        (1) the operator within the subclause can be used with one
  281.  *             of the index's operator classes, and
  282.  *        (2) there is a usable key that matches the variable within a
  283.  *             sargable clause.
  284.  *    
  285.  *        'or-clauses' are the remaining subclauses within the 'or' clause
  286.  *        'other-matching-indices' is the list of information on other indices
  287.  *            that have already been matched to subclauses within this
  288.  *            particular 'or' clause (i.e., a list previously generated by
  289.  *            this routine)
  290.  *    
  291.  *        Returns a list of the form ((a b c) (d e f) nil (g h) ...) where
  292.  *        a,b,c are nodes of indices that match the first subclause in
  293.  *        'or-clauses', d,e,f match the second subclause, no indices
  294.  *        match the third, g,h match the fourth, etc.
  295.  */
  296.  
  297. /*  .. match-index-orclauses       */
  298.  
  299. LispValue
  300. match_index_orclause (rel,index,indexkey,xclass,
  301.               or_clauses,other_matching_indices)
  302.      Rel rel,index;
  303.      LispValue indexkey,xclass,or_clauses,other_matching_indices ;
  304. {
  305.     /* XXX - lisp mapCAR  -- may be wrong. */
  306.     LispValue clause = LispNil;
  307.     LispValue matched_indices  = other_matching_indices;
  308.     LispValue index_list = LispNil;
  309.     LispValue clist;
  310.     LispValue ind;
  311.  
  312.     if (!matched_indices)
  313.     matched_indices = lispCons(LispNil, LispNil);
  314.  
  315.     for (clist = or_clauses, ind = matched_indices; 
  316.      clist; 
  317.      clist = CDR(clist), ind = CDR(ind))
  318.     {
  319.     clause = CAR(clist);
  320.     if (is_clause (clause) && 
  321.         op_class(get_opno((Oper)get_op(clause)),CInteger(xclass)) && 
  322.         match_index_to_operand (indexkey,
  323.                     get_leftop(clause),
  324.                     rel,
  325.                     index) &&
  326.         IsA(get_rightop (clause),Const)) {
  327.       
  328.       matched_indices =  lispCons((LispValue)index, matched_indices);
  329.       index_list = nappend1(index_list,
  330.                 matched_indices);
  331.     }
  332.     }
  333.     return(index_list);
  334.      
  335. }  /* function end */
  336.  
  337. /*            ----  ROUTINES TO CHECK RESTRICTIONS  ----      */
  338.  
  339.  
  340. /*
  341.  * DoneMatchingIndexKeys() - MACRO
  342.  *
  343.  * Determine whether we should continue matching index keys in a clause.
  344.  * Depends on if there are more to match or if this is a functional index.
  345.  * In the latter case we stop after the first match since the there can
  346.  * be only key (i.e. the function's return value) and the attributes in
  347.  * keys list represent the arguments to the function.  -mer 3 Oct. 1991
  348.  */
  349. #define DoneMatchingIndexKeys(indexkeys, index) \
  350.     ((CDR (indexkeys) == LispNil) || \
  351.      (CInteger(CADR(indexkeys)) == 0) || \
  352.      (get_indproc(index) != InvalidObjectId))
  353.  
  354. /*    
  355.  *        group-clauses-by-indexkey
  356.  *    
  357.  *        Determines whether there are clauses which will match each and every
  358.  *        one of the remaining keys of an index.  
  359.  *    
  360.  *        'rel' is the node of the relation corresponding to the index.
  361.  *        'indexkeys' are the remaining index keys to be matched.
  362.  *        'classes' are the classes of the index operators on those keys.
  363.  *        'clauses' is either:
  364.  *            (1) the list of available restriction clauses on a single
  365.  *                relation, or
  366.  *            (2) a list of join clauses between 'rel' and a fixed set of
  367.  *                relations,
  368.  *            depending on the value of 'join'.
  369.  *        'startlist' is a list of those clause nodes that have matched the keys 
  370.  *            that have already been checked.
  371.  *        'join' is a flag indicating that the clauses being checked are join
  372.  *            clauses.
  373.  *    
  374.  *        Returns all possible groups of clauses that will match (given that
  375.  *        one or more clauses can match any of the remaining keys).
  376.  *        E.g., if you have clauses A, B, and C, ((A B) (A C)) might be 
  377.  *        returned for an index with 2 keys.
  378.  *    
  379.  */
  380.  
  381. /*  .. find-index-paths, group-clauses-by-indexkey, indexable-joinclauses  */
  382.  
  383. LispValue
  384. group_clauses_by_indexkey (rel,index,indexkeys,classes,clauseinfo_list,join)
  385.     Rel rel,index;
  386.     LispValue indexkeys,classes,clauseinfo_list;
  387.     bool join;
  388. {
  389.     LispValue curCinfo        = LispNil;
  390.     CInfo matched_clause    = (CInfo)NULL;
  391.     LispValue retlist        = LispNil;
  392.     LispValue clausegroup    = LispNil;
  393.  
  394.  
  395.     if ( !consp (clauseinfo_list) )
  396.     return LispNil;
  397.  
  398.     foreach (curCinfo,clauseinfo_list) {
  399.     CInfo temp        = (CInfo)CAR(curCinfo);
  400.     LispValue curIndxKey    = indexkeys;
  401.     LispValue curClass    = classes;
  402.  
  403.     do {
  404.         /*
  405.          * If we can't find any matching clauses for the first of 
  406.          * the remaining keys, give up.
  407.          */
  408.         matched_clause = match_clause_to_indexkey (rel, 
  409.                                index, 
  410.                                CAR(curIndxKey),
  411.                                CAR(curClass),
  412.                                temp,
  413.                                join);
  414.         if ( !matched_clause )
  415.         break;
  416.  
  417.         clausegroup = cons ((LispValue)matched_clause,clausegroup);
  418.         curIndxKey = CDR(curIndxKey);
  419.         curClass = CDR(curClass);
  420.  
  421.     } while ( !DoneMatchingIndexKeys(indexkeys, index) );
  422.     }
  423.  
  424.     if (consp(clausegroup))
  425.     return(lispCons(clausegroup,LispNil));
  426.     return LispNil;
  427. }
  428.  
  429. /*
  430.  * IndexScanableClause ()  MACRO
  431.  *
  432.  * Generalize condition on which we match a clause with an index.
  433.  * Now we can match with functional indices.
  434.  */
  435. #define IndexScanableOperand(opnd, indkeys, rel, index) \
  436.     ((index->indproc == InvalidObjectId) ? \
  437.     equal_indexkey_var(indkeys,opnd) : \
  438.     function_index_operand(opnd,rel,index))
  439.  
  440. /*    
  441.  *        match_clause_to-indexkey
  442.  *    
  443.  *        Finds the first of a relation's available restriction clauses that
  444.  *        matches a key of an index.
  445.  *    
  446.  *        To match, the clause must:
  447.  *        (1) be in the form (op var const) if the clause is a single-
  448.  *            relation clause, and
  449.  *        (2) contain an operator which is in the same class as the index
  450.  *            operator for this key.
  451.  *    
  452.  *        If the clause being matched is a join clause, then 'join' is t.
  453.  *    
  454.  *        Returns a single clauseinfo node corresponding to the matching 
  455.  *        clause.
  456.  *
  457.  *      NOTE:  returns nil if clause is an or_clause.
  458.  *    
  459.  */
  460.  
  461. /*  .. group-clauses-by-indexkey  */
  462.  
  463. CInfo
  464. match_clause_to_indexkey (rel,index,indexkey,xclass,clauseInfo,join)
  465.      Rel rel,index;
  466.      LispValue indexkey,xclass;
  467.      CInfo clauseInfo;
  468.      bool join;
  469. {
  470.     LispValue clause    = get_clause (clauseInfo);
  471.     Var leftop    = get_leftop (clause);
  472.     Var rightop    = get_rightop (clause);
  473.     ObjectId join_op = InvalidObjectId;
  474.     bool isIndexable = false;
  475.  
  476.     if ( or_clause (clause))
  477.     return ((CInfo)NULL);
  478.  
  479.      /*
  480.       * If this is not a join clause, check for clauses of the form:
  481.       * (operator var/func constant) and (operator constant var/func)
  482.       */
  483.     if(!join) 
  484.     {
  485.     ObjectId restrict_op = InvalidObjectId;
  486.  
  487.     /*
  488.      * Check for standard s-argable clause
  489.      */
  490.     if (IsA(rightop,Const))
  491.     {
  492.         restrict_op = get_opno((Oper)get_op(clause));
  493.         isIndexable =
  494.         ( op_class(restrict_op, CInteger(xclass)) &&
  495.           IndexScanableOperand((LispValue)leftop,indexkey,rel,index) );
  496.     }
  497.  
  498.     /*
  499.      * Must try to commute the clause to standard s-arg format.
  500.      */
  501.     else if (IsA(leftop,Const))
  502.     {
  503.         restrict_op = get_commutator(get_opno((Oper)get_op(clause)));
  504.  
  505.         if ( (restrict_op != InvalidObjectId) &&
  506.           op_class(restrict_op, CInteger(xclass)) &&
  507.           IndexScanableOperand((LispValue)rightop,indexkey,rel,index) )
  508.         {
  509.         isIndexable = true;
  510.         /*
  511.          * In place list modification.
  512.          * (op const var/func) -> (op var/func const)
  513.          */
  514.         /* BUG!  Old version:
  515.            CommuteClause(clause, restrict_op);
  516.         */
  517.         CommuteClause(clause);
  518.         }
  519.     }
  520.     } 
  521.  
  522.     /*
  523.      * Check for an indexable scan on one of the join relations.
  524.      * clause is of the form (operator var/func var/func)
  525.      */
  526.     else
  527.     {
  528.     if (match_index_to_operand (indexkey,rightop,rel,index))
  529.         join_op = get_commutator(get_opno((Oper)get_op(clause)));
  530.  
  531.     else if (match_index_to_operand (indexkey,leftop,rel,index))
  532.         join_op = get_opno((Oper)get_op(clause));
  533.  
  534.     if ( join_op && op_class(join_op,CInteger(xclass)) &&
  535.          join_clause_p(clause))
  536.     {
  537.         isIndexable = true;
  538.  
  539.         /*
  540.          * If we're using the operand's commutator we must
  541.          * commute the clause.
  542.          */
  543.         if ( join_op != get_opno((Oper)get_op(clause)) )
  544.         CommuteClause(clause);
  545.     }
  546.     }
  547.  
  548.     if (isIndexable)
  549.     return(clauseInfo);
  550.  
  551.     return(NULL);
  552. }
  553.  
  554.  
  555.               
  556. /*            ----  ROUTINES TO CHECK JOIN CLAUSES  ----      */
  557.  
  558.  
  559. /*    
  560.  *        indexable-joinclauses
  561.  *    
  562.  *        Finds all groups of join clauses from among 'joininfo-list' that can 
  563.  *        be used in conjunction with 'index'.
  564.  *    
  565.  *        The first clause in the group is marked as having the other relation
  566.  *        in the join clause as its outer join relation.
  567.  *    
  568.  *        Returns a list of these clause groups.
  569.  *    
  570.  */
  571.  
  572. /*  .. find-index-paths      */
  573.  
  574. LispValue
  575. indexable_joinclauses (rel,index,joininfo_list)
  576.      Rel rel,index;
  577.      List joininfo_list ;
  578. {
  579.     /*  XXX Lisp Mapcan -- may be wrong  */
  580.  
  581.     JInfo joininfo = (JInfo)NULL;
  582.     LispValue cg_list = LispNil;
  583.     LispValue i = LispNil;
  584.     LispValue clausegroups = LispNil;
  585.  
  586.     foreach(i,joininfo_list) { 
  587.     joininfo = (JInfo)CAR(i);
  588.     clausegroups = 
  589.       group_clauses_by_indexkey (rel,
  590.                      index,
  591.                      get_indexkeys(index),
  592.                      get_classlist (index),
  593.                      get_jinfoclauseinfo(joininfo),
  594.                      true);
  595.  
  596.     if ( consp (clausegroups)) {
  597.         set_cinfojoinid((CInfo)CAAR(clausegroups),
  598.             get_otherrels(joininfo));
  599.     }
  600.     cg_list = nconc(cg_list,clausegroups);
  601.     }
  602.     return(cg_list);
  603. }  /* function end */
  604.  
  605. /*            ----  PATH CREATION UTILITIES  ---- */
  606.  
  607.  
  608. /*    
  609.  *        index-innerjoin
  610.  *    
  611.  *        Creates index path nodes corresponding to paths to be used as inner
  612.  *        relations in nestloop joins.
  613.  *    
  614.  *        'clausegroup-list' is a list of list of clauseinfo nodes which can use
  615.  *        'index' on their inner relation.
  616.  *    
  617.  *        Returns a list of index pathnodes.
  618.  *    
  619.  */
  620.  
  621. /*  .. find-index-paths         */
  622.  
  623. LispValue
  624. index_innerjoin (rel,clausegroup_list,index)
  625.      Rel    rel;
  626.      List     clausegroup_list;
  627.      Rel     index ;
  628. {
  629.      LispValue clausegroup = LispNil;
  630.      LispValue cg_list = LispNil;
  631.      LispValue i = LispNil;
  632.      LispValue relattvals = LispNil;
  633.      List pagesel = LispNil;
  634.      IndexPath pathnode = (IndexPath)NULL;
  635.      Cost      temp_selec;
  636.      Count    temp_pages;
  637.  
  638.      foreach(i,clausegroup_list) {
  639.      clausegroup = CAR(i);
  640.      pathnode = RMakeIndexPath();
  641.      relattvals =                
  642.        get_joinvars (CAR(get_relids(rel)),clausegroup);
  643.      pagesel = 
  644.        index_selectivity (CInteger(CAR(get_relids (index))),
  645.                   get_classlist (index),
  646.                   get_opnos (clausegroup),
  647.                   CInteger(getrelid (CInteger(CAR
  648.                               (get_relids (rel))),
  649.                          _query_range_table_)),
  650.                   CAR (relattvals),
  651.                   CADR (relattvals),
  652.                   CADDR (relattvals),
  653.                   length (clausegroup));
  654.       
  655.      set_pathtype((Path)pathnode,T_IndexScan);
  656.      set_parent((Path)pathnode,rel);
  657.      set_indexid(pathnode,get_relids (index));
  658.      set_indexqual(pathnode,clausegroup);
  659.      set_joinid((Path)pathnode,get_cinfojoinid((CInfo)CAR(clausegroup)));
  660.  
  661.      temp_pages = (int)CDouble(CAR(pagesel));
  662.      temp_selec = CDouble(CADR(pagesel));
  663.  
  664.      set_path_cost ((Path)pathnode,cost_index(
  665.                     (ObjectId)CInteger(CAR(get_relids (index))),
  666.                     temp_pages,
  667.                     temp_selec,
  668.                     get_pages (rel),
  669.                     get_tuples (rel),
  670.                     get_pages (index),
  671.                     get_tuples (index), true));
  672.  
  673.      /* copy clauseinfo list into path for expensive function processing 
  674.         -- JMH, 7/7/92 */
  675.      set_locclauseinfo(pathnode,
  676.                set_difference(CopyObject(get_clauseinfo(rel)),
  677.                       clausegroup /*,
  678.                       LispNil (arg too much - kai) */));
  679.  
  680.      /* add in cost for expensive functions!  -- JMH, 7/7/92 */
  681.      set_path_cost((Path)pathnode, get_path_cost((Path)pathnode) + 
  682.                xfunc_get_path_cost(pathnode));
  683.  
  684.      cg_list = nappend1(cg_list,(LispValue)pathnode);
  685.      }
  686.      return(cg_list);
  687.  }  /*  function end */
  688.  
  689. /*    
  690.  *        create-index-paths
  691.  *    
  692.  *        Creates a list of index path nodes for each group of clauses
  693.  *        (restriction or join) that can be used in conjunction with an index.
  694.  *    
  695.  *        'rel' is the relation for which 'index' is defined
  696.  *        'clausegroup-list' is the list of clause groups (lists of clauseinfo 
  697.  *            nodes) grouped by mergesortorder
  698.  *        'join' is a flag indicating whether or not the clauses are join
  699.  *            clauses
  700.  *    
  701.  *        Returns a list of new index path nodes.
  702.  *    
  703.  */
  704.  
  705. /*  .. find-index-paths     */
  706.  
  707. LispValue
  708. create_index_paths (rel,index,clausegroup_list,join)
  709.      Rel rel, index;
  710.      LispValue clausegroup_list;
  711.      bool join;
  712. {
  713.      /* XXX Mapcan  */
  714.      LispValue clausegroup = LispNil;
  715.      LispValue ip_list = LispNil;
  716.      LispValue temp = LispTrue;
  717.      LispValue i = LispNil;
  718.      LispValue j = LispNil;
  719.      IndexPath  temp_path;
  720.  
  721.      foreach(i,clausegroup_list) {
  722.      CInfo clauseinfo;
  723.      LispValue temp_node = LispNil;
  724.      bool temp = true;
  725.  
  726.      clausegroup = CAR(i);
  727.  
  728.      foreach (j,clausegroup) {
  729.          clauseinfo = (CInfo)CAR(j); 
  730.          if ( !(join_clause_p(get_clause(clauseinfo))
  731.             && equal_path_merge_ordering
  732.             ( get_ordering(index),
  733.              get_mergesortorder (clauseinfo)))) {
  734.          temp = false;
  735.          }
  736.      }
  737.       
  738.      if ( !join  || temp ) {  /* restriction, ordering scan */
  739.          temp_path = create_index_path (rel,index,clausegroup,join);
  740.          temp_node = 
  741.            lispCons ((LispValue)temp_path,
  742.             LispNil);
  743.          ip_list = nconc(ip_list,temp_node);
  744.       } 
  745.       }
  746.      return(ip_list);
  747. }  /* function end */
  748.  
  749. bool
  750. indexpath_useless(p, plist)
  751. IndexPath p;
  752. List plist;
  753. {
  754.     LispValue x;
  755.     IndexPath path;
  756.     List qual;
  757.  
  758.     if (get_indexqual(p)) return false;
  759.     foreach (x, plist) {
  760.     path = (IndexPath)CAR(x);
  761.     qual = get_indexqual(path);
  762.     set_indexqual(path, LispNil);
  763.     if (equal((Node)p, (Node)path)) {
  764.         set_indexqual(path, qual);
  765.         return true;
  766.       }
  767.         set_indexqual(path, qual);
  768.       }
  769.     return false;
  770. }
  771.  
  772. List
  773. add_index_paths(indexpaths, new_indexpaths)
  774. List indexpaths, new_indexpaths;
  775. {
  776.     LispValue x;
  777.     IndexPath path;
  778.     List retlist;
  779.     extern int testFlag;
  780.  
  781.     if (!testFlag)
  782.     return append(indexpaths, new_indexpaths);
  783.     retlist = indexpaths;
  784.     foreach (x, new_indexpaths) {
  785.     path = (IndexPath)CAR(x);
  786.     if (!indexpath_useless(path, retlist))
  787.         retlist = nappend1(retlist, (LispValue)path);
  788.       }
  789.     return retlist;
  790. }
  791.  
  792. bool
  793. function_index_operand(funcOpnd, rel, index)
  794.     LispValue funcOpnd;
  795.     Rel rel;
  796.     Rel index;
  797. {
  798.     ObjectId heapRelid    = CInteger(CAR(get_relids(rel)));
  799.     Func function     = (Func)get_function(funcOpnd);
  800.     LispValue funcargs    = get_funcargs(funcOpnd);
  801.     LispValue indexKeys    = get_indexkeys(index);
  802.     LispValue arg;
  803.  
  804.     /*
  805.      * sanity check, make sure we know what we're dealing with here.
  806.      */
  807.     if ( !((consp(funcOpnd) && function) && IsA(function,Func)) )
  808.     return false;
  809.  
  810.     if (get_funcid(function) != get_indproc(index))
  811.     return false;
  812.  
  813.     /*
  814.      * Check that the arguments correspond to the same arguments used
  815.      * to create the functional index.  To do this we must check that
  816.      * 1. refer to the right relatiion. 
  817.      * 2. the args have the right attr. numbers in the right order.
  818.      *
  819.      *
  820.      * Check all args refer to the correct relation (i.e. the one with
  821.      * the functional index defined on it (rel).  To do this we can
  822.      * simply compare range table entry numbers, they must be the same.
  823.      */
  824.     foreach (arg, funcargs) 
  825.     {
  826.     if (heapRelid != get_varno((Var)CAR(arg)))
  827.         return false;
  828.     }
  829.  
  830.     /*
  831.      * check attr numbers and order.
  832.      */
  833.     foreach (arg, funcargs) 
  834.     {
  835.     int curKey;
  836.  
  837.     if (indexKeys == LispNil)
  838.         return (false);
  839.  
  840.     curKey = CInteger(CAR(indexKeys));
  841.     indexKeys = CDR (indexKeys);
  842.     if (get_varattno((Var)CAR(arg)) != curKey)
  843.         return (false);
  844.     }
  845.  
  846.     /*
  847.      * We have passed all the tests.
  848.      */
  849.     return true;
  850. }
  851.  
  852. bool
  853. SingleAttributeIndex(index)
  854.     Rel index;
  855. {
  856.     /*
  857.      * Non-functional indices.
  858.      */
  859.  
  860.     /*
  861.      * return false for now as I don't know if we support index scans
  862.      * on disjunction and the code doesn't work
  863.      */
  864.     return (false);
  865.  
  866. #if 0
  867.     if (index->indproc == InvalidObjectId)
  868.     {
  869.     switch (length(get_indexkeys(index)))
  870.     {
  871.         case 0:  return false;
  872.         case 1:  return true;
  873.  
  874.         /*
  875.          * The list of index keys currently always has 8 elements.
  876.          * It is a SingleAttributeIndex if the second element on
  877.          * are invalid. It suffices to just check the 2nd -mer Oct 21 1991
  878.          */
  879.         default: return (CInteger(CADR(get_indexkeys(index))) == 
  880.                                 InvalidObjectId);
  881.     }
  882.     }
  883.  
  884.     /*
  885.      * We have a functional index which is a single attr index
  886.      */
  887.     return true;
  888. #endif
  889. }
  890.