开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数据库系统 > 查看源码
pathnode.c
资源名称：postgresql-6.5.2.tar.gz　[点击查看]
上传用户：blenddy
上传日期：2007-01-07
资源大小：6495k
文件大小：18k
源码类别：

数据库系统

开发平台：

Unix_Linux

pathnode.c：源码内容
  1. /*-------------------------------------------------------------------------
  2.  *
  3.  * pathnode.c
  4.  *   Routines to manipulate pathlists and create path nodes
  5.  *
  6.  * Copyright (c) 1994, Regents of the University of California
  7.  *
  8.  *
  9.  * IDENTIFICATION
  10.  *   $Header: /usr/local/cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.42.2.1 1999/08/02 06:27:08 scrappy Exp $
  11.  *
  12.  *-------------------------------------------------------------------------
  13.  */
  14. #include <math.h>
  16. #include "postgres.h"
  18. #include "optimizer/cost.h"
  19. #include "optimizer/keys.h"
  20. #include "optimizer/ordering.h"
  21. #include "optimizer/pathnode.h"
  22. #include "optimizer/paths.h"
  23. #include "optimizer/plancat.h"
  24. #include "optimizer/restrictinfo.h"
  25. #include "parser/parsetree.h"
  27. static Path *better_path(Path *new_path, List *unique_paths, bool *is_new);
  30. /*****************************************************************************
  31.  * MISC. PATH UTILITIES
  32.  *****************************************************************************/
  34. /*
  35.  * path_is_cheaper
  36.  *   Returns t iff 'path1' is cheaper than 'path2'.
  37.  *
  38.  */
  39. bool
  40. path_is_cheaper(Path *path1, Path *path2)
  41. {
  42. Cost cost1 = path1->path_cost;
  43. Cost cost2 = path2->path_cost;
  45. return (bool) (cost1 < cost2);
  46. }
  48. /*
  49.  * set_cheapest
  50.  *   Finds the minimum cost path from among a relation's paths.
  51.  *
  52.  * 'parent_rel' is the parent relation
  53.  * 'pathlist' is a list of path nodes corresponding to 'parent_rel'
  54.  *
  55.  * Returns and sets the relation entry field with the pathnode that
  56.  * is minimum.
  57.  *
  58.  */
  59. Path *
  60. set_cheapest(RelOptInfo *parent_rel, List *pathlist)
  61. {
  62. List    *p;
  63. Path    *cheapest_so_far;
  65. Assert(pathlist != NIL);
  66. Assert(IsA(parent_rel, RelOptInfo));
  68. cheapest_so_far = (Path *) lfirst(pathlist);
  70. foreach(p, lnext(pathlist))
  71. {
  72. Path    *path = (Path *) lfirst(p);
  74. if (path_is_cheaper(path, cheapest_so_far))
  75. cheapest_so_far = path;
  76. }
  78. parent_rel->cheapestpath = cheapest_so_far;
  80. return cheapest_so_far;
  81. }
  83. /*
  84.  * add_pathlist
  85.  *   For each path in the list 'new_paths', add to the list 'unique_paths'
  86.  *   only those paths that are unique (i.e., unique ordering and ordering
  87.  *   keys).  Should a conflict arise, the more expensive path is thrown out,
  88.  *   thereby pruning the plan space.  But we don't prune if xfunc
  89.  *   told us not to.
  90.  *
  91.  * 'parent_rel' is the relation entry to which these paths correspond.
  92.  *
  93.  * Returns the list of unique pathnodes.
  94.  *
  95.  */
  96. List *
  97. add_pathlist(RelOptInfo *parent_rel, List *unique_paths, List *new_paths)
  98. {
  99. List    *p1;
  101. foreach(p1, new_paths)
  102. {
  103. Path    *new_path = (Path *) lfirst(p1);
  104. Path    *old_path;
  105. bool is_new;
  107. /* Is this new path already in unique_paths? */
  108. if (member(new_path, unique_paths))
  109. continue;
  111. /* Find best matching path */
  112. old_path = better_path(new_path, unique_paths, &is_new);
  114. if (is_new)
  115. {
  116. /* This is a brand new path.  */
  117. new_path->parent = parent_rel;
  118. unique_paths = lcons(new_path, unique_paths);
  119. }
  120. else if (old_path == NULL)
  121. {
  122. ; /* do nothing if path is not cheaper */
  123. }
  124. else if (old_path != NULL)
  125. { /* (IsA(old_path,Path)) { */
  126. new_path->parent = parent_rel;
  127. if (!parent_rel->pruneable)
  128. unique_paths = lcons(new_path, unique_paths);
  129. else
  130. unique_paths = lcons(new_path,
  131.  LispRemove(old_path, unique_paths));
  132. }
  133. }
  134. return unique_paths;
  135. }
  137. /*
  138.  * better_path
  139.  *   Determines whether 'new_path' has the same ordering and keys as some
  140.  *   path in the list 'unique_paths'. If there is a redundant path,
  141.  *   eliminate the more expensive path.
  142.  *
  143.  * Returns:
  144.  *   The old path - if 'new_path' matches some path in 'unique_paths' and is
  145.  * cheaper
  146.  *   nil - if 'new_path' matches but isn't cheaper
  147.  *   t - if there is no path in the list with the same ordering and keys
  148.  *
  149.  */
  150. static Path *
  151. better_path(Path *new_path, List *unique_paths, bool *is_new)
  152. {
  153. Path    *path = (Path *) NULL;
  154. List    *temp = NIL;
  155. int better_key;
  156. int better_sort;
  158. #ifdef OPTDUP_DEBUG
  159. printf("better_path entryn");
  160. printf("newn");
  161. pprint(new_path);
  162. printf("unique_pathsn");
  163. pprint(unique_paths);
  164. #endif
  166. foreach(temp, unique_paths)
  167. {
  168. path = (Path *) lfirst(temp);
  170. #ifdef OPTDUP_DEBUG
  171. if (!pathkeys_match(new_path->pathkeys, path->pathkeys, &better_key) ||
  172. better_key != 0)
  173. {
  174. printf("betterkey = %dn", better_key);
  175. printf("newpathn");
  176. pprint(new_path->pathkeys);
  177. printf("oldpathn");
  178. pprint(path->pathkeys);
  179. if (path->pathkeys && new_path->pathkeys &&
  180. length(lfirst(path->pathkeys)) >= 2 /* &&
  181.  * length(lfirst(path->pa
  182.  * thkeys)) <
  183.  * length(lfirst(new_path
  184. ->pathkeys)) */ )
  185. sleep(0); /* set breakpoint here */
  186. }
  187. if (!pathorder_match(new_path->pathorder, path->pathorder,
  188.  &better_sort) ||
  189. better_sort != 0)
  190. {
  191. printf("newordn");
  192. pprint(new_path->pathorder);
  193. printf("oldordn");
  194. pprint(path->pathorder);
  195. }
  196. #endif
  198. if (pathkeys_match(new_path->pathkeys, path->pathkeys,
  199.    &better_key) &&
  200. pathorder_match(new_path->pathorder, path->pathorder,
  201. &better_sort))
  202. {
  204. /*
  205.  * Replace pathkeys that match exactly, {{1,2}}, {{1,2}}
  206.  * Replace pathkeys {{1,2}} with {{1,2,3}}} if the latter is
  207.  * not more expensive and replace unordered path with ordered
  208.  * path if it is not more expensive.  Favor sorted keys over
  209.  * unsorted keys in the same way.
  210.  */
  211. /* same keys, and new is cheaper, use it */
  212. if ((better_key == 0 && better_sort == 0 &&
  213.  new_path->path_cost < path->path_cost) ||
  215. /* new is better, and cheaper, use it */
  216. (((better_key == 1 && better_sort != 2) ||
  217.   (better_key != 2 && better_sort == 1)) &&
  218.  new_path->path_cost <= path->path_cost))
  219. {
  220. #ifdef OPTDUP_DEBUG
  221. printf("replace with new %p old %p better key %d better sort %dn", &new_path, &path, better_key, better_sort);
  222. printf("newn");
  223. pprint(new_path);
  224. printf("oldn");
  225. pprint(path);
  226. #endif
  227. *is_new = false;
  228. return path;
  229. }
  231. /* same keys, new is more expensive, stop */
  232. if ((better_key == 0 && better_sort == 0 &&
  233.  new_path->path_cost >= path->path_cost) ||
  235. /* old is better, and less expensive, stop */
  236. (((better_key == 2 && better_sort != 1) ||
  237.   (better_key != 1 && better_sort == 2)) &&
  238.  new_path->path_cost >= path->path_cost))
  239. {
  240. #ifdef OPTDUP_DEBUG
  241. printf("skip new %p old %p better key %d better sort %dn", &new_path, &path, better_key, better_sort);
  242. printf("newn");
  243. pprint(new_path);
  244. printf("oldn");
  245. pprint(path);
  246. #endif
  247. *is_new = false;
  248. return NULL;
  249. }
  250. }
  251. }
  253. #ifdef OPTDUP_DEBUG
  254. printf("add new %p old %p better key %d better sort %dn", &new_path, &path, better_key, better_sort);
  255. printf("newn");
  256. pprint(new_path);
  257. #endif
  259. *is_new = true;
  260. return NULL;
  261. }
  265. /*****************************************************************************
  266.  * PATH NODE CREATION ROUTINES
  267.  *****************************************************************************/
  269. /*
  270.  * create_seqscan_path
  271.  *   Creates a path corresponding to a sequential scan, returning the
  272.  *   pathnode.
  273.  *
  274.  */
  275. Path *
  276. create_seqscan_path(RelOptInfo *rel)
  277. {
  278. int relid = 0;
  280. Path    *pathnode = makeNode(Path);
  282. pathnode->pathtype = T_SeqScan;
  283. pathnode->parent = rel;
  284. pathnode->path_cost = 0.0;
  285. pathnode->pathorder = makeNode(PathOrder);
  286. pathnode->pathorder->ordtype = SORTOP_ORDER;
  287. pathnode->pathorder->ord.sortop = NULL;
  288. pathnode->pathkeys = NIL;
  290. /*
  291.  * copy restrictinfo list into path for expensive function processing
  292.  * JMH, 7/7/92
  293.  */
  294. pathnode->loc_restrictinfo = (List *) copyObject((Node *) rel->restrictinfo);
  296. if (rel->relids != NULL)
  297. relid = lfirsti(rel->relids);
  299. pathnode->path_cost = cost_seqscan(relid,
  300.    rel->pages, rel->tuples);
  301. /* add in expensive functions cost!  -- JMH, 7/7/92 */
  302. #ifdef NOT_USED
  303. if (XfuncMode != XFUNC_OFF)
  304. pathnode->path_cost += xfunc_get_path_cost(pathnode);
  305. #endif
  306. return pathnode;
  307. }
  309. /*
  310.  * create_index_path
  311.  *   Creates a single path node for an index scan.
  312.  *
  313.  * 'rel' is the parent rel
  314.  * 'index' is the pathnode for the index on 'rel'
  315.  * 'restriction_clauses' is a list of restriction clause nodes.
  316.  * 'is_join_scan' is a flag indicating whether or not the index is being
  317.  * considered because of its sort order.
  318.  *
  319.  * Returns the new path node.
  320.  *
  321.  */
  322. IndexPath  *
  323. create_index_path(Query *root,
  324.   RelOptInfo *rel,
  325.   RelOptInfo *index,
  326.   List *restriction_clauses,
  327.   bool is_join_scan)
  328. {
  329. IndexPath  *pathnode = makeNode(IndexPath);
  331. pathnode->path.pathtype = T_IndexScan;
  332. pathnode->path.parent = rel;
  333. pathnode->path.pathorder = makeNode(PathOrder);
  334. pathnode->path.pathorder->ordtype = SORTOP_ORDER;
  335. pathnode->path.pathorder->ord.sortop = index->ordering;
  337. pathnode->indexid = index->relids;
  338. pathnode->indexkeys = index->indexkeys;
  339. pathnode->indexqual = NIL;
  341. /*
  342.  * copy restrictinfo list into path for expensive function processing
  343.  * JMH, 7/7/92
  344.  */
  345. pathnode->path.loc_restrictinfo = set_difference((List *) copyObject((Node *) rel->restrictinfo),
  346.    (List *) restriction_clauses);
  348. /*
  349.  * The index must have an ordering for the path to have (ordering)
  350.  * keys, and vice versa.
  351.  */
  352. if (pathnode->path.pathorder->ord.sortop)
  353. {
  354. pathnode->path.pathkeys = collect_index_pathkeys(index->indexkeys,
  355.  rel->targetlist);
  357. /*
  358.  * Check that the keys haven't 'disappeared', since they may no
  359.  * longer be in the target list (i.e., index keys that are not
  360.  * relevant to the scan are not applied to the scan path node, so
  361.  * if no index keys were found, we can't order the path).
  362.  */
  363. if (pathnode->path.pathkeys == NULL)
  364. pathnode->path.pathorder->ord.sortop = NULL;
  365. }
  366. else
  367. pathnode->path.pathkeys = NULL;
  369. if (is_join_scan || restriction_clauses == NULL)
  370. {
  372. /*
  373.  * Indices used for joins or sorting result nodes don't restrict
  374.  * the result at all, they simply order it, so compute the scan
  375.  * cost accordingly -- use a selectivity of 1.0.
  376.  */
  377. /* is the statement above really true? what about IndexScan as the
  378.    inner of a join? */
  379. pathnode->path.path_cost = cost_index(lfirsti(index->relids),
  380.   index->pages,
  381.   1.0,
  382.   rel->pages,
  383.   rel->tuples,
  384.   index->pages,
  385.   index->tuples,
  386.   false);
  387. #ifdef NOT_USED
  388. /* add in expensive functions cost!  -- JMH, 7/7/92 */
  389. if (XfuncMode != XFUNC_OFF)
  390. {
  391. pathnode->path_cost = (pathnode->path_cost +
  392.  xfunc_get_path_cost((Path *) pathnode));
  393. }
  394. #endif
  395. }
  396. else
  397. {
  399. /*
  400.  * Compute scan cost for the case when 'index' is used with a
  401.  * restriction clause.
  402.  */
  403. List    *attnos;
  404. List    *values;
  405. List    *flags;
  406. float npages;
  407. float selec;
  408. Cost clausesel;
  410. get_relattvals(restriction_clauses,
  411.    &attnos,
  412.    &values,
  413.    &flags);
  414. index_selectivity(lfirsti(index->relids),
  415.   index->classlist,
  416.   get_opnos(restriction_clauses),
  417.   getrelid(lfirsti(rel->relids),
  418.    root->rtable),
  419.   attnos,
  420.   values,
  421.   flags,
  422.   length(restriction_clauses),
  423.   &npages,
  424.   &selec);
  425. /* each clause gets an equal selectivity */
  426. clausesel = pow(selec, 1.0 / (double) length(restriction_clauses));
  428. pathnode->indexqual = restriction_clauses;
  429. pathnode->path.path_cost = cost_index(lfirsti(index->relids),
  430.   (int) npages,
  431.   selec,
  432.   rel->pages,
  433.   rel->tuples,
  434.   index->pages,
  435.   index->tuples,
  436.   false);
  438. #ifdef NOT_USED
  439. /* add in expensive functions cost!  -- JMH, 7/7/92 */
  440. if (XfuncMode != XFUNC_OFF)
  441. pathnode->path_cost += xfunc_get_path_cost((Path *) pathnode);
  442. #endif
  444. /*
  445.  * Set selectivities of clauses used with index to the selectivity
  446.  * of this index, subdividing the selectivity equally over each of
  447.  * the clauses.
  448.  */
  450. /* XXX Can this divide the selectivities in a better way? */
  451. set_clause_selectivities(restriction_clauses, clausesel);
  452. }
  453. return pathnode;
  454. }
  456. /*
  457.  * create_nestloop_path
  458.  *   Creates a pathnode corresponding to a nestloop join between two
  459.  *   relations.
  460.  *
  461.  * 'joinrel' is the join relation.
  462.  * 'outer_rel' is the outer join relation
  463.  * 'outer_path' is the outer join path.
  464.  * 'inner_path' is the inner join path.
  465.  * 'pathkeys' are the keys of the path
  466.  *
  467.  * Returns the resulting path node.
  468.  *
  469.  */
  470. NestPath   *
  471. create_nestloop_path(RelOptInfo *joinrel,
  472.  RelOptInfo *outer_rel,
  473.  Path *outer_path,
  474.  Path *inner_path,
  475.  List *pathkeys)
  476. {
  477. NestPath   *pathnode = makeNode(NestPath);
  479. pathnode->path.pathtype = T_NestLoop;
  480. pathnode->path.parent = joinrel;
  481. pathnode->outerjoinpath = outer_path;
  482. pathnode->innerjoinpath = inner_path;
  483. pathnode->pathinfo = joinrel->restrictinfo;
  484. pathnode->path.pathkeys = pathkeys;
  485. pathnode->path.joinid = NIL;
  486. pathnode->path.outerjoincost = (Cost) 0.0;
  487. pathnode->path.loc_restrictinfo = NIL;
  488. pathnode->path.pathorder = makeNode(PathOrder);
  490. if (pathkeys)
  491. {
  492. pathnode->path.pathorder->ordtype = outer_path->pathorder->ordtype;
  493. if (outer_path->pathorder->ordtype == SORTOP_ORDER)
  494. pathnode->path.pathorder->ord.sortop = outer_path->pathorder->ord.sortop;
  495. else
  496. pathnode->path.pathorder->ord.merge = outer_path->pathorder->ord.merge;
  497. }
  498. else
  499. {
  500. pathnode->path.pathorder->ordtype = SORTOP_ORDER;
  501. pathnode->path.pathorder->ord.sortop = NULL;
  502. }
  504. pathnode->path.path_cost = cost_nestloop(outer_path->path_cost,
  505.  inner_path->path_cost,
  506.  outer_rel->size,
  507.  inner_path->parent->size,
  508.  page_size(outer_rel->size,
  509.    outer_rel->width),
  510.  IsA(inner_path, IndexPath));
  511. /* add in expensive function costs -- JMH 7/7/92 */
  512. #ifdef NOT_USED
  513. if (XfuncMode != XFUNC_OFF)
  514. pathnode->path_cost += xfunc_get_path_cost((Path *) pathnode);
  515. #endif
  516. return pathnode;
  517. }
  519. /*
  520.  * create_mergejoin_path
  521.  *   Creates a pathnode corresponding to a mergejoin join between
  522.  *   two relations
  523.  *
  524.  * 'joinrel' is the join relation
  525.  * 'outersize' is the number of tuples in the outer relation
  526.  * 'innersize' is the number of tuples in the inner relation
  527.  * 'outerwidth' is the number of bytes per tuple in the outer relation
  528.  * 'innerwidth' is the number of bytes per tuple in the inner relation
  529.  * 'outer_path' is the outer path
  530.  * 'inner_path' is the inner path
  531.  * 'pathkeys' are the new keys of the join relation
  532.  * 'order' is the sort order required for the merge
  533.  * 'mergeclauses' are the applicable join/restriction clauses
  534.  * 'outersortkeys' are the sort varkeys for the outer relation
  535.  * 'innersortkeys' are the sort varkeys for the inner relation
  536.  *
  537.  */
  538. MergePath  *
  539. create_mergejoin_path(RelOptInfo *joinrel,
  540.   int outersize,
  541.   int innersize,
  542.   int outerwidth,
  543.   int innerwidth,
  544.   Path *outer_path,
  545.   Path *inner_path,
  546.   List *pathkeys,
  547.   MergeOrder *order,
  548.   List *mergeclauses,
  549.   List *outersortkeys,
  550.   List *innersortkeys)
  551. {
  552. MergePath  *pathnode = makeNode(MergePath);
  554. pathnode->jpath.path.pathtype = T_MergeJoin;
  555. pathnode->jpath.path.parent = joinrel;
  556. pathnode->jpath.outerjoinpath = outer_path;
  557. pathnode->jpath.innerjoinpath = inner_path;
  558. pathnode->jpath.pathinfo = joinrel->restrictinfo;
  559. pathnode->jpath.path.pathkeys = pathkeys;
  560. pathnode->jpath.path.pathorder = makeNode(PathOrder);
  561. pathnode->jpath.path.pathorder->ordtype = MERGE_ORDER;
  562. pathnode->jpath.path.pathorder->ord.merge = order;
  563. pathnode->path_mergeclauses = mergeclauses;
  564. pathnode->jpath.path.loc_restrictinfo = NIL;
  565. pathnode->outersortkeys = outersortkeys;
  566. pathnode->innersortkeys = innersortkeys;
  567. pathnode->jpath.path.path_cost = cost_mergejoin(outer_path->path_cost,
  568. inner_path->path_cost,
  569. outersortkeys,
  570. innersortkeys,
  571. outersize,
  572. innersize,
  573. outerwidth,
  574. innerwidth);
  575. /* add in expensive function costs -- JMH 7/7/92 */
  576. #ifdef NOT_USED
  577. if (XfuncMode != XFUNC_OFF)
  578. pathnode->path_cost += xfunc_get_path_cost((Path *) pathnode);
  579. #endif
  580. return pathnode;
  581. }
  583. /*
  584.  * create_hashjoin_path-- XXX HASH
  585.  *   Creates a pathnode corresponding to a hash join between two relations.
  586.  *
  587.  * 'joinrel' is the join relation
  588.  * 'outersize' is the number of tuples in the outer relation
  589.  * 'innersize' is the number of tuples in the inner relation
  590.  * 'outerwidth' is the number of bytes per tuple in the outer relation
  591.  * 'innerwidth' is the number of bytes per tuple in the inner relation
  592.  * 'outer_path' is the outer path
  593.  * 'inner_path' is the inner path
  594.  * 'pathkeys' are the new keys of the join relation
  595.  * 'operator' is the hashjoin operator
  596.  * 'hashclauses' are the applicable join/restriction clauses
  597.  * 'outerkeys' are the sort varkeys for the outer relation
  598.  * 'innerkeys' are the sort varkeys for the inner relation
  599.  *
  600.  */
  601. HashPath   *
  602. create_hashjoin_path(RelOptInfo *joinrel,
  603.  int outersize,
  604.  int innersize,
  605.  int outerwidth,
  606.  int innerwidth,
  607.  Path *outer_path,
  608.  Path *inner_path,
  609.  List *pathkeys,
  610.  Oid operator,
  611.  List *hashclauses,
  612.  List *outerkeys,
  613.  List *innerkeys)
  614. {
  615. HashPath   *pathnode = makeNode(HashPath);
  617. pathnode->jpath.path.pathtype = T_HashJoin;
  618. pathnode->jpath.path.parent = joinrel;
  619. pathnode->jpath.outerjoinpath = outer_path;
  620. pathnode->jpath.innerjoinpath = inner_path;
  621. pathnode->jpath.pathinfo = joinrel->restrictinfo;
  622. pathnode->jpath.path.loc_restrictinfo = NIL;
  623. pathnode->jpath.path.pathkeys = pathkeys;
  624. pathnode->jpath.path.pathorder = makeNode(PathOrder);
  625. pathnode->jpath.path.pathorder->ordtype = SORTOP_ORDER;
  626. pathnode->jpath.path.pathorder->ord.sortop = NULL;
  627. pathnode->jpath.path.outerjoincost = (Cost) 0.0;
  628. pathnode->jpath.path.joinid = (Relids) NULL;
  629. /* pathnode->hashjoinoperator = operator;  */
  630. pathnode->path_hashclauses = hashclauses;
  631. pathnode->outerhashkeys = outerkeys;
  632. pathnode->innerhashkeys = innerkeys;
  633. pathnode->jpath.path.path_cost = cost_hashjoin(outer_path->path_cost,
  634.    inner_path->path_cost,
  635.    outerkeys,
  636.    innerkeys,
  637.    outersize, innersize,
  638.  outerwidth, innerwidth);
  639. /* add in expensive function costs -- JMH 7/7/92 */
  640. #ifdef NOT_USED
  641. if (XfuncMode != XFUNC_OFF)
  642. pathnode->path_cost += xfunc_get_path_cost((Path *) pathnode);
  643. #endif
  644. return pathnode;
  645. }