head 1.31; access; symbols release_4_2:1.31 aix_ok:1.29 Version_2_1:1.17 C_Demo_1:1.8 Retrieve_x_qual:1.5 Retrieve_x_all:1.4 Retrieve_x_1:1.3; locks; strict; comment @ * @; 1.31 date 94.02.07.11.40.56; author aoki; state Exp; branches; next 1.30; 1.30 date 93.11.01.08.00.35; author aoki; state Exp; branches; next 1.29; 1.29 date 93.09.22.01.19.04; author aoki; state Exp; branches; next 1.28; 1.28 date 93.07.24.02.49.52; author aoki; state Exp; branches; next 1.27; 1.27 date 93.07.10.03.16.18; author aoki; state Exp; branches; next 1.26; 1.26 date 92.12.30.17.37.25; author marc; state Exp; branches; next 1.25; 1.25 date 92.07.15.00.40.22; author joey; state Exp; branches; next 1.24; 1.24 date 92.07.08.05.04.07; author joey; state Exp; branches; next 1.23; 1.23 date 92.03.31.23.15.02; author mer; state Exp; branches; next 1.22; 1.22 date 91.11.17.20.36.34; author mer; state Exp; branches; next 1.21; 1.21 date 91.11.15.16.33.14; author hong; state Exp; branches; next 1.20; 1.20 date 91.05.08.15.13.11; author hong; state Exp; branches; next 1.19; 1.19 date 91.04.27.14.19.32; author hong; state Exp; branches; next 1.18; 1.18 date 91.04.05.01.19.18; author hong; state Exp; branches; next 1.17; 1.17 date 90.10.15.15.03.10; author choi; state Exp; branches; next 1.16; 1.16 date 90.09.25.16.39.08; author kemnitz; state Exp; branches; next 1.15; 1.15 date 90.06.13.01.57.20; author hong; state Exp; branches; next 1.14; 1.14 date 90.05.30.18.57.06; author cimarron; state Exp; branches; next 1.13; 1.13 date 90.05.25.14.07.53; author mao; state Exp; branches; next 1.12; 1.12 date 89.11.16.14.20.07; author hong; state Exp; branches; next 1.11; 1.11 date 89.10.25.21.54.52; author hong; state Exp; branches; next 1.10; 1.10 date 89.10.17.13.45.48; author cimarron; state Exp; branches; next 1.9; 1.9 date 89.10.13.18.02.20; author hong; state Exp; branches; next 1.8; 1.8 date 89.09.05.17.19.27; author mao; state C_Demo_1; branches; next 1.7; 1.7 date 89.09.02.13.43.04; author ong; state Exp; branches; next 1.6; 1.6 date 89.08.23.16.01.56; author ong; state Exp; branches; next 1.5; 1.5 date 89.08.04.14.31.26; author goh; state Exp; branches; next 1.4; 1.4 date 89.08.04.13.30.04; author goh; state Exp; branches; next 1.3; 1.3 date 89.08.01.14.33.40; author goh; state Exp; branches; next 1.2; 1.2 date 89.07.19.19.38.39; author goh; state Exp; branches; next 1.1; 1.1 date 89.07.19.13.28.05; author goh; state Exp; branches; next ; desc @@ 1.31 log @proto fixes @ text @/* ---------------------------------------------------------------- * FILE * pathnode.c * * DESCRIPTION * Routines to manipulate pathlists and create path nodes * * INTERFACE ROUTINES * path-is-cheaper * cheaper-path * set_cheapest * add_pathlist * create_seqscan_path * create_index_path * create_nestloop_path * create_mergesort_path * create_hashjoin_path * * IDENTIFICATION * $Header: /import/faerie/faerie/aoki/postgres/src/backend/planner/util/RCS/pathnode.c,v 1.30 1993/11/01 08:00:35 aoki Exp aoki $ *---------------------------------------------------------------- */ #include #include "tmp/c.h" RcsId("$Header: /import/faerie/faerie/aoki/postgres/src/backend/planner/util/RCS/pathnode.c,v 1.30 1993/11/01 08:00:35 aoki Exp aoki $"); #include "planner/internal.h" #include "nodes/relation.h" #include "nodes/relation.a.h" #include "utils/log.h" #include "planner/pathnode.h" #include "planner/clauseinfo.h" #include "planner/cfi.h" #include "planner/costsize.h" #include "planner/keys.h" #include "planner/xfunc.h" #include "planner/clausesel.h" #include "lib/copyfuncs.h" extern int testFlag; /* ==================== * MISC. PATH UTILITIES * ==================== */ /* * path-is-cheaper * * Returns t iff 'path1' is cheaper than 'path2'. * */ /* .. best-innerjoin, better_path, cheaper-path, match-unsorted-outer * .. set_cheapest */ bool path_is_cheaper (path1,path2) Path path1,path2 ; { Cost cost1 = get_path_cost (path1); Cost cost2 = get_path_cost (path2); return((bool)(cost1 < cost2)); } /* * cheaper-path * * Returns the cheaper of 'path1' and 'path2'. * */ Path cheaper_path (path1,path2) Path path1,path2 ; { if ( null(path1) || null (path2) ) { elog (WARN,"cheaper-path: bad path"); } if ( path_is_cheaper (path1,path2) ) { return(path1); } else { return(path2); } } /* * set_cheapest * * Finds the minimum cost path from among a relation's paths. * * 'parent-rel' is the parent relation * 'pathlist' is a list of path nodes corresponding to 'parent-rel' * * Returns and sets the relation entry field with the pathnode that * is minimum. * */ /* .. prune-rel-path, set_cheapest, sort-relation-paths */ Path set_cheapest (parent_rel,pathlist) Rel parent_rel; List pathlist ; { List temp_path; Path cheapest_so_far; Assert(consp(pathlist)); Assert(IsA(parent_rel,Rel)); cheapest_so_far = (Path)CAR(pathlist); foreach (temp_path,CDR(pathlist)) { Path path = (Path)CAR(temp_path); cheapest_so_far = cheaper_path(path,cheapest_so_far); } set_cheapestpath (parent_rel,(PathPtr)cheapest_so_far); return(cheapest_so_far); } /* * add_pathlist * * For each path in the list 'new-paths', add to the list 'unique-paths' * only those paths that are unique (i.e., unique ordering and ordering * keys). Should a conflict arise, the more expensive path is thrown out, * thereby pruning the plan space. But we don't prune if xfunc * told us not to. * * 'parent-rel' is the relation entry to which these paths correspond. * * Returns the list of unique pathnodes. * */ /* .. find-all-join-paths, find-rel-paths, prune-joinrel */ LispValue add_pathlist (parent_rel,unique_paths,new_paths) Rel parent_rel; List unique_paths,new_paths ; { LispValue x; Path new_path; LispValue old_path; foreach (x, new_paths) { new_path = (Path)CAR(x); if (member((LispValue)new_path, unique_paths)) continue; old_path = better_path (new_path,unique_paths); if (old_path == LispTrue) { /* Is a brand new path. */ set_parent (new_path,parent_rel); unique_paths = lispCons ((LispValue)new_path,unique_paths); } else if (null(old_path)) ; /* do nothing if path is not cheaper */ else if (IsA(old_path,Path)) { set_parent (new_path,parent_rel); if (testFlag || !get_pruneable(parent_rel)) { unique_paths = lispCons((LispValue)new_path, unique_paths); } else unique_paths = lispCons((LispValue)new_path, LispRemove(old_path,unique_paths)); } } return(unique_paths); } /* * better_path * * Determines whether 'new-path' has the same ordering and keys as some * path in the list 'unique-paths'. If there is a redundant path, * eliminate the more expensive path. * * Returns: * The old path - if 'new-path' matches some path in 'unique-paths' and is * cheaper * nil - if 'new-path' matches but isn't cheaper * t - if there is no path in the list with the same ordering and keys * */ /* .. add_pathlist */ LispValue better_path (new_path,unique_paths) Path new_path; List unique_paths ; { Path old_path = (Path)NULL; Path path = (Path)NULL; LispValue temp = LispNil; LispValue retval = LispNil; /* XXX - added the following two lines which weren't int the lisp planner, but otherwise, doesn't seem to work for the case where new_path is 'nil */ foreach (temp,unique_paths) { path = (Path) CAR(temp); if ((equal_path_path_ordering (get_p_ordering (new_path), get_p_ordering(path)) && samekeys (get_keys (new_path),get_keys (path)))) { old_path = path; break; } } if ( null(old_path)) { retval = LispTrue; } else if (path_is_cheaper (new_path,old_path) || testFlag) { retval = (LispValue)old_path; } else retval = LispNil; return(retval); } /* =========================== * PATH NODE CREATION ROUTINES * =========================== */ /* * create_seqscan_path * * Creates a path corresponding to a sequential scan, returning the * pathnode. * */ /* .. find-rel-paths */ Path create_seqscan_path (rel) Rel rel ; { LispValue relid; Path pathnode = RMakePath(); set_pathtype (pathnode,T_SeqScan); set_parent (pathnode,rel); set_path_cost (pathnode,0.0); set_p_ordering (pathnode,LispNil); set_pathsortkey (pathnode,(SortKey)NULL); set_keys (pathnode,LispNil); /* copy clauseinfo list into path for expensive function processing -- JMH, 7/7/92 */ set_locclauseinfo(pathnode, (List)CopyObject(get_clauseinfo(rel))); relid = get_relids(rel); if (!null(relid)) relid = CAR(relid); set_path_cost (pathnode,cost_seqscan (relid, get_pages (rel),get_tuples (rel))); /* add in expensive functions cost! -- JMH, 7/7/92 */ if (XfuncMode != XFUNC_OFF) { set_path_cost(pathnode, (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode))); } return(pathnode); } /* * create_index_path * * Creates a single path node for an index scan. * * 'rel' is the parent rel * 'index' is the pathnode for the index on 'rel' * 'restriction-clauses' is a list of restriction clause nodes. * 'is-join-scan' is a flag indicating whether or not the index is being * considered because of its sort order. * * Returns the new path node. * */ /* .. create-index-paths, find-index-paths */ IndexPath create_index_path (rel,index,restriction_clauses,is_join_scan) Rel rel,index; LispValue restriction_clauses; bool is_join_scan; { IndexPath pathnode = RMakeIndexPath(); set_pathtype ((Path)pathnode,T_IndexScan); set_parent ((Path)pathnode,rel); set_indexid (pathnode,get_relids (index)); set_p_ordering ((Path)pathnode,get_ordering (index)); set_keys ((Path)pathnode,get_indexkeys (index)); set_pathsortkey((Path)pathnode, (SortKey)NULL); set_indexqual(pathnode, LispNil); /* copy clauseinfo list into path for expensive function processing -- JMH, 7/7/92 */ set_locclauseinfo(pathnode, set_difference((List) CopyObject(get_clauseinfo(rel)), (List) restriction_clauses)); /* The index must have an ordering for the path to have (ordering) keys, and vice versa. */ if ( get_p_ordering ((Path)pathnode)) { set_keys ((Path)pathnode,collect_index_pathkeys( get_indexkeys (index), get_targetlist (rel))); /* Check that the keys haven't 'disappeared', since they may no longer be in the target list (i.e., index keys that are not relevant to the scan are not applied to the scan path node, so if no index keys were found, we can't order the path). */ if ( null (get_keys ((Path)pathnode))) { set_p_ordering ((Path)pathnode,LispNil); } } if(is_join_scan || null (restriction_clauses)) { /* Indices used for joins or sorting result nodes don't restrict the result at all, they simply order it, so compute the scan cost accordingly -- use a selectivity of 1.0. */ set_path_cost ( (Path)pathnode, cost_index (CInteger(CAR(get_relids(index))), get_pages (index),1.0, get_pages (rel), get_tuples (rel), get_pages (index), get_tuples(index), false)); /* add in expensive functions cost! -- JMH, 7/7/92 */ if (XfuncMode != XFUNC_OFF) { set_path_cost(pathnode, (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode))); } } else { /* Compute scan cost for the case when 'index' is used with a restriction clause. */ LispValue relattvals = get_relattvals (restriction_clauses); /* pagesel is '(Cost Cost) */ List pagesel = index_selectivity (CInteger(CAR(get_relids(index))), get_classlist (index), get_opnos (restriction_clauses), CInteger(getrelid (CInteger (CAR(get_relids (rel))), _query_range_table_)), nth (0,relattvals), nth (1,relattvals), nth (2,relattvals), length (restriction_clauses)); /* each clause gets an equal selectivity */ Cost clausesel = pow (CDouble(CADR (pagesel)), 1.0 / (double) length(restriction_clauses)); Count temp1 = (Count)CDouble(CAR(pagesel)); Cost temp2 = (Cost)CDouble(CADR(pagesel)); set_indexqual (pathnode,restriction_clauses); set_path_cost ( (Path)pathnode, cost_index (CInteger(CAR(get_relids(index))), temp1, temp2, get_pages (rel), get_tuples (rel),get_pages (index), get_tuples (index), false)); /* add in expensive functions cost! -- JMH, 7/7/92 */ if (XfuncMode != XFUNC_OFF) { set_path_cost(pathnode, (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode))); } /* Set selectivities of clauses used with index to the selectivity of this index, subdividing the selectivity equally over each of the clauses. */ /* XXX Can this divide the selectivities in a better way? */ set_clause_selectivities (restriction_clauses,clausesel); } return(pathnode); } /* * create_nestloop_path * * Creates a pathnode corresponding to a nestloop join between two * relations. * * 'joinrel' is the join relation. * 'outer_rel' is the outer join relation * 'outer_path' is the outer join path. * 'inner_path' is the inner join path. * 'keys' are the keys of the path * * Returns the resulting path node. * */ /* .. match-unsorted-outer */ JoinPath create_nestloop_path (joinrel,outer_rel,outer_path,inner_path,keys) Rel joinrel,outer_rel; Path outer_path,inner_path; List keys ; { JoinPath pathnode = RMakeJoinPath(); set_pathtype((Path)pathnode,T_NestLoop); set_parent ((Path)pathnode,joinrel); set_outerjoinpath (pathnode,(pathPtr)outer_path); set_innerjoinpath (pathnode,(pathPtr)inner_path); set_pathclauseinfo (pathnode,get_clauseinfo (joinrel)); set_keys ((Path)pathnode,keys); set_pathsortkey ((Path)pathnode,(SortKey)NULL); set_joinid((Path)pathnode,LispNil); set_outerjoincost((Path)pathnode,(Cost)0); set_p_ordering((Path)pathnode,LispNil); set_locclauseinfo((Path)pathnode,LispNil); if /*when */ ( keys) { set_p_ordering ((Path)pathnode,get_p_ordering (outer_path)); } set_path_cost ((Path)pathnode, cost_nestloop (get_path_cost (outer_path), get_path_cost (inner_path), get_size( outer_rel), get_size( get_parent(inner_path)), page_size( get_size(outer_rel), get_width(outer_rel)), IsA(inner_path,IndexPath))); /* add in expensive function costs -- JMH 7/7/92 */ if (XfuncMode != XFUNC_OFF) { set_path_cost(pathnode, (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode))); } return(pathnode); } /* * create_mergesort_path * * Creates a pathnode corresponding to a mergesort join between * two relations * * 'joinrel' is the join relation * 'outersize' is the number of tuples in the outer relation * 'innersize' is the number of tuples in the inner relation * 'outerwidth' is the number of bytes per tuple in the outer relation * 'innerwidth' is the number of bytes per tuple in the inner relation * 'outer_path' is the outer path * 'inner_path' is the inner path * 'keys' are the new keys of the join relation * 'order' is the sort order required for the merge * 'mergeclauses' are the applicable join/restriction clauses * 'outersortkeys' are the sort varkeys for the outer relation * 'innersortkeys' are the sort varkeys for the inner relation * */ /* .. match-unsorted-inner, match-unsorted-outer, sort-inner-and-outer */ MergePath create_mergesort_path (joinrel,outersize,innersize,outerwidth, innerwidth,outer_path,inner_path,keys,order, mergeclauses,outersortkeys,innersortkeys) Rel joinrel; Count outersize,innersize,outerwidth,innerwidth; Path outer_path,inner_path; LispValue keys,order,mergeclauses,outersortkeys,innersortkeys ; { MergePath pathnode = RMakeMergePath(); set_pathtype ((Path)pathnode,T_MergeJoin); set_parent ((Path)pathnode,joinrel); set_outerjoinpath ((JoinPath)pathnode,(pathPtr)outer_path); set_innerjoinpath ((JoinPath)pathnode,(pathPtr)inner_path); set_pathclauseinfo ((JoinPath)pathnode,get_clauseinfo (joinrel)); set_keys ((Path)pathnode,keys); set_p_ordering ((Path)pathnode,order); set_path_mergeclauses (pathnode,mergeclauses); set_locclauseinfo((Path)pathnode,LispNil); set_outersortkeys (pathnode,outersortkeys); set_innersortkeys (pathnode,innersortkeys); set_path_cost ((Path)pathnode, cost_mergesort( get_path_cost (outer_path), get_path_cost (inner_path), outersortkeys, innersortkeys, outersize, innersize, outerwidth, innerwidth)); /* add in expensive function costs -- JMH 7/7/92 */ if (XfuncMode != XFUNC_OFF) { set_path_cost(pathnode, (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode))); } return(pathnode); } /* * create_hashjoin_path * * XXX HASH * * Creates a pathnode corresponding to a hash join between two relations. * * 'joinrel' is the join relation * 'outersize' is the number of tuples in the outer relation * 'innersize' is the number of tuples in the inner relation * 'outerwidth' is the number of bytes per tuple in the outer relation * 'innerwidth' is the number of bytes per tuple in the inner relation * 'outer_path' is the outer path * 'inner_path' is the inner path * 'keys' are the new keys of the join relation * 'operator' is the hashjoin operator * 'hashclauses' are the applicable join/restriction clauses * 'outerkeys' are the sort varkeys for the outer relation * 'innerkeys' are the sort varkeys for the inner relation * */ /* .. hash-inner-and-outer */ HashPath create_hashjoin_path (joinrel,outersize,innersize,outerwidth, innerwidth,outer_path,inner_path,keys,operator, hashclauses,outerkeys,innerkeys) Rel joinrel; Count outersize,innersize,outerwidth,innerwidth; Path outer_path,inner_path; LispValue keys,hashclauses,outerkeys,innerkeys ; ObjectId operator; { HashPath pathnode = RMakeHashPath(); set_pathtype ((Path)pathnode,T_HashJoin); set_parent ((Path)pathnode,joinrel); set_outerjoinpath ((JoinPath)pathnode,(pathPtr)outer_path); set_innerjoinpath ((JoinPath)pathnode,(pathPtr)inner_path); set_pathclauseinfo ((JoinPath)pathnode,get_clauseinfo (joinrel)); set_locclauseinfo((Path)pathnode,LispNil); set_keys ((Path)pathnode,keys); set_pathsortkey ((Path)pathnode,(SortKey)NULL); set_p_ordering((Path)pathnode,LispNil); set_outerjoincost((Path)pathnode,(Cost)0); set_joinid((Path)pathnode, (Relid)NULL); /* set_hashjoinoperator (pathnode,operator); */ set_path_hashclauses (pathnode,hashclauses); set_outerhashkeys (pathnode,outerkeys); set_innerhashkeys (pathnode,innerkeys); set_path_cost ((Path)pathnode,cost_hashjoin( get_path_cost (outer_path), get_path_cost (inner_path), outerkeys, innerkeys, outersize,innersize, outerwidth,innerwidth)); /* add in expensive function costs -- JMH 7/7/92 */ if (XfuncMode != XFUNC_OFF) { set_path_cost(pathnode, (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode))); } return(pathnode); } @ 1.30 log @added lib/copyfuncs.h @ text @d20 1 a20 1 * $Header: /usr/local/devel/postgres/src/backend/planner/util/RCS/pathnode.c,v 1.29 1993/09/22 01:19:04 aoki Exp aoki $ d28 1 a28 1 RcsId("$Header$"); d42 1 @ 1.29 log @selectivity of or'd clauses was always being computed to be 0 by a bogus cast: (double) (int/int) instead of double / (double) int @ text @d20 1 a20 1 * $Header: /faerie/sparc/postgres/src/backend/planner/util/RCS/pathnode.c,v 1.28 1993/07/24 02:49:52 aoki Exp $ d23 1 d26 4 d42 2 @ 1.28 log @joey's fix from tuesday @ text @d1 3 a3 3 /* * FILE * pathnode d5 2 a6 2 * DESCRIPTION * Routines to manipulate pathlists and create path nodes d8 1 a8 1 * EXPORTS d18 4 a21 1 * $Header: /home2/aoki/master/src/backend/planner/util/RCS/pathnode.c,v 1.28 1993/07/21 18:41:16 joey Exp $ d374 1 a374 1 (double)(1/length(restriction_clauses))); a592 1 @ 1.27 log @wrapped xfunc calculations in XFUNC_OFF tests @ text @d18 1 a18 1 * $Header: /faerie/hpux/postgres/src/backend/planner/util/RCS/pathnode.c,v 1.26 1992/12/30 17:37:25 marc Exp aoki $ d128 2 a129 1 * thereby pruning the plan space. d162 1 a162 1 if (testFlag) { @ 1.26 log @don't use pointer @ text @d18 1 a18 1 * $Header: /a/staff/marc/src/postgres/src/backend/planner/util/RCS/pathnode.c,v 1.25 92/07/15 00:40:22 joey Exp Locker: marc $ d268 5 a272 2 set_path_cost(pathnode, (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode))); d313 2 a314 3 set_difference(CopyObject(get_clauseinfo(rel)), restriction_clauses, LispNil)); d346 5 a350 2 set_path_cost(pathnode, (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode))); d384 5 a388 2 set_path_cost(pathnode, (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode))); d452 5 a456 2 set_path_cost(pathnode, (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode))); d515 5 a519 2 set_path_cost(pathnode, (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode))); d582 5 a586 2 set_path_cost(pathnode, (get_path_cost(pathnode) + xfunc_get_path_cost(pathnode))); @ 1.25 log @make sure that 2nd arg to set_path_cost is in parens @ text @d18 1 a18 1 * $Header: /private/joey/pg/src/planner/util/RCS/pathnode.c,v 1.24 1992/07/08 05:04:07 joey Exp joey $ d428 1 a428 1 set_outerjoincost((Path)pathnode,(Cost)NULL); @ 1.24 log @Made the various create_xxx_path functions set up the locclauseinfo and correctly include expensive functions in their path_cost fields. @ text @d18 1 a18 1 * $Header: /private/joey/pg/src/planner/util/RCS/pathnode.c,v 1.23 1992/03/31 23:15:02 mer Exp joey $ d268 2 a269 2 set_path_cost(pathnode, get_path_cost(pathnode) + xfunc_get_path_cost(pathnode)); d344 2 a345 2 set_path_cost(pathnode, get_path_cost(pathnode) + xfunc_get_path_cost(pathnode)); d379 2 a380 2 set_path_cost(pathnode, get_path_cost(pathnode) + xfunc_get_path_cost(pathnode)); d444 2 a445 2 set_path_cost(pathnode, get_path_cost(pathnode) + xfunc_get_path_cost(pathnode)); d504 2 a505 2 set_path_cost(pathnode, get_path_cost(pathnode) + xfunc_get_path_cost(pathnode)); d568 2 a569 2 set_path_cost(pathnode, get_path_cost(pathnode) + xfunc_get_path_cost(pathnode)); @ 1.23 log @change accessor functions into macros @ text @d18 1 a18 1 * $Header: /users/mer/pg/src/planner/util/RCS/pathnode.c,v 1.22 1991/11/17 20:36:34 mer Exp mer $ d33 1 d256 4 d267 3 d307 6 d343 3 d378 4 d430 1 d443 3 d492 1 d503 3 d551 1 d567 3 @ 1.22 log @prototyping @ text @d18 1 a18 1 * $Header: /users/mer/postgres/src/planner/util/RCS/pathnode.c,v 1.21 1991/11/15 16:33:14 hong Exp mer $ d116 1 a116 1 set_cheapestpath (parent_rel,cheapest_so_far); d401 2 a402 2 set_outerjoinpath (pathnode,outer_path); set_innerjoinpath (pathnode,inner_path); d461 2 a462 2 set_outerjoinpath ((JoinPath)pathnode,outer_path); set_innerjoinpath ((JoinPath)pathnode,inner_path); d519 2 a520 2 set_outerjoinpath ((JoinPath)pathnode,outer_path); set_innerjoinpath ((JoinPath)pathnode,inner_path); @ 1.21 log @for prototyping @ text @d18 1 a18 1 * $Header: RCS/pathnode.c,v 1.20 91/05/08 15:13:11 hong Exp Locker: hong $ d32 1 a34 9 /* ---------------- * node creator declarations * ---------------- */ extern HashPath RMakeHashPath(); extern MergePath RMakeMergePath(); extern JoinPath RMakeJoinPath(); extern IndexPath RMakeIndexPath(); extern Path RMakePath(); a35 1 d147 1 a147 1 if (member(new_path, unique_paths)) d153 1 a153 1 unique_paths = lispCons (new_path,unique_paths); d161 1 a161 1 unique_paths = lispCons(new_path, unique_paths); d164 1 a164 1 unique_paths = lispCons(new_path, d292 2 a293 2 set_pathtype (pathnode,T_IndexScan); set_parent (pathnode,rel); d295 3 a297 3 set_p_ordering (pathnode,get_ordering (index)); set_keys (pathnode,get_indexkeys (index)); set_pathsortkey(pathnode, (SortKey)NULL); d304 3 a306 3 if ( get_p_ordering (pathnode)) { set_keys (pathnode,collect_index_pathkeys (get_indexkeys (index), get_targetlist (rel))); d313 2 a314 2 if ( null (get_keys (pathnode))) { set_p_ordering (pathnode,LispNil); d322 7 a328 6 set_path_cost (pathnode,cost_index (CInteger(CAR(get_relids(index))), get_pages (index),1.0, get_pages (rel), get_tuples (rel), get_pages (index), get_tuples(index), false)); d354 7 a360 6 set_path_cost (pathnode,cost_index (CInteger(CAR(get_relids(index))), temp1, temp2, get_pages (rel), get_tuples (rel),get_pages (index), get_tuples (index), false)); d399 2 a400 2 set_pathtype(pathnode,T_NestLoop); set_parent (pathnode,joinrel); d404 5 a408 5 set_keys (pathnode,keys); set_pathsortkey (pathnode,LispNil); set_joinid(pathnode,LispNil); set_outerjoincost(pathnode,LispNil); set_p_ordering(pathnode,LispNil); d411 1 a411 1 set_p_ordering (pathnode,get_p_ordering (outer_path)); d413 8 a420 7 set_path_cost (pathnode,cost_nestloop (get_path_cost (outer_path), get_path_cost (inner_path), get_size (outer_rel), get_size (get_parent(inner_path)), page_size (get_size(outer_rel), get_width(outer_rel)), IsA(inner_path,IndexPath))); d459 7 a465 7 set_pathtype (pathnode,T_MergeJoin); set_parent (pathnode,joinrel); set_outerjoinpath (pathnode,outer_path); set_innerjoinpath (pathnode,inner_path); set_pathclauseinfo (pathnode,get_clauseinfo (joinrel)); set_keys (pathnode,keys); set_p_ordering (pathnode,order); d469 8 a476 5 set_path_cost (pathnode,cost_mergesort (get_path_cost (outer_path), get_path_cost (inner_path), outersortkeys,innersortkeys, outersize,innersize,outerwidth, innerwidth)); d517 10 a526 10 set_pathtype (pathnode,T_HashJoin); set_parent (pathnode,joinrel); set_outerjoinpath (pathnode,outer_path); set_innerjoinpath (pathnode,inner_path); set_pathclauseinfo (pathnode,get_clauseinfo (joinrel)); set_keys (pathnode,keys); set_pathsortkey (pathnode,(SortKey)NULL); set_p_ordering(pathnode,LispNil); set_outerjoincost(pathnode,0); set_joinid(pathnode,LispNil); d531 6 a536 6 set_path_cost (pathnode,cost_hashjoin (get_path_cost (outer_path), get_path_cost (inner_path), outerkeys, innerkeys, outersize,innersize, outerwidth,innerwidth)); @ 1.20 log @try to eliminate duplicate paths @ text @d18 1 a18 1 * $Header: RCS/pathnode.c,v 1.19 91/04/27 14:19:32 hong Exp $ d262 1 a262 1 set_sortpath (pathnode,(SortKey)NULL); d306 1 a306 1 set_sortpath(pathnode, (SortKey)NULL); d412 1 a412 1 set_sortpath (pathnode,LispNil); d459 1 a459 1 int outersize,innersize,outerwidth,innerwidth; d526 1 a526 1 set_sortpath (pathnode,(SortKey)NULL); @ 1.19 log @added some special code for my experiments only @ text @d18 1 a18 1 * $Header: RCS/pathnode.c,v 1.19 91/04/25 04:22:06 hong Exp Locker: hong $ d156 2 @ 1.18 log @cost_index() sometimes needs know whether the indexscan is as the inner path of a nestloop join . @ text @a0 1 d18 1 a18 1 * $Header: RCS/pathnode.c,v 1.17 90/10/15 15:03:10 choi Exp Locker: hong $ d33 1 d151 6 a156 3 LispValue new_path = LispNil; foreach (new_path, new_paths) { LispValue old_path = better_path (CAR(new_path),unique_paths); d159 2 a160 2 set_parent (CAR(new_path),parent_rel); unique_paths = lispCons (CAR(new_path),unique_paths); d166 7 a172 3 set_parent (CAR(new_path),parent_rel); unique_paths = lispCons (CAR(new_path), LispRemove(old_path,unique_paths)); d222 1 a222 1 if (path_is_cheaper (new_path,old_path)) { d229 1 a229 1 } @ 1.17 log @changed remove () to LispRemove(). (posix) @ text @d19 1 a19 1 * $Header: RCS/pathnode.c,v 1.16 90/09/25 16:39:08 kemnitz Exp Locker: choi $ d324 4 a327 2 get_pages (rel),get_tuples (rel), get_pages (index),get_tuples(index))); d358 1 a358 1 get_tuples (index))); @ 1.16 log @Updating from revision 1.15 to revision 1.16 @ text @d19 1 a19 1 * $Header: RCS/pathnode.c,v 1.16 90/08/14 13:17:56 cimarron Exp $ d165 1 a165 1 remove(old_path,unique_paths)); @ 1.15 log @a fix for index scan @ text @d19 1 a19 1 * $Header: RCS/pathnode.c,v 1.14 90/05/30 18:57:06 cimarron Exp $ d21 1 d24 5 a28 3 #include "log.h" #include "relation.h" #include "relation.a.h" a31 1 #include @ 1.14 log @CreateNode(Foo) --> RMakeFoo() change @ text @d19 1 a19 1 * $Header: RCS/pathnode.c,v 1.12 89/11/16 14:20:07 hong Exp $ d333 3 a335 3 getrelid (CInteger(CAR(get_relids (rel))), _query_range_table_), @ 1.13 log @when computing index selectivity, we were botching the fetch of the indexed relation's oid. @ text @d32 9 d42 1 a242 2 extern void PrintPath(); extern bool EqualPath(); d245 1 a245 1 Path pathnode = CreateNode(Path); a246 2 pathnode->equalFunc = EqualPath; pathnode->printFunc = PrintPath; d288 1 a288 1 IndexPath pathnode = CreateNode(IndexPath); a297 3 pathnode->printFunc = PrintIndexPath; pathnode->equalFunc = EqualIndexPath; d333 3 a335 3 CInteger(getrelid (CInteger (CAR(get_relids(rel))), _query_range_table_)), d391 1 a391 1 JoinPath pathnode = CreateNode(JoinPath); a392 3 pathnode->printFunc = PrintJoinPath; pathnode->equalFunc = EqualJoinPath; d450 1 a450 1 MergePath pathnode = CreateNode(MergePath); a451 3 pathnode->printFunc = PrintMergePath; pathnode->equalFunc = EqualMergePath; d505 1 a505 4 HashPath pathnode = CreateNode(HashPath); pathnode->printFunc = PrintHashPath; pathnode->equalFunc = EqualHashPath; @ 1.12 log @changes of cost_nestloop interface @ text @d19 1 a19 1 * $Header: RCS/pathnode.c,v 1.11 89/10/25 21:54:52 hong Exp $ d330 3 a332 3 getrelid (CInteger(CAR(get_relids (rel))), _query_range_table_), @ 1.11 log @fixed cost for index join @ text @d19 1 a19 1 * $Header: RCS/pathnode.c,v 1.10 89/10/17 13:45:48 cimarron Exp Locker: hong $ d409 5 a413 1 get_size (outer_rel))); @ 1.10 log @changes to support MergeJoins in the executor. @ text @d19 1 a19 1 * $Header: RCS/pathnode.c,v 1.9 89/10/13 18:02:20 hong Exp $ d318 1 a318 1 get_pages (index),0.000000, @ 1.9 log @fixes for mergejoins @ text @d19 1 a19 1 * $Header: RCS/pathnode.c,v 1.8 89/09/05 17:19:27 mao C_Demo_1 Locker: hong $ d451 1 a451 1 set_pathtype (pathnode,T_MergeSort); @ 1.8 log @Working version of C-only demo @ text @d19 1 a19 1 * $Header: RCS/pathnode.c,v 1.7 89/09/02 13:43:04 ong Exp $ d441 4 a444 3 LispValue joinrel,outersize,innersize,outerwidth,innerwidth, outer_path,inner_path,keys,order,mergeclauses,outersortkeys, innersortkeys ; d451 1 d457 2 a458 2 set_ordering (pathnode,order); set_mergeclauses (pathnode,mergeclauses); @ 1.7 log @#included costsize.h @ text @d19 1 a19 1 * $Header: RCS/pathnode.c,v 1.6 89/08/23 16:01:56 ong Exp Locker: ong $ @ 1.6 log @planner supports all but rules and mergesort @ text @d19 1 a19 1 * $Header: /n/postgres/a/postgres/ong/postgres/src/planner/util/RCS/pathnode.c,v 1.5 89/08/04 14:31:26 goh Exp $ d30 1 a30 1 @ 1.5 log @reorganised header files @ text @d19 1 a19 1 * $Header: pathnode.c,v 1.4 89/08/04 13:30:04 goh Locked $ d29 1 d103 2 a104 3 cheapest_so_far = CreateNode(Path); set_path_cost(cheapest_so_far, 9999999.999); /* XXX - what is the max cost ? */ d106 3 a108 1 foreach (temp_path,pathlist) { d139 1 a139 1 LispValue new_path; d141 14 a154 6 LispValue old_path = better_path (CAR(new_path),unique_paths); if /*when */ ( old_path) { set_parent (CAR(new_path),parent_rel); unique_paths = lispCons (CAR(new_path), remove (old_path,unique_paths)); } d157 1 a157 1 } d181 2 a182 2 Path old_path; Path path; d189 1 a189 5 if (null(new_path)) return(LispNil); old_path = (Path)LispNil; d199 1 a199 1 if(null (old_path)) { d202 6 a207 3 else if (path_is_cheaper (new_path,old_path)) { retval = (LispValue)old_path; } d209 2 a210 1 } d278 3 a280 1 LispValue rel,index,restriction_clauses,is_join_scan ; d282 9 a290 1 IndexPath pathnode = CreateNode(IndexPath); d292 6 a297 5 set_pathtype (pathnode,T_IndexScan); set_parent (pathnode,rel); set_indexid (pathnode,get_indexid (index)); set_ordering (pathnode,get_ordering (index)); set_keys (pathnode,get_indexkeys (index)); d299 2 a300 6 /* The index must have an ordering for the path to have (ordering) keys, and vice versa. */ if /*when */ ( get_ordering (pathnode)) { set_keys (pathnode,collect_index_pathkeys (get_indexkeys (index), d309 1 a309 1 set_ordering (pathnode,LispNil); d311 33 a343 29 } if(is_join_scan || null (restriction_clauses)) { /* Indices used for joins or sorting result nodes don't restrict the result at all, they simply order it, so compute the scan cost accordingly -- use a selectivity of 1.0. */ set_path_cost (pathnode,cost_index (nth (0,get_indexid (index)), get_pages (index),0.000000, get_pages (rel),get_tuples (rel), get_pages (index),get_tuples(index))); } else { /* Compute scan cost for the case when 'index' is used with a restriction clause. */ LispValue relattvals = get_relattvals (restriction_clauses); /* pagesel is '(Cost Cost) */ List pagesel = index_selectivity (nth (0,get_indexid (index)), get_classlist (index), get_opnos (restriction_clauses), getrelid (get_relid (rel), _query_range_table_), nth (0,relattvals), nth (1,relattvals), nth (2,relattvals), length (restriction_clauses)); /* each clause gets an equal selectivity */ Cost clausesel = expt (nth (1,pagesel), (1 / length (restriction_clauses))); d345 17 a361 16 set_indexqual (pathnode,restriction_clauses); set_path_cost (pathnode,cost_index (nth (0,get_indexid (index)), floor (nth (0,pagesel)), nth (1,pagesel),get_pages (rel), get_tuples (rel),get_pages (index), get_tuples (index))); /* Set selectivities of clauses used with index to the selectivity of this index, subdividing the selectivity equally over each of the clauses. */ /* XXX Can this divide the selectivities in a better way? */ set_clause_selectivities (restriction_clauses,clausesel); } return(pathnode); d382 1 a382 1 Path d384 3 a386 1 LispValue joinrel,outer_rel,outer_path,inner_path,keys ; d388 1 a388 1 Path pathnode = CreateNode(Path); d390 3 d397 1 a397 1 set_clauseinfo (pathnode,get_clauseinfo (joinrel)); d399 5 d405 1 a405 1 set_ordering (pathnode,get_ordering (outer_path)); d408 2 a409 2 get_path_cost (inner_path), get_size (outer_rel))); d447 3 d453 1 a453 1 set_clauseinfo (pathnode,get_clauseinfo (joinrel)); d496 5 a500 2 LispValue joinrel,outersize,innersize,outerwidth,innerwidth, outer_path,inner_path,keys,operator,hashclauses,outerkeys,innerkeys ; d502 1 a502 1 HashPath pathnode = CreateNode(HashPath); d504 24 a527 15 set_pathtype (pathnode,T_HashJoin); set_parent (pathnode,joinrel); set_outerjoinpath (pathnode,outer_path); set_innerjoinpath (pathnode,inner_path); set_clauseinfo (pathnode,get_clauseinfo (joinrel)); set_keys (pathnode,keys); set_hashjoinoperator (pathnode,operator); set_hashclauses (pathnode,hashclauses); set_outerhashkeys (pathnode,outerkeys); set_innerhashkeys (pathnode,innerkeys); set_path_cost (pathnode,cost_hashjoin (get_path_cost (outer_path), get_path_cost (inner_path),outerkeys, innerkeys,outersize,innersize, outerwidth,innerwidth)); return(pathnode); @ 1.4 log @checkin for retrieve (x.all) @ text @d19 1 a19 1 * $Header: pathnode.c,v 1.3 89/08/01 14:33:40 goh Locked $ d22 1 a22 1 #include "internal.h" d26 3 a28 2 #include "pathnode.h" #include "clauseinfo.h" a29 1 extern List index_selectivity(); /* #include "cfi.h" */ a30 2 /* declare (localf (better_path)); */ /* declare (special (_WARN_)); */ @ 1.3 log @retrieve (x=1) checkin @ text @d19 1 a19 1 * $Header: pathnode.c,v 1.2 89/07/19 19:38:39 goh Locked $ d53 2 a54 2 Cost cost1 = get_cost (path1); Cost cost2 = get_cost (path2); d101 2 a102 1 Path path,cheapest_so_far; d105 2 a106 1 set_cost(cheapest_so_far,9999999.999); /* XXX - what is the max cost ? */ d108 2 a109 1 foreach ((LispValue)path,pathlist) { d136 2 a137 1 LispValue parent_rel,unique_paths,new_paths ; d141 1 a141 1 LispValue old_path = better_path (new_path,unique_paths); d143 3 a145 2 set_parent (new_path,parent_rel); unique_paths = cons (new_path,remove (old_path,unique_paths)); a167 9 static bool lambda1(path,new_path) Path path,new_path; { return (bool)(equal_path_path_ordering (get_ordering (new_path), get_ordering(path)) && samekeys (get_keys (new_path),get_keys (path))); } a172 1 /* declare (special (new_path)); */ d174 2 d178 3 a180 1 old_path = (Path)find_if (lambda1,unique_paths); d182 13 d196 1 a196 1 retval = LispTrue; d199 1 a199 1 retval = (LispValue)old_path; d201 1 a201 1 d223 1 a223 1 LispValue rel ; d225 3 a227 1 Path pathnode = CreateNode(Path); d229 18 a246 5 /* set_pathtype (pathnode,SEQ_SCAN); */ set_parent (pathnode,rel); set_cost (pathnode,cost_seqscan (get_relid (rel), get_pages (rel),get_tuples (rel))); return(pathnode); d274 1 a274 2 /* set_pathtype (pathnode,INDEX_SCAN);*/ d302 1 a302 1 set_cost (pathnode,cost_index (nth (0,get_indexid (index)), d327 1 a327 1 set_cost (pathnode,cost_index (nth (0,get_indexid (index)), d368 1 a368 1 /* set_pathtype(pathnode,NEST_LOOP); */ d377 2 a378 2 set_cost (pathnode,cost_nestloop (get_cost (outer_path), get_cost (inner_path), d426 2 a427 2 set_cost (pathnode,cost_mergesort (get_cost (outer_path), get_cost (inner_path), d468 1 a468 1 /* set_pathtype (pathnode,T_HashJoin); */ d478 2 a479 2 set_cost (pathnode,cost_hashjoin (get_cost (outer_path), get_cost (inner_path),outerkeys, @ 1.2 log @phase II of checkin @ text @d19 1 a19 1 * $Header: pathnode.c,v 1.1 89/07/19 13:28:05 goh Locked $ d161 3 a163 3 /* .. add_pathlist */ bool d167 1 a167 1 return (bool)(qual_path_path_ordering (get_ordering (new_path), d260 1 a260 1 get_tlist (rel))); d287 1 a287 1 get_class (index), d297 2 a298 1 expt (nth (1,pagesel),div (0.000000,length (restriction_clauses))); d344 3 a346 3 set_outerpath (pathnode,outer_path); set_innerpath (pathnode,inner_path); set_clause_info (pathnode,get_clause_info (joinrel)); d392 3 a394 3 set_outerpath (pathnode,outer_path); set_innerpath (pathnode,inner_path); set_clause_info (pathnode,get_clause_info (joinrel)); d444 3 a446 3 set_outerpath (pathnode,outer_path); set_innerpath (pathnode,inner_path); set_clause_info (pathnode,get_clause_info (joinrel)); @ 1.1 log @Initial revision @ text @d19 1 a19 1 * $Header:$ d24 4 d29 2 d51 1 a51 1 LispValue path1,path2 ; d53 4 a56 7 LispValue cost1 = get_cost (path1); LispValue cost2 = get_cost (path2); if (numberp (cost1) && numberp (cost2) && CInteger(cost1) < CInteger(cost2)) return(true); else return(false); d65 1 a65 1 LispValue d67 1 a67 1 LispValue path1,path2 ; d69 9 a77 13 if ( or (null (path1),null (path2)) ) { elog (WARN,"cheaper-path: bad path"); } else { } ; if ( path_is_cheaper (path1,path2) ) { path1; } else { path2; } ; d95 2 a96 1 LispValue d98 2 a99 1 LispValue parent_rel,pathlist ; d101 12 a112 10 LispValue retval; LispValue cheapest_path = ( CDR (pathlist) ? set_cheapest (parent_rel,cdr (pathlist)) : LispNil); retval = set_cheapest_path (parent_rel, ( (cheapest_path && path_is_cheaper (cheapest_path, car (pathlist))) ? cheapest_path : CAR(pathlist))); return(retval); d164 2 a165 2 lambda1(path) LispValue path ; d167 3 a169 5 if(qual_path_path_ordering (get_ordering (new_path),get_ordering(path)) && samekeys (get_keys (new_path),get_keys (path))) return(true); else return(false); d174 2 a175 1 LispValue new_path,unique_paths ; d178 1 a178 1 LispValue old_path; d181 2 a182 1 old_path = find_if (lambda1,unique_paths); d187 1 a187 1 retval = old_path; d189 1 a189 4 else { /* 'path' is cheaper */ retval = LispNil; /* 'path' isn't cheaper */ } d209 1 a209 1 LispValue d213 7 a219 7 /* XXX - let form, maybe incorrect */ LispValue pathnode = create_node ("Path"); set_pathtype (pathnode,/* XXX- QUOTE SeqScan,*/); set_parent (pathnode,rel); set_cost (pathnode,cost_seqscan (get_relid (rel),get_pages (rel),get_tuples (rel))); pathnode; ; d237 1 d240 2 a241 1 LispValue d245 4 a248 3 /* XXX - let form, maybe incorrect */ LispValue pathnode = create_node ("Path"); set_pathtype (pathnode,/* XXX- QUOTE IndexScan,*/); d252 6 a257 4 set_indexkeys (pathnode,get_indexkeys (index)) /* The index must have an ordering for the path to have (ordering) keys, */ /* and vice versa. */ d259 11 a269 10 set_keys (pathnode,collect_index_pathkeys (get_indexkeys (index), get_tlist (rel))) /* Check that the keys haven't 'disappeared', since they may no longer be in the target list (i.e., index keys that are not relevant to the scan are not applied to the scan path node, so if no index keys were found, we can't order the path). */ if /*when */ ( null (get_keys (pathnode))) { set_ordering (pathnode,nil); } d285 2 a286 1 LispValue pagesel = index_selectivity (nth (0,get_indexid (index)), d295 2 a296 2 LispValue clausesel = /* each clause gets an equal selectivity */ d298 1 d304 1 a304 1 get_tuples (index))) d335 1 a335 1 LispValue d339 3 a341 3 /* XXX - let form, maybe incorrect */ LispValue pathnode = create_node ("Path"); set_pathtype (pathnode,/* XXX- QUOTE NestLoop,*/); d349 1 a349 1 }; d377 4 a380 3 /* .. match-unsorted-inner, match-unsorted-outer, sort-inner-and-outer */ LispValue d388 2 a389 3 /* XXX - let form, maybe incorrect */ LispValue pathnode = create_node ("Path"); set_pathtype (pathnode,/* XXX- QUOTE MergeSort,*/); d429 4 a432 3 /* .. hash-inner-and-outer */ LispValue d439 3 a441 2 LispValue pathnode = create_node ("Path"); set_pathtype (pathnode,/* XXX- QUOTE HashJoin,*/); @