home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / planner / plan / planner.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  14.5 KB  |  578 lines
  1. /*
  2.  *      FILE
  3.  *         planner
  4.  *     
  5.  *      DESCRIPTION
  6.  *         The query optimizer external interface.
  7.  *     
  8.  */
  9.  
  10. /* RcsId ("$Header: /private/postgres/src/planner/plan/RCS/planner.c,v 1.32 1992/08/10 21:44:13 mer Exp $");  */
  11.  
  12. /*     
  13.  *      EXPORTS
  14.  *             planner
  15.  */
  16.  
  17. #include "tmp/c.h"
  18.  
  19. #include "nodes/pg_lisp.h"
  20. #include "nodes/relation.h"
  21. #include "nodes/relation.a.h"
  22.  
  23. #include "parser/parse.h"
  24.  
  25. #include "planner/internal.h"
  26. #include "planner/planner.h"
  27.  
  28. #include "catalog/pg_type.h"    /* for pg_checkretval() */
  29.  
  30. #include "utils/log.h"
  31.  
  32. /* ----------------
  33.  *    Existential creator declaration
  34.  * ----------------
  35.  */
  36. extern Existential RMakeExistential();
  37.  
  38. /*    
  39.  *        *** Module loading ***
  40.  *    
  41.  */
  42.  
  43. #include "planner/cfi.h"   
  44. /*   C function interface routines */
  45. /* #include "pppp.h" */
  46. /*   POSTGRES plan pretty printer */
  47.  
  48. /* #include "storeplan.h" */
  49.  
  50. /*   plan i/o routines */
  51.  
  52. /*    
  53.  *        PLANNER INITIALIZATION
  54.  *    
  55.  */
  56.  
  57. /*     ...Query tree preprocessing
  58.  */
  59. #include "planner/prepqual.h"
  60.  
  61. /*   for rule queries */
  62. #include "planner/preptlist.h"
  63.  
  64. /*   normal targetlist preprocessing */
  65. #include "planner/prepunion.h"
  66.  
  67. /*   for union (archive, inheritance, ...) queries */
  68.  
  69. /*    
  70.  *        PLAN CREATION
  71.  *    
  72.  */
  73.  
  74. /*     ...Planner driver routines
  75.  */
  76. #include "planner/planmain.h"
  77.  
  78. /*     ...Subplanner initialization
  79.  */
  80. #include "planner/initsplan.h"
  81.  
  82. /*     ...Query plan generation
  83.  */
  84. #include "planner/createplan.h"
  85.  
  86. /*   routines to create optimal subplan */
  87. #include "planner/setrefs.h"
  88.  
  89. /*   routines to set vars to reference other nodes */
  90. /* #include "planner/sortresult.h" */
  91.  
  92. /*   routines to manipulate sort keys */
  93.  
  94. /*    
  95.  *        SUBPLAN GENERATION
  96.  *    
  97.  */
  98. #include "planner/allpaths.h"
  99.  
  100. /*   main routines to generate subplans */
  101. #include "planner/indxpath.h"
  102.  
  103. /*   main routines to generate index paths */
  104. #include "planner/orindxpath.h"
  105. #include "planner/prune.h" 
  106.  
  107. /*   routines to prune the path space */
  108. #include "planner/joinpath.h"
  109.  
  110. /*   main routines to create join paths */
  111. #include "planner/joinrels.h"
  112.  
  113. /*   routines to determine which relations to join */
  114. #include "planner/joinutils.h"
  115.  
  116. /*   generic join method key/clause routines */
  117. #include "planner/mergeutils.h"
  118.  
  119. /*   routines to deal with merge keys and clauses */
  120. #include "planner/hashutils.h"
  121.  
  122. /*   routines to deal with hash keys and clauses */
  123.  
  124. /*    
  125.  *        SUBPLAN SELECTION - utilities for planner, create-plan, join routines
  126.  *    
  127.  */
  128. #include "planner/clausesel.h"
  129.  
  130. /*   routines to compute clause selectivities */
  131. #include "planner/costsize.h"
  132.  
  133. /*   routines to compute costs and sizes */
  134.  
  135. /*    
  136.  *        DATA STRUCTURE CREATION/MANIPULATION ROUTINES
  137.  *    
  138.  */
  139. #include "nodes/relation.h"
  140. #include "planner/clauseinfo.h"
  141. #include "planner/indexnode.h"
  142. #include "planner/joininfo.h"
  143. #include "planner/keys.h"
  144. #include "planner/ordering.h"
  145. #include "planner/pathnode.h"
  146. #include "planner/clause.h"
  147. #include "planner/relnode.h"
  148. #include "planner/tlist.h"
  149. #include "planner/var.h"
  150.  
  151. extern bool DebugPrintPlan;
  152.  
  153. /*    
  154.  *        *** Query optimizer entry point ***
  155.  *    
  156.  */
  157.  
  158. /*    
  159.  *        planner
  160.  *    
  161.  *        Main query optimizer routine.
  162.  *    
  163.  *        Invokes the planner on union queries if there are any left,
  164.  *        recursing if necessary to get them all, then processes normal plans.
  165.  *    
  166.  *        Returns a query plan.
  167.  *    
  168.  */
  169.  
  170. /*  .. make-rule-plans, plan-union-query, process-rules    */
  171.  
  172. Plan
  173. planner (parse)
  174.      LispValue parse ;
  175. {
  176.     LispValue root = parse_root (parse);
  177.     LispValue tlist = parse_targetlist (parse);
  178.     LispValue qual = parse_qualification (parse);
  179.     LispValue rangetable = root_rangetable (root);
  180.     LispValue commandType = root_command_type_atom (root);
  181.     LispValue uniqueflag = root_uniqueflag(root);
  182.     LispValue sortclause = root_sortclause(root);
  183.     LispValue sortkeys = LispNil;
  184.     LispValue sortops = LispNil;
  185.     Plan special_plans = (Plan)NULL;
  186.     Plan regular_plans = (Plan)NULL;
  187.     LispValue flag = LispNil;
  188.     List plan_list = LispNil;
  189.  
  190.     plan_list = lispCons(lispAtom("inherits"),
  191.            lispCons(lispAtom("union"),
  192.                 lispCons(lispAtom("archive"),LispNil)));
  193.     foreach (flag,plan_list) {
  194.     Index rt_index = first_matching_rt_entry (rangetable,CAR(flag));
  195.     if ( rt_index != -1 )
  196.       special_plans = (Plan)plan_union_queries (rt_index,
  197.                             CAtom(CAR(flag)),
  198.                             root,
  199.                             tlist,
  200.                             qual,rangetable);
  201.     }
  202.  
  203.     /*
  204.      *  For now, before we hand back the plan, check to see if there
  205.      *  is a user-specified sort that needs to be done.  Eventually, this 
  206.      *  will be moved into the guts of the planner s.t. user specified 
  207.      *  sorts will be considered as part of the planning process. 
  208.      *  Since we can only make use of user-specified sorts in
  209.      *  special cases, we can do the optimization step later.
  210.      *   
  211.      *  sortkeys:    a list of resdom nodes corresponding to the attributes in
  212.      *               the tlist that are to be sorted.
  213.      *  sortops:     a corresponding list of sort operators.               
  214.      */
  215.  
  216.     if (uniqueflag || sortclause) {
  217.     sortkeys = CADR(sortclause);
  218.     sortops = CADDR(sortclause);
  219.     }
  220.  
  221.     if (special_plans) {
  222.     if (uniqueflag) {
  223.         Plan sortplan = make_sortplan(tlist,sortkeys,
  224.                       sortops,special_plans);
  225.         return((Plan)make_unique(tlist,sortplan));
  226.     }
  227.     else 
  228.       if (sortclause) 
  229.           return(make_sortplan(tlist,sortkeys,sortops,special_plans));
  230.       else 
  231.         return((Plan)special_plans);
  232.     }
  233.     else {  
  234.     regular_plans = init_query_planner(root,tlist,qual);
  235.     
  236.     if (uniqueflag) {
  237.         Plan sortplan = make_sortplan(tlist,sortkeys,
  238.                       sortops,regular_plans);
  239.         return((Plan)make_unique(tlist,sortplan));
  240.     }
  241.     else
  242.       if (sortclause)
  243.         return(make_sortplan(tlist,sortkeys,sortops,regular_plans)); 
  244.       else
  245.         return(regular_plans);
  246.     }
  247.     
  248. } /* function end  */
  249.  
  250. /*
  251.  *      make_sortplan
  252.  *   
  253.  *      Returns a sortplan which is basically a SORT node attached to the
  254.  *      top of the plan returned from the planner.  It also adds the 
  255.  *      cost of sorting into the plan.
  256.  *      
  257.  *      sortkeys: ( resdom1 resdom2 resdom3 ...)
  258.  *      sortops:  (sortop1 sortop2 sortop3 ...)
  259.  */
  260.  
  261. Plan
  262. make_sortplan(tlist,sortkeys,sortops,plannode)
  263.      List tlist;
  264.      List sortkeys;
  265.      List sortops;
  266.      Plan plannode;
  267.  
  268. {
  269.   Plan sortplan = (Plan)NULL;
  270.   List temp_tlist = LispNil;
  271.   LispValue i = LispNil;
  272.   Resdom resnode = (Resdom)NULL;
  273.   Resdom resdom = (Resdom)NULL;
  274.   int keyno =1;
  275.  
  276.   /*  First make a copy of the tlist so that we don't corrupt the 
  277.    *  the original .
  278.    */
  279.   
  280.   temp_tlist = new_unsorted_tlist(tlist);
  281.   
  282.   foreach (i, sortkeys) {
  283.       
  284.       resnode = (Resdom)CAR(i);
  285.       resdom = tlist_resdom(temp_tlist,resnode);
  286.  
  287.       /*    Order the resdom keys and replace the operator OID for each 
  288.        *    key with the regproc OID. 
  289.        */
  290.       
  291.       set_reskey (resdom,keyno);
  292.       set_reskeyop (resdom,(OperatorTupleForm)get_opcode (CInteger(CAR(sortops))));      
  293.  
  294.       keyno += 1;
  295.       sortops = CDR(sortops);
  296.   }
  297.  
  298.   sortplan = (Plan) make_sort(temp_tlist,
  299.                   _TEMP_RELATION_ID_,
  300.                   (Plan)plannode,
  301.                   length(sortkeys));
  302.  
  303.   /*
  304.    *  XXX Assuming that an internal sort has no. cost. 
  305.    *      This is wrong, but given that at this point, we don't
  306.    *      know the no. of tuples returned, etc, we can't do
  307.    *      better than to add a constant cost.
  308.    *      This will be fixed once we move the sort further into the planner,
  309.    *      but for now ... functionality....
  310.    */
  311.  
  312.   set_cost(sortplan, get_cost(plannode));
  313.   
  314.   return(sortplan);
  315. }
  316.  
  317.  
  318. /*    
  319.  *        init-query-planner
  320.  *    
  321.  *        Deals with all non-union preprocessing, including existential
  322.  *        qualifications and CNFifying the qualifications.
  323.  *    
  324.  *        Returns a query plan.
  325.  *    MODIFIES: tlist,qual
  326.  *    
  327.  */
  328.  
  329. /*  .. plan-union-queries, planner    */
  330.  
  331. Plan
  332. init_query_planner (root,tlist,qual)
  333.      LispValue root,tlist,qual ;
  334. {
  335.      LispValue primary_qual;
  336.      LispValue existential_qual;
  337.      Existential exist_plan;
  338.  
  339.      _query_max_level_ = root_numlevels (root);
  340.      _query_command_type_ = (int) root_command_type (root);
  341.      _query_result_relation_ = root_result_relation (root);
  342.      _query_range_table_ = root_rangetable (root);
  343.      
  344.      tlist = preprocess_targetlist (tlist,
  345.                     _query_command_type_,
  346.                     _query_result_relation_,
  347.                     _query_range_table_);
  348.  
  349.      qual = preprocess_qualification (qual,tlist);
  350.  
  351.      if ( DebugPrintPlan ) {
  352.      printf("after preprocessing, qual is :\n");
  353.      lispDisplay(qual);
  354.      printf("\n");
  355.      fflush(stdout);
  356.      }
  357.  
  358.      if (qual) {
  359.      primary_qual = CAR(qual);
  360.      existential_qual = CADR(qual);
  361.      } else {
  362.      primary_qual = LispNil;
  363.      existential_qual = LispNil;
  364.      }
  365.  
  366.      if(lispNullp (existential_qual)) {
  367.      return(query_planner(_query_command_type_,
  368.                   tlist,
  369.                   primary_qual,
  370.                   1,_query_max_level_));
  371.  
  372.      } else {
  373.  
  374.      char *globals;
  375.      int temp = _query_command_type_;
  376.      Plan existential_plan;
  377.  
  378.      /* with saved globals */
  379.      globals = save_globals();
  380.  
  381.      _query_command_type_ = RETRIEVE;
  382.      existential_plan = query_planner(temp,LispNil,existential_qual,1,
  383.                       _query_max_level_);
  384.      
  385.      exist_plan = make_existential (existential_plan,
  386.                     query_planner (_query_command_type_,
  387.                                tlist,primary_qual,
  388.                                1,
  389.                                _query_max_level_));
  390.  
  391.      restore_globals(globals);
  392.      return((Plan)exist_plan);
  393. }
  394.  
  395.  }  /* function end  */
  396.  
  397. /* 
  398.  *     make_existential
  399.  *    ( NB: no corresponding lisp code )
  400.  *
  401.  *    Instantiates an existential plan node and fills in 
  402.  *    the left and right subtree slots.
  403.  */
  404.  
  405. Existential
  406. make_existential(left,right)
  407.      Plan left,right;
  408. {
  409.     Existential node = RMakeExistential();
  410.  
  411.     set_lefttree(node,(PlanPtr)left);
  412.     set_righttree(node,(PlanPtr)right);
  413.     return(node);
  414. }
  415.  
  416. /*
  417.  *  pg_checkretval() -- check return value of a list of postquel parse
  418.  *            trees.
  419.  *
  420.  *    The return value of a postquel function is the value returned by
  421.  *    the final query in the function.  We do some ad-hoc define-time
  422.  *    type checking here to be sure that the user is returning the
  423.  *    type he claims.
  424.  */
  425.  
  426. void
  427. pg_checkretval(rettype, parselist)
  428.     ObjectId rettype;
  429.     List parselist;
  430. {
  431.     LispValue parse;
  432.     LispValue tlist;
  433.     LispValue tle;
  434.     LispValue root;
  435.     LispValue rt;
  436.     LispValue rte;
  437.     int cmd;
  438.     char *typ;
  439.     Resdom resnode;
  440.     LispValue thenode;
  441.     Relation reln;
  442.     ObjectId relid;
  443.     ObjectId tletype;
  444.     int relnatts;
  445.     int i;
  446.  
  447.     /* find the final query */
  448.     while (CDR(parselist) != LispNil)
  449.     parselist = CDR(parselist);
  450.  
  451.     parse = CAR(parselist);
  452.  
  453.     /*
  454.      *  test 1:  if the last query is a utility invocation, then there
  455.      *  had better not be a return value declared.
  456.      */
  457.  
  458.     if (atom(CAR(parse))) {
  459.     if (rettype == InvalidObjectId)
  460.         return;
  461.     else
  462.         elog(WARN, "return type mismatch in function decl: final query is a catalog utility");
  463.     }
  464.  
  465.     /* okay, it's an ordinary query */
  466.     root = parse_root(parse);
  467.     tlist = parse_targetlist(parse);
  468.     rt = root_rangetable(root);
  469.     cmd = (int) root_command_type(root);
  470.  
  471.     /*
  472.      *  test 2:  if the function is declared to return no value, then the
  473.      *  final query had better not be a retrieve.
  474.      */
  475.  
  476.     if (rettype == InvalidObjectId) {
  477.     if (cmd == RETRIEVE)
  478.         elog(WARN, "function declared with no return type, but final query is a retrieve");
  479.     else
  480.         return;
  481.     }
  482.  
  483.     /* by here, the function is declared to return some type */
  484.     if ((typ = (char *) get_id_type(rettype)) == (char *) NULL)
  485.     elog(WARN, "can't find return type %d for function\n", rettype);
  486.  
  487.     /*
  488.      *  test 3:  if the function is declared to return a value, then the
  489.      *  final query had better be a retrieve.
  490.      */
  491.  
  492.     if (cmd != RETRIEVE)
  493.     elog(WARN, "function declared to return type %s, but final query is not a retrieve", tname(typ));
  494.  
  495.     /*
  496.      *  test 4:  for base type returns, the target list should have exactly
  497.      *  one entry, and its type should agree with what the user declared.
  498.      */
  499.  
  500.     if (get_typrelid(typ) == InvalidObjectId) {
  501.     if (ExecTargetListLength(tlist) > 1)
  502.         elog(WARN, "function declared to return %s returns multiple values in final retrieve", tname(typ));
  503.  
  504.     resnode = (Resdom) CAR(CAR(tlist));
  505.     if (get_restype(resnode) != rettype)
  506.         elog(WARN, "return type mismatch in function: declared to return %s, returns %s", tname(typ), tname(get_id_type(get_restype(resnode))));
  507.  
  508.     /* by here, base return types match */
  509.     return;
  510.     }
  511.  
  512.     /*
  513.      *  If the target list is of length 1, and the type of the varnode
  514.      *  in the target list is the same as the declared return type, this
  515.      *  is okay.  This can happen, for example, where the body of the
  516.      *  function is 'retrieve (x = func2())', where func2 has the same
  517.      *  return type as the function that's calling it.
  518.      */
  519.  
  520.     if (ExecTargetListLength(tlist) == 1) {
  521.     resnode = (Resdom) CAR(CAR(tlist));
  522.     if (get_restype(resnode) == rettype)
  523.         return;
  524.     }
  525.  
  526.     /*
  527.      *  By here, the procedure returns a (set of) tuples.  This part of
  528.      *  the typechecking is a hack.  We look up the relation that is
  529.      *  the declared return type, and be sure that attributes 1 .. n
  530.      *  in the target list match the declared types.
  531.      */
  532.  
  533.     reln = heap_open(get_typrelid(typ));
  534.  
  535.     if (!RelationIsValid(reln))
  536.     elog(WARN, "cannot open relation relid %d", get_typrelid(typ));
  537.  
  538.     relid = reln->rd_id;
  539.     relnatts = reln->rd_rel->relnatts;
  540.  
  541.     if (ExecTargetListLength(tlist) != relnatts)
  542.     elog(WARN, "function declared to return type %s does not retrieve (%s.all)", tname(typ), tname(typ));
  543.  
  544.     /* expect attributes 1 .. n in order */
  545.     for (i = 1; i <= relnatts; i++) {
  546.     tle = CAR(tlist);
  547.     tlist = CDR(tlist);
  548.     thenode = CADR(tle);
  549.  
  550.     /* this is tedious */
  551.     if (IsA(thenode,Var))
  552.         tletype = (ObjectId) get_vartype((Var)thenode);
  553.     else if (IsA(thenode,Const))
  554.         tletype = (ObjectId) get_consttype((Const)thenode);
  555.     else if (IsA(thenode,Param))
  556.         tletype = (ObjectId) get_paramtype((Param)thenode);
  557.     else if (IsA(thenode,LispList)) {
  558.         thenode = CAR(thenode);
  559.         if (IsA(thenode,Oper))
  560.         tletype = (ObjectId) get_opresulttype((Oper)thenode);
  561.         else if (IsA(thenode,Func))
  562.         tletype = (ObjectId) get_functype((Func)thenode);
  563.         else
  564.         elog(WARN, "function declared to return type %s does not retrieve (%s.all)", tname(typ), tname(typ));
  565.     } else
  566.         elog(WARN, "function declared to return type %s does not retrieve (%s.all)", tname(typ), tname(typ));
  567.  
  568.     /* reach right in there, why don't you? */
  569.     if (tletype != reln->rd_att.data[i-1]->atttypid)
  570.         elog(WARN, "function declared to return type %s does not retrieve (%s.all)", tname(typ), tname(typ));
  571.     }
  572.  
  573.     heap_close(reln);
  574.  
  575.     /* success */
  576.     return;
  577. }
  578.