head 1.29; access; symbols release_4_2:1.29 aix_ok:1.29 Version_2_1:1.15 C_Demo_1:1.9 Retrieve_x_qual:1.6 Retrieve_x_all:1.5 Retrieve_x_1:1.4; locks; strict; comment @ * @; 1.29 date 93.06.15.23.59.02; author aoki; state Exp; branches; next 1.28; 1.28 date 92.08.19.01.12.02; author mer; state Exp; branches; next 1.27; 1.27 date 92.07.09.07.33.23; author joey; state Exp; branches; next 1.26; 1.26 date 92.03.31.23.13.08; author mer; state Exp; branches; next 1.25; 1.25 date 92.01.22.23.13.37; author joey; state Exp; branches; next 1.24; 1.24 date 91.11.27.11.41.51; author postgres; state Exp; branches; next 1.23; 1.23 date 91.11.27.10.44.42; author postgres; state Exp; branches; next 1.22; 1.22 date 91.11.17.20.39.50; author mer; state Exp; branches; next 1.21; 1.21 date 91.11.15.16.27.08; author hong; state Exp; branches; next 1.20; 1.20 date 91.11.02.21.42.25; author hong; state Exp; branches; next 1.19; 1.19 date 91.05.29.23.10.43; author hong; state Exp; branches; next 1.18; 1.18 date 91.05.08.15.09.12; author hong; state Exp; branches; next 1.17; 1.17 date 91.04.25.04.15.42; author hong; state Exp; branches; next 1.16; 1.16 date 91.04.24.19.42.26; author kemnitz; state Exp; branches; next 1.15; 1.15 date 90.10.16.11.09.53; author choi; state Exp; branches; next 1.14; 1.14 date 90.09.25.16.35.47; author kemnitz; state Exp; branches; next 1.13; 1.13 date 89.10.26.16.18.14; author hong; state Exp; branches; next 1.12; 1.12 date 89.10.13.17.59.20; author hong; state Exp; branches; next 1.11; 1.11 date 89.09.29.14.42.28; author hong; state Exp; branches; next 1.10; 1.10 date 89.09.05.22.52.47; author ong; state Exp; branches; next 1.9; 1.9 date 89.09.05.17.17.24; author mao; state C_Demo_1; branches; next 1.8; 1.8 date 89.09.02.13.45.31; author ong; state Exp; branches; next 1.7; 1.7 date 89.08.23.16.02.39; author ong; state Exp; branches; next 1.6; 1.6 date 89.08.04.14.27.19; author goh; state Exp; branches; next 1.5; 1.5 date 89.08.04.13.23.19; author goh; state Exp; branches; next 1.4; 1.4 date 89.08.01.14.39.56; author goh; state Exp; branches; next 1.3; 1.3 date 89.07.25.17.35.28; author ong; state Exp; branches; next 1.2; 1.2 date 89.07.21.11.51.58; author ong; state Exp; branches; next 1.1; 1.1 date 89.07.10.15.16.16; author ong; state Exp; branches; next ; desc @stuff to do joins @ 1.29 log @missing @ text @/* * FILE * joinpath * * DESCRIPTION * Routines to find all possible paths for processing a set of joins * */ /* RcsId("$Header: /home2/aoki/postgres/src/backend/planner/path/RCS/joinpath.c,v 1.28 1992/08/19 01:12:02 mer Exp aoki $"); */ /* * EXPORTS * find-all-join-paths */ #include #include "nodes/pg_lisp.h" #include "nodes/relation.h" #include "nodes/relation.a.h" #include "nodes/plannodes.h" #include "nodes/plannodes.a.h" #include "planner/internal.h" #include "planner/joinpath.h" #include "planner/relnode.h" #include "planner/mergeutils.h" #include "planner/hashutils.h" #include "planner/pathnode.h" #include "planner/joinutils.h" #include "planner/keys.h" #include "planner/costsize.h" extern bool _enable_hashjoin_; extern bool _enable_mergesort_; extern int testFlag; /* * find-all-join-paths * * Creates all possible ways to process joins for each of the join * relations in the list 'joinrels.' Each unique path will be included * in the join relation's 'pathlist' field. * * In postgres, n-way joins are handled left-only(permuting clauseless * joins doesn't usually win much). * * if BushyPlanFlag is true, bushy tree plans will be generated * * 'joinrels' is the list of relation entries to be joined * 'previous-level-rels' is the list of(outer) relation entries from * the previous join processing level * 'nest-level' is the current attribute nesting level * * Modifies the pathlist field of the appropriate rel node to contain * the unique join paths. * If bushy trees are considered, may modify the relid field of the * join rel nodes to flatten the lists. * * Returns nothing of interest. (?) * It does a destructive modification. */ /* .. find-all-join-paths, find-join-paths */ void find_all_join_paths(joinrels,previous_level_rels,nest_level) LispValue joinrels,previous_level_rels; int nest_level; { LispValue mergeinfo_list = LispNil; LispValue hashinfo_list = LispNil; LispValue temp_list = LispNil; LispValue path = LispNil; LispValue form_relid(); if( consp(joinrels) ) { Rel joinrel = (Rel)CAR(joinrels); List innerrelids; List outerrelids; LispValue innerrelid; LispValue outerrelid; Rel innerrel; Rel outerrel; Path bestinnerjoin; LispValue pathlist = LispNil; innerrelids = CADR(get_relids(joinrel)); outerrelids = CAR(get_relids(joinrel)); innerrelid = form_relid(innerrelids); outerrelid = form_relid(outerrelids); innerrel = get_rel(innerrelid); outerrel = get_rel(outerrelid); bestinnerjoin = best_innerjoin(get_innerjoin(innerrel), get_relids(outerrel)); if( _enable_mergesort_ ) { mergeinfo_list = group_clauses_by_order(get_clauseinfo(joinrel), CAR(get_relids(innerrel))); } if( _enable_hashjoin_ ) { hashinfo_list = group_clauses_by_hashop(get_clauseinfo(joinrel), CAR(get_relids(innerrel))); } /* need to flatten the relids list */ set_relids(joinrel, append(outerrelids,innerrelids)); /* * 1. Consider mergesort paths where both relations must be explicitly * sorted. */ if(!testFlag) { pathlist = sort_inner_and_outer(joinrel,outerrel, innerrel,mergeinfo_list); } /* 2. Consider paths where the outer relation need not be explicitly * sorted. This may include either nestloops and mergesorts where * the outer path is already ordered. */ pathlist = add_pathlist(joinrel,pathlist, match_unsorted_outer(joinrel, outerrel, innerrel, get_pathlist(outerrel), (Path)get_cheapestpath (innerrel), bestinnerjoin, mergeinfo_list)); /* 3. Consider paths where the inner relation need not be explicitly * sorted. This may include nestloops and mergesorts the actual * nestloop nodes were constructed in(match-unsorted-outer). * Thus, this call is unnecessary for higher attribute nesting * levels since index scans can't be used(all scans are on * temporaries). */ if( 1 == nest_level) { pathlist = add_pathlist(joinrel,pathlist, match_unsorted_inner(joinrel,outerrel, innerrel, get_pathlist(innerrel), mergeinfo_list)); } /* 4. Consider paths where both outer and inner relations must be * hashed before being joined. */ pathlist = add_pathlist(joinrel,pathlist, hash_inner_and_outer(joinrel,outerrel, innerrel,hashinfo_list)); set_pathlist(joinrel,pathlist); /* 'OuterJoinCost is only valid when calling(match-unsorted-inner) * with the same arguments as the previous invokation of * (match-unsorted-outer), so clear the field before going on. */ temp_list = get_pathlist(innerrel); foreach(path, temp_list) { /* * XXX * * This gross hack is to get around an apparent optimizer bug on Sparc * (or maybe it is a bug of ours?) that causes really wierd behavior. */ if(IsA(path,JoinPath)) #ifndef sparc set_outerjoincost((Path)CAR(path), (Cost) 0); #else /* DO NOT PROTOTYPE ME !!! */ sparc_bug_set_outerjoincost((Path)CAR(path), 0); #endif /* do it iff it is a join path, which is not always true, esp since the base level */ } find_all_join_paths(CDR(joinrels), previous_level_rels,nest_level); } } /* function end */ /* * best-innerjoin * * Find the cheapest index path that has already been identified by * (indexable_joinclauses) as being a possible inner path for the given * outer relation in a nestloop join. * * 'join-paths' is a list of join nodes * 'outer-relid' is the relid of the outer join relation * * Returns the pathnode of the selected path. * */ /* .. find-all-join-paths */ Path best_innerjoin(join_paths,outer_relid) LispValue join_paths,outer_relid ; { Path cheapest = (Path)NULL; LispValue join_path = LispNil; foreach(join_path, join_paths) { if (member(CAR(get_joinid((Path)CAR(join_path))),outer_relid) && ((null(cheapest) || path_is_cheaper((Path)CAR(join_path),cheapest)))) { cheapest = (Path)CAR(join_path); } } return(cheapest); } /* function end */ /* * sort-inner-and-outer * * Create mergesort join paths by explicitly sorting both the outer and * inner join relations on each available merge ordering. * * 'joinrel' is the join relation * 'outerrel' is the outer join relation * 'innerrel' is the inner join relation * 'mergeinfo-list' is a list of nodes containing info on(mergesortable) * clauses for joining the relations * * Returns a list of mergesort paths. * */ /* .. find-all-join-paths */ LispValue sort_inner_and_outer(joinrel,outerrel,innerrel,mergeinfo_list) Rel joinrel,outerrel,innerrel; List mergeinfo_list ; { LispValue ms_list = LispNil; MInfo xmergeinfo = (MInfo)NULL; MergePath temp_node = (MergePath)NULL; LispValue i = LispNil; LispValue outerkeys = LispNil; LispValue innerkeys = LispNil; LispValue merge_pathkeys = LispNil; foreach(i,mergeinfo_list) { xmergeinfo = (MInfo)CAR(i); outerkeys = extract_path_keys(joinmethod_keys((JoinMethod)xmergeinfo), get_targetlist(outerrel), OUTER); innerkeys = extract_path_keys(joinmethod_keys((JoinMethod)xmergeinfo), get_targetlist(innerrel), INNER); merge_pathkeys = new_join_pathkeys(outerkeys,get_targetlist(joinrel), joinmethod_clauses((JoinMethod)xmergeinfo)); if(testFlag) { LispValue x, y; foreach(x, get_pathlist(outerrel)) { foreach(y, get_pathlist(innerrel)) { temp_node = create_mergesort_path(joinrel, get_size(outerrel), get_size(innerrel), get_width(outerrel), get_width(innerrel), (Path)CAR(x), (Path)CAR(y), merge_pathkeys, (List)get_m_ordering(xmergeinfo), joinmethod_clauses((JoinMethod)xmergeinfo), outerkeys,innerkeys); ms_list = nappend1(ms_list,(LispValue)temp_node); } } } else { temp_node = create_mergesort_path(joinrel, get_size(outerrel), get_size(innerrel), get_width(outerrel), get_width(innerrel), (Path)get_cheapestpath(outerrel), (Path)get_cheapestpath(innerrel), merge_pathkeys, (List)get_m_ordering(xmergeinfo), joinmethod_clauses((JoinMethod)xmergeinfo), outerkeys,innerkeys); ms_list = nappend1(ms_list,(LispValue)temp_node); } } return(ms_list); } /* function end */ /* * match-unsorted-outer * * Creates possible join paths for processing a single join relation * 'joinrel' by employing either iterative substitution or * mergesorting on each of its possible outer paths(assuming that the * outer relation need not be explicitly sorted). * * 1. The inner path is the cheapest available inner path. * 2. Mergesort wherever possible. Mergesorts are considered if there * are mergesortable join clauses between the outer and inner join * relations such that the outer path is keyed on the variables * appearing in the clauses. The corresponding inner merge path is * either a path whose keys match those of the outer path(if such a * path is available) or an explicit sort on the appropriate inner * join keys, whichever is cheaper. * * 'joinrel' is the join relation * 'outerrel' is the outer join relation * 'innerrel' is the inner join relation * 'outerpath-list' is the list of possible outer paths * 'cheapest-inner' is the cheapest inner path * 'best-innerjoin' is the best inner index path(if any) * 'mergeinfo-list' is a list of nodes containing info on mergesortable * clauses * * Returns a list of possible join path nodes. * */ /* .. find-all-join-paths */ List match_unsorted_outer(joinrel,outerrel,innerrel,outerpath_list, cheapest_inner,best_innerjoin,mergeinfo_list) Rel joinrel,outerrel,innerrel; List outerpath_list; Path cheapest_inner,best_innerjoin; List mergeinfo_list ; { Path outerpath = (Path)NULL; LispValue jp_list = LispNil; LispValue temp_node = LispNil; LispValue merge_pathkeys = LispNil; Path nestinnerpath =(Path)NULL; LispValue paths = LispNil; LispValue i = LispNil; LispValue outerpath_ordering = LispNil; foreach(i,outerpath_list) { List clauses = LispNil; LispValue keyquals = LispNil; MInfo xmergeinfo = (MInfo)NULL; outerpath = (Path)CAR(i); outerpath_ordering = get_p_ordering(outerpath); if( outerpath_ordering ) { xmergeinfo = match_order_mergeinfo((MergeOrder)outerpath_ordering,mergeinfo_list); } if(xmergeinfo ) { clauses = get_clauses((JoinMethod)xmergeinfo); } if( clauses ) { keyquals = match_pathkeys_joinkeys(get_keys(outerpath), joinmethod_keys((JoinMethod)xmergeinfo), joinmethod_clauses((JoinMethod)xmergeinfo), OUTER); merge_pathkeys = new_join_pathkeys(get_keys(outerpath), get_targetlist(joinrel),clauses); } else { merge_pathkeys = get_keys(outerpath); } if(best_innerjoin && path_is_cheaper(best_innerjoin,cheapest_inner)) { nestinnerpath = best_innerjoin; } else { nestinnerpath = cheapest_inner; } if(testFlag && best_innerjoin) nestinnerpath = best_innerjoin; if (testFlag) { LispValue x; Path innerpath; List outer_relid = get_relids(outerrel); paths = LispNil; if (length(get_relids(innerrel)) > 1) { /* if join, then */ foreach (x, get_pathlist(innerrel)) { innerpath = (Path)CAR(x); paths = lispCons((LispValue)create_nestloop_path(joinrel, outerrel, outerpath, innerpath, merge_pathkeys), paths); } } else { /* if base relation, then */ foreach (x, get_innerjoin(innerrel)) { innerpath = (Path)CAR(x); if (member(CAR(get_joinid(innerpath)),outer_relid)) { paths = lispCons((LispValue)create_nestloop_path(joinrel, outerrel, outerpath, innerpath, merge_pathkeys), paths); } } } } else { paths = lispCons((LispValue)create_nestloop_path(joinrel,outerrel, outerpath,nestinnerpath, merge_pathkeys), LispNil); } if( clauses && keyquals) { bool path_is_cheaper_than_sort; LispValue varkeys = LispNil; Path mergeinnerpath = match_paths_joinkeys(nth(0,keyquals), outerpath_ordering, get_pathlist(innerrel), INNER); path_is_cheaper_than_sort = (bool) (mergeinnerpath && (get_path_cost(mergeinnerpath) < (get_path_cost(cheapest_inner) + cost_sort(nth(0,keyquals) ,get_size(innerrel), get_width(innerrel), false)))); if(!path_is_cheaper_than_sort || testFlag) { varkeys = extract_path_keys(nth(0,keyquals), get_targetlist(innerrel), INNER); } /* Keep track of the cost of the outer path used with * this ordered inner path for later processing in * (match-unsorted-inner), since it isn't a sort and * thus wouldn't otherwise be considered. */ if(path_is_cheaper_than_sort || testFlag) { set_outerjoincost(mergeinnerpath, get_path_cost(outerpath)); } else { mergeinnerpath = cheapest_inner; } if(testFlag) { LispValue x; if(mergeinnerpath) temp_node = lispCons((LispValue)create_mergesort_path(joinrel, get_size(outerrel), get_size(innerrel), get_width(outerrel), get_width(innerrel), outerpath, mergeinnerpath, merge_pathkeys, (List)get_m_ordering(xmergeinfo), nth(1,keyquals), LispNil,LispNil), paths); /* to reduce path space: any path involving explicit sort is ditched foreach(x, get_pathlist(innerrel)) { temp_node = lispCons(create_mergesort_path(joinrel, get_size(outerrel), get_size(innerrel), get_width(outerrel), get_width(innerrel), outerpath, CAR(x), merge_pathkeys, get_m_ordering(xmergeinfo), nth(1,keyquals), LispNil,varkeys), temp_node); } */ } else { temp_node = lispCons((LispValue)create_mergesort_path(joinrel, get_size(outerrel), get_size(innerrel), get_width(outerrel), get_width(innerrel), outerpath, mergeinnerpath, merge_pathkeys, (List)get_m_ordering(xmergeinfo), nth(1,keyquals), LispNil,varkeys), paths); } } else { temp_node = paths; } jp_list = nconc(jp_list,temp_node); } return(jp_list); } /* function end */ /* * match-unsorted-inner * * Find the cheapest ordered join path for a given(ordered, unsorted) * inner join path. * * Scans through each path available on an inner join relation and tries * matching its ordering keys against those of mergejoin clauses. * If 1. an appropriately-ordered inner path and matching mergeclause are * found, and * 2. sorting the cheapest outer path is cheaper than using an ordered * but unsorted outer path(as was considered in * (match-unsorted-outer)), * then this merge path is considered. * * 'joinrel' is the join result relation * 'outerrel' is the outer join relation * 'innerrel' is the inner join relation * 'innerpath-list' is the list of possible inner join paths * 'mergeinfo-list' is a list of nodes containing info on mergesortable * clauses * * Returns a list of possible merge paths. * */ /* .. find-all-join-paths */ LispValue match_unsorted_inner(joinrel,outerrel,innerrel,innerpath_list,mergeinfo_list) Rel joinrel,outerrel,innerrel; List innerpath_list,mergeinfo_list ; { Path innerpath = (Path)NULL; LispValue mp_list = LispNil; LispValue temp_node = LispNil; LispValue innerpath_ordering = LispNil; Cost temp1 = 0.0; bool temp2 = false; LispValue i = LispNil; foreach(i,innerpath_list) { MInfo xmergeinfo = (MInfo)NULL; List clauses = LispNil; LispValue keyquals = LispNil; innerpath = (Path)CAR(i); innerpath_ordering = get_p_ordering(innerpath); if( innerpath_ordering ) { xmergeinfo = match_order_mergeinfo((MergeOrder)innerpath_ordering,mergeinfo_list); } if( xmergeinfo ) { clauses = get_clauses((JoinMethod)xmergeinfo); } if( clauses ) { keyquals = match_pathkeys_joinkeys(get_keys(innerpath), joinmethod_keys((JoinMethod)xmergeinfo), joinmethod_clauses((JoinMethod)xmergeinfo), INNER); } /* (match-unsorted-outer) if it is applicable. */ /* 'OuterJoinCost was set above in */ if( clauses && keyquals) { temp1 = get_path_cost((Path)get_cheapestpath(outerrel)) + cost_sort(nth(0,keyquals), get_size(outerrel), get_width(outerrel), false); temp2 = (bool) (FLOAT_IS_ZERO(get_outerjoincost(innerpath)) || (get_outerjoincost(innerpath) > temp1)); if(temp2 || testFlag) { LispValue outerkeys = extract_path_keys(nth(0,keyquals), get_targetlist(outerrel), OUTER); LispValue merge_pathkeys = new_join_pathkeys(outerkeys,get_targetlist(joinrel),clauses); if(testFlag) { LispValue x; /* to reduce path space, all paths involving explicit sort is ditched. foreach(x, get_pathlist(outerrel)) { temp_node = lispCons(create_mergesort_path(joinrel, get_size(outerrel), get_size(innerrel), get_width(outerrel), get_width(innerrel), CAR(x), innerpath,merge_pathkeys, get_m_ordering(xmergeinfo), nth(1,keyquals), outerkeys,LispNil), LispNil); mp_list = nconc(mp_list,temp_node); } */ } else { temp_node = lispCons((LispValue)create_mergesort_path(joinrel, get_size(outerrel), get_size(innerrel), get_width(outerrel), get_width(innerrel), (Path)get_cheapestpath (outerrel), innerpath,merge_pathkeys, (List)get_m_ordering(xmergeinfo), nth(1,keyquals), outerkeys,LispNil), LispNil); mp_list = nconc(mp_list,temp_node); } } /* if temp2 */ } /* if clauses */ } return(mp_list); } /* function end */ bool EnoughMemoryForHashjoin(hashrel) Rel hashrel; { int ntuples; int tupsize; int pages; ntuples = get_size(hashrel); if (ntuples == 0) ntuples = 1000; tupsize = get_width(hashrel) + sizeof(HeapTupleData); pages = page_size(ntuples, tupsize); /* * if amount of buffer space below hashjoin threshold, * return false */ if (ceil(sqrt((double)pages)) > NBuffers) return false; return true; } /* * hash-inner-and-outer XXX HASH * * Create hashjoin join paths by explicitly hashing both the outer and * inner join relations on each available hash op. * * 'joinrel' is the join relation * 'outerrel' is the outer join relation * 'innerrel' is the inner join relation * 'hashinfo-list' is a list of nodes containing info on(hashjoinable) * clauses for joining the relations * * Returns a list of hashjoin paths. * */ /* .. find-all-join-paths */ LispValue hash_inner_and_outer(joinrel,outerrel,innerrel,hashinfo_list) Rel joinrel,outerrel,innerrel; LispValue hashinfo_list ; { /* XXX was mapCAR */ HInfo xhashinfo = (HInfo)NULL; LispValue hjoin_list = LispNil; HashPath temp_node = (HashPath)NULL; LispValue i = LispNil; LispValue outerkeys = LispNil; LispValue innerkeys = LispNil; LispValue hash_pathkeys = LispNil; foreach(i,hashinfo_list) { xhashinfo = (HInfo)CAR(i); outerkeys = extract_path_keys(get_jmkeys((JoinMethod)xhashinfo), get_targetlist(outerrel),OUTER); innerkeys = extract_path_keys(get_jmkeys((JoinMethod)xhashinfo), get_targetlist(innerrel),INNER); hash_pathkeys = new_join_pathkeys(outerkeys, get_targetlist(joinrel), get_clauses((JoinMethod)xhashinfo)); if(testFlag) { LispValue x, y; foreach(x, get_pathlist(outerrel)) { foreach(y, get_pathlist(innerrel)) { temp_node = create_hashjoin_path(joinrel, get_size(outerrel), get_size(innerrel), get_width(outerrel), get_width(innerrel), (Path)CAR(x), (Path)CAR(y), hash_pathkeys, get_hashop(xhashinfo), get_clauses((JoinMethod)xhashinfo), outerkeys,innerkeys); hjoin_list = nappend1(hjoin_list,(LispValue)temp_node); } } } else if (EnoughMemoryForHashjoin(innerrel)) { temp_node = create_hashjoin_path(joinrel, get_size(outerrel), get_size(innerrel), get_width(outerrel), get_width(innerrel), (Path)get_cheapestpath(outerrel), (Path)get_cheapestpath(innerrel), hash_pathkeys, get_hashop(xhashinfo), get_clauses((JoinMethod)xhashinfo), outerkeys,innerkeys); hjoin_list = nappend1(hjoin_list,(LispValue)temp_node); } } return(hjoin_list); } /* function end */ /* * form_relid * * correctly form a relid: if it is a base relation relid is a * integer, if it is a join relation relid is a list of integers */ LispValue form_relid(relids) LispValue relids; { if(length(relids) == 1) return(CAR(relids)); else return(relids); } @ 1.28 log @fix to prevent hashjoins when there isn't enough memory @ text @d9 1 a9 1 /* RcsId("$Header: /home/postgres/hong/postgres/src/planner/path/RCS/joinpath.c,v 1.27 1992/07/09 07:33:23 joey Exp hong $"); */ d16 2 @ 1.27 log @remove a clueless comment I added long ago @ text @d9 1 a9 1 /* RcsId("$Header: /private/joey/pg/src/planner/path/RCS/joinpath.c,v 1.26 1992/03/31 23:13:08 mer Exp joey $"); */ d666 21 d752 1 a752 1 else { @ 1.26 log @change accessor functions into macros @ text @d9 1 a9 1 /* RcsId("$Header: /users/mer/pg/src/planner/path/RCS/joinpath.c,v 1.25 1992/01/22 23:13:37 joey Exp mer $"); */ a160 9 /* Add the following: ** If costing all pullups, the repeat the above 4 steps for ** all permutations of one-step pullups. ** for each join on path do: ** try to pull clauses up through join; ** call function to order clauses in join restriction ** -- JMH 1/8/92 */ @ 1.25 log @added some comments for my future edification on expensive functions @ text @d9 1 a9 1 /* RcsId("$Header: /users/joey/pg/src/planner/path/RCS/joinpath.c,v 1.24 1991/11/27 11:41:51 postgres Exp $"); */ d131 1 a131 1 get_cheapestpath d310 2 a311 2 get_cheapestpath(outerrel), get_cheapestpath(innerrel), d615 1 a615 1 temp1 = get_path_cost(get_cheapestpath(outerrel)) + d658 1 a658 2 get_cheapestpath (outerrel), d746 2 a747 2 get_cheapestpath(outerrel), get_cheapestpath(innerrel), @ 1.24 log @better bugfix which won't break prototypes. @ text @d9 1 a9 1 /* RcsId("$Header: RCS/joinpath.c,v 1.23 91/11/27 10:44:42 postgres Exp Locker: postgres $"); */ d161 9 @ 1.23 log @Gross hack to fix apparent compiler error on Sparcstation. @ text @d9 1 a9 1 /* RcsId("$Header: RCS/joinpath.c,v 1.22 91/11/17 20:39:50 mer Exp Locker: postgres $"); */ a177 4 #ifdef _PROTOTYPES_ #define UNDEF_PROTOS #undef _PROTOTYPES_ #endif d179 5 a183 4 set_outerjoincost((Path)CAR(path), LispNil); /* XXX */ #ifdef UNDEF_PROTOS #define _PROTOTYPES_ @ 1.22 log @prototyping @ text @d9 1 a9 1 /* RcsId("$Header: /users/mer/postgres/src/planner/path/RCS/joinpath.c,v 1.21 1991/11/15 16:27:08 hong Exp mer $"); */ d170 12 d183 6 a188 1 set_outerjoincost((Path)CAR(path),(Cost)0); @ 1.21 log @planner prototyping @ text @d9 1 a9 1 /* RcsId("$Header: RCS/joinpath.c,v 1.20 91/11/02 21:42:25 hong Exp $"); */ d277 1 a277 1 ms_list = nappend1(ms_list,temp_node); d294 1 a294 1 ms_list = nappend1(ms_list,temp_node); d400 1 a400 1 paths = lispCons(create_nestloop_path(joinrel, outerrel, d411 1 a411 1 paths = lispCons(create_nestloop_path(joinrel, outerrel, d420 1 a420 1 paths = lispCons(create_nestloop_path(joinrel,outerrel, d468 1 a468 1 temp_node = lispCons(create_mergesort_path(joinrel, d499 1 a499 1 temp_node = lispCons(create_mergesort_path(joinrel, d630 1 a630 1 temp_node = lispCons(create_mergesort_path(joinrel, d714 1 a714 1 hjoin_list = nappend1(hjoin_list,temp_node); d730 1 a730 1 hjoin_list = nappend1(hjoin_list,temp_node); @ 1.20 log @cleaned up bushy tree plan generation code. @ text @d9 1 a9 1 /* RcsId("$Header: RCS/joinpath.c,v 1.19 91/05/29 23:10:43 hong Exp Locker: hong $"); */ d171 1 a171 1 set_outerjoincost(CAR(path),LispNil); d204 2 a205 2 if (member(CAR(get_joinid(CAR(join_path))),outer_relid) && ((null(cheapest) || path_is_cheaper(CAR(join_path),cheapest)))) { d233 2 a234 1 LispValue joinrel,outerrel,innerrel,mergeinfo_list ; d248 1 a248 1 extract_path_keys(joinmethod_keys(xmergeinfo), d253 1 a253 1 extract_path_keys(joinmethod_keys(xmergeinfo), d259 1 a259 1 joinmethod_clauses(xmergeinfo)); d270 2 a271 2 CAR(x), CAR(y), d273 2 a274 2 get_m_ordering(xmergeinfo), joinmethod_clauses(xmergeinfo), d290 2 a291 2 get_m_ordering(xmergeinfo), joinmethod_clauses(xmergeinfo), d359 1 a359 1 match_order_mergeinfo(outerpath_ordering,mergeinfo_list); d363 1 a363 1 clauses = get_clauses(xmergeinfo); d369 2 a370 2 joinmethod_keys(xmergeinfo), joinmethod_clauses(xmergeinfo), d442 1 a442 1 LispNil)))); d476 1 a476 1 get_m_ordering(xmergeinfo), d478 1 a478 1 LispNil,LispNil), d507 1 a507 1 get_m_ordering(xmergeinfo), d509 1 a509 1 LispNil,varkeys), d574 1 a574 1 match_order_mergeinfo(innerpath_ordering,mergeinfo_list); d578 1 a578 1 clauses = get_clauses(xmergeinfo); d584 2 a585 2 joinmethod_keys(xmergeinfo), joinmethod_clauses(xmergeinfo), d594 1 a594 1 get_width(outerrel), LispNil); d638 1 a638 1 get_m_ordering(xmergeinfo), d689 1 a689 1 extract_path_keys(get_jmkeys(xhashinfo), d692 1 a692 1 extract_path_keys(get_jmkeys(xhashinfo), d697 1 a697 1 get_clauses(xhashinfo)); d708 2 a709 2 CAR(x), CAR(y), d712 1 a712 1 get_clauses(xhashinfo), d728 1 a728 1 get_clauses(xhashinfo), @ 1.19 log @a minor change for my test @ text @d9 1 a9 1 /* RcsId("$Header: RCS/joinpath.c,v 1.18 91/05/08 15:09:12 hong Exp Locker: hong $"); */ d45 1 a45 1 * In postgres, n-way joins are handled left-only (permuting clauseless d48 1 a48 1 * In xprs, bushy-tree joins are cosidered for parallelism's sake d51 1 a51 1 * 'previous-level-rels' is the list of (outer) relation entries from d67 1 a67 1 find_all_join_paths (joinrels,previous_level_rels,nest_level) a74 1 #ifdef _xprs_ a75 1 #endif /* _xprs_ */ d77 10 d88 10 a97 26 if ( consp (joinrels) ) { LispValue joinrel = CAR (joinrels); #ifdef _xprs_ LispValue innerrelids = CADR (get_relids (joinrel)); LispValue outerrelids = CAR (get_relids (joinrel)); LispValue innerrelid = /* grow bushy plan trees */ form_relid (innerrelids); LispValue outerrelid = form_relid (outerrelids); Rel innerrel = rel_member (innerrelids,previous_level_rels); Rel outerrel = rel_member (outerrelids,previous_level_rels); #else /* _xprs_ */ LispValue innerrelid = /* grow left-only plan trees */ last_element (get_relids (joinrel)); Rel innerrel = get_rel (innerrelid); Rel outerrel = rel_member (LispRemove (innerrelid, get_relids (joinrel)), previous_level_rels); #endif /* _xprs_ */ Path bestinnerjoin = best_innerjoin(get_innerjoin (innerrel), get_relids(outerrel)); LispValue pathlist = LispNil; if ( _enable_mergesort_ ) { d99 2 a100 2 group_clauses_by_order (get_clauseinfo (joinrel), CAR(get_relids (innerrel))); d103 1 a103 1 if ( _enable_hashjoin_ ) { d105 2 a106 2 group_clauses_by_hashop(get_clauseinfo (joinrel), CAR(get_relids (innerrel))); d109 2 a110 3 #ifdef _xprs_ set_relids (joinrel, append (outerrelids,innerrelids)); #endif /* _xprs_ */ d112 2 a113 2 /* 1. Consider mergesort paths where both relations must be explicitly d116 4 a119 4 if (!testFlag) pathlist = sort_inner_and_outer (joinrel,outerrel, innerrel,mergeinfo_list); d138 1 a138 1 * nestloop nodes were constructed in (match-unsorted-outer). d140 1 a140 1 * levels since index scans can't be used (all scans are on d144 1 a144 1 if ( 1 == nest_level) { d146 1 a146 1 add_pathlist (joinrel,pathlist, d158 1 a158 1 add_pathlist (joinrel,pathlist, d162 1 a162 1 set_pathlist (joinrel,pathlist); d164 1 a164 1 /* 'OuterJoinCost is only valid when calling (match-unsorted-inner) d169 3 a171 3 foreach (path, temp_list) { if (IsA(path,JoinPath)) set_outerjoincost (CAR(path),LispNil); d175 1 a175 1 find_all_join_paths (CDR (joinrels), d197 1 a197 1 best_innerjoin (join_paths,outer_relid) d203 3 a205 4 foreach (join_path, join_paths) { if ( member(CAR(get_joinid(CAR(join_path))),outer_relid) && ((null (cheapest) || path_is_cheaper(CAR(join_path),cheapest)) || testFlag)) { d222 1 a222 1 * 'mergeinfo-list' is a list of nodes containing info on (mergesortable) d232 1 a232 1 sort_inner_and_outer (joinrel,outerrel,innerrel,mergeinfo_list) d243 1 a243 1 foreach (i,mergeinfo_list) { d247 2 a248 2 extract_path_keys (joinmethod_keys(xmergeinfo), get_targetlist (outerrel), d252 1 a252 1 extract_path_keys (joinmethod_keys(xmergeinfo), d257 2 a258 2 new_join_pathkeys (outerkeys,get_targetlist(joinrel), joinmethod_clauses (xmergeinfo)); d260 1 a260 1 if (testFlag) { d262 2 a263 2 foreach (x, get_pathlist(outerrel)) { foreach (y, get_pathlist(innerrel)) { d265 4 a268 4 get_size (outerrel), get_size (innerrel), get_width (outerrel), get_width (innerrel), d282 4 a285 4 get_size (outerrel), get_size (innerrel), get_width (outerrel), get_width (innerrel), d305 1 a305 1 * mergesorting on each of its possible outer paths (assuming that the d313 1 a313 1 * either a path whose keys match those of the outer path (if such a d322 1 a322 1 * 'best-innerjoin' is the best inner index path (if any) d333 1 a333 1 match_unsorted_outer (joinrel,outerrel,innerrel,outerpath_list, a339 2 /* XXX was mapcan */ d354 1 a354 1 outerpath_ordering = get_p_ordering (outerpath); d356 1 a356 1 if ( outerpath_ordering ) { d358 1 a358 1 match_order_mergeinfo (outerpath_ordering,mergeinfo_list); d361 2 a362 2 if (xmergeinfo ) { clauses = get_clauses (xmergeinfo); d365 1 a365 1 if ( clauses ) { d367 3 a369 3 match_pathkeys_joinkeys (get_keys (outerpath), joinmethod_keys (xmergeinfo), joinmethod_clauses (xmergeinfo), d372 2 a373 2 new_join_pathkeys (get_keys (outerpath), get_targetlist (joinrel),clauses); d376 1 a376 1 merge_pathkeys = get_keys (outerpath); d379 1 a379 1 if (best_innerjoin && d387 1 a387 1 if (testFlag && best_innerjoin) d390 34 a423 5 paths = lispCons (create_nestloop_path (joinrel,outerrel, outerpath,nestinnerpath, merge_pathkeys), LispNil); d425 1 a425 1 if ( clauses && keyquals) { d430 1 a430 1 match_paths_joinkeys (nth (0,keyquals), d432 1 a432 1 get_pathlist (innerrel), d436 3 a438 3 (get_path_cost (mergeinnerpath) < (get_path_cost (cheapest_inner) + cost_sort (nth (0,keyquals) d442 1 a442 1 if (!path_is_cheaper_than_sort || testFlag) { d444 2 a445 2 extract_path_keys (nth (0,keyquals), get_targetlist (innerrel), d457 2 a458 2 set_outerjoincost (mergeinnerpath, get_path_cost (outerpath)); d464 1 a464 1 if (testFlag) { d466 1 a466 1 if (mergeinnerpath) d468 4 a471 4 get_size (outerrel), get_size (innerrel), get_width (outerrel), get_width (innerrel), d476 1 a476 1 nth (1,keyquals), d479 3 a481 1 foreach (x, get_pathlist(innerrel)) { d483 4 a486 4 get_size (outerrel), get_size (innerrel), get_width (outerrel), get_width (innerrel), d491 1 a491 1 nth (1,keyquals), d495 1 d499 4 a502 4 get_size (outerrel), get_size (innerrel), get_width (outerrel), get_width (innerrel), d507 1 a507 1 nth (1,keyquals), d525 1 a525 1 * Find the cheapest ordered join path for a given (ordered, unsorted) d533 1 a533 1 * but unsorted outer path (as was considered in d551 1 a551 1 match_unsorted_inner (joinrel,outerrel,innerrel,innerpath_list,mergeinfo_list) d565 1 a565 1 foreach (i,innerpath_list) { d570 2 a571 2 innerpath_ordering = get_p_ordering (innerpath); if ( innerpath_ordering ) { d573 1 a573 1 match_order_mergeinfo (innerpath_ordering,mergeinfo_list); d576 2 a577 2 if ( xmergeinfo ) { clauses = get_clauses (xmergeinfo); d580 1 a580 1 if ( clauses ) { d582 3 a584 3 match_pathkeys_joinkeys (get_keys (innerpath), joinmethod_keys (xmergeinfo), joinmethod_clauses (xmergeinfo), d590 1 a590 1 if ( clauses && keyquals) { d598 1 a598 1 if (temp2 || testFlag) { d601 2 a602 2 extract_path_keys(nth (0,keyquals), get_targetlist (outerrel), d605 1 a605 1 new_join_pathkeys (outerkeys,get_targetlist (joinrel),clauses); d607 1 a607 1 if (testFlag) { d609 3 a611 1 foreach (x, get_pathlist(outerrel)) { d613 4 a616 4 get_size (outerrel), get_size (innerrel), get_width (outerrel), get_width (innerrel), d620 1 a620 1 nth (1,keyquals), d626 1 d630 4 a633 4 get_size (outerrel), get_size (innerrel), get_width (outerrel), get_width (innerrel), d638 1 a638 1 nth (1,keyquals), d661 1 a661 1 * 'hashinfo-list' is a list of nodes containing info on (hashjoinable) d671 1 a671 1 hash_inner_and_outer (joinrel,outerrel,innerrel,hashinfo_list) d689 1 a689 1 get_targetlist (outerrel),OUTER); d692 1 a692 1 get_targetlist (innerrel),INNER); d696 1 a696 1 get_clauses (xhashinfo)); d698 1 a698 1 if (testFlag) { d700 2 a701 2 foreach (x, get_pathlist(outerrel)) { foreach (y, get_pathlist(innerrel)) { d703 4 a706 4 get_size (outerrel), get_size (innerrel), get_width (outerrel), get_width (innerrel), d710 2 a711 2 get_hashop (xhashinfo), get_clauses (xhashinfo), d719 6 a724 6 get_size (outerrel), get_size (innerrel), get_width (outerrel), get_width (innerrel), get_cheapestpath (outerrel), get_cheapestpath (innerrel), d726 2 a727 2 get_hashop (xhashinfo), get_clauses (xhashinfo), a735 1 #ifdef _xprs_ d739 2 d744 1 a744 1 form_relid (relids) d747 2 a748 2 if (length (relids) == 1) return (CAR (relids)); d750 1 a750 1 return (relids); a751 1 #endif /* _xprs_ */ @ 1.18 log @added some special code for wei's experiments. fixed a bug in generating mergejoin plans @ text @d9 1 a9 1 /* RcsId("$Header: RCS/joinpath.c,v 1.17 91/04/25 04:15:42 hong Exp Locker: hong $"); */ d126 1 @ 1.17 log @only generate hashjoin plans that hash on the smaller relation @ text @d9 1 a9 1 /* RcsId("$Header: RCS/joinpath.c,v 1.16 91/04/24 19:42:26 kemnitz Exp Locker: hong $"); */ d34 1 d212 1 a212 1 if ( same(get_joinid(CAR(join_path)),outer_relid) d214 1 a214 1 || path_is_cheaper(CAR(join_path),cheapest)))) { d269 22 a290 1 temp_node = create_mergesort_path(joinrel, d303 1 d398 3 a405 1 d424 1 a424 1 if (!path_is_cheaper_than_sort) { d438 1 a438 1 if(path_is_cheaper_than_sort) { d446 31 d489 1 d577 1 a577 1 if (temp2) { d586 19 d619 1 a659 1 int outerpages, innerpages; d674 33 a706 16 outerpages = page_size(get_size(outerrel), get_width(outerrel)); innerpages = page_size(get_size(innerrel), get_width(innerrel)); if (length(get_relids(innerrel)) > 1 || outerpages >= innerpages) { temp_node = create_hashjoin_path(joinrel, get_size (outerrel), get_size (innerrel), get_width (outerrel), get_width (innerrel), get_cheapestpath (outerrel), get_cheapestpath (innerrel), hash_pathkeys, get_hashop (xhashinfo), get_clauses (xhashinfo), outerkeys,innerkeys); hjoin_list = nappend1(hjoin_list,temp_node); } @ 1.16 log @got rid of stupid "null()". @ text @d9 1 a9 1 /* RcsId("$Header: RCS/joinpath.c,v 1.15 90/10/16 11:09:53 choi Exp Locker: kemnitz $"); */ d583 1 d598 16 a613 12 temp_node = create_hashjoin_path(joinrel, get_size (outerrel), get_size (innerrel), get_width (outerrel), get_width (innerrel), get_cheapestpath (outerrel), get_cheapestpath (innerrel), hash_pathkeys, get_hashop (xhashinfo), get_clauses (xhashinfo), outerkeys,innerkeys); hjoin_list = nappend1(hjoin_list,temp_node); @ 1.15 log @changed remove() to LispRemove(). (posix compliance) @ text @d9 1 a9 1 /* RcsId("$Header: RCS/joinpath.c,v 1.14 90/09/25 16:35:47 kemnitz Exp Locker: choi $"); */ d517 1 a517 1 temp2 = (bool) (null(get_outerjoincost(innerpath)) @ 1.14 log @Updating from revision 1.13 to revision 1.14 @ text @d9 1 a9 1 /* RcsId("$Header: RCS/joinpath.c,v 1.14 90/08/14 11:09:56 cimarron Exp $"); */ d94 1 a94 1 Rel outerrel = rel_member (remove @ 1.13 log @fixed indexscan in mergesort @ text @d9 1 a9 1 /* RcsId("$Header: RCS/joinpath.c,v 1.12 89/10/13 17:59:20 hong Exp Locker: hong $"); */ d16 6 a21 1 #include "pg_lisp.h" a22 4 #include "relation.h" #include "relation.a.h" #include "plannodes.h" #include "plannodes.a.h" @ 1.12 log @some fixes for mergejoins @ text @d9 1 a9 1 /* RcsId("$Header: RCS/joinpath.c,v 1.11 89/09/29 14:42:28 hong Exp Locker: hong $"); */ a329 3 MInfo xmergeinfo = (MInfo)NULL; List clauses = LispNil; LispValue keyquals = LispNil; d337 3 d428 1 a428 1 outerpath_ordering, a479 1 MInfo xmergeinfo = (MInfo)NULL; a480 2 List clauses = LispNil; LispValue keyquals = LispNil; d487 3 d536 1 a536 1 innerpath_ordering, @ 1.11 log @added in bushy tree stuffs. @ text @d9 1 a9 1 /* RcsId("$Header: RCS/joinpath.c,v 1.10 89/09/05 22:52:47 ong Exp Locker: hong $"); */ d243 1 a243 1 CInfo xmergeinfo = (CInfo)NULL; d251 1 a251 1 xmergeinfo = (CInfo)CAR(i); d275 1 a275 1 get_mergesortorder(xmergeinfo), d330 2 a331 2 CInfo xmergeinfo = (CInfo)NULL; Expr clauses = (Expr)NULL; d349 1 a349 1 clauses = get_clause (xmergeinfo); d392 2 a393 2 (get_cost (mergeinnerpath) < (get_cost (cheapest_inner) + d414 1 a414 1 get_cost (outerpath)); d480 1 a480 1 CInfo xmergeinfo = (CInfo)NULL; d482 1 a482 1 Expr clauses = (Expr)NULL; d498 1 a498 1 clauses = get_clause (xmergeinfo); d512 1 a512 1 temp1 = get_cost(get_cheapestpath(outerrel)) + @ 1.10 log @IMPORTANT: fixes for hermes to work, o/w fp stack blows @ text @d9 1 a9 1 /* RcsId("$Header: RCS/joinpath.c,v 1.8 89/09/02 13:45:31 ong Exp $"); */ d43 1 a43 1 * In reality, n-way joins are handled left-only (permuting clauseless d46 2 d55 2 d73 3 d77 1 d80 10 d97 1 d115 3 d612 17 @ 1.9 log @Working version of C-only demo @ text @d9 1 a9 1 /* RcsId("$Header: RCS/joinpath.c,v 1.7 89/08/23 16:02:39 ong Exp Locker: ong $"); */ d29 1 @ 1.8 log @#included costsize.h @ text @a28 1 #include "planner/costsize.h" @ 1.7 log @planner supports all but rules and mergesort @ text @d9 1 a9 1 /* RcsId("$Header: /n/postgres/a/postgres/ong/postgres/src/planner/path/RCS/joinpath.c,v 1.6 89/08/04 14:27:19 goh Exp $"); */ d29 1 @ 1.6 log @reorganised header files @ text @a0 2 d9 1 a9 1 /* RcsId("$Header: joinpath.c,v 1.5 89/08/04 13:23:19 goh Locked $"); */ d78 1 a78 1 LispValue bestinnerjoin = best_innerjoin(get_innerjoin d86 1 a86 1 get_relid (innerrel)); d90 3 a92 3 hashinfo_list = group_clauses_by_hashop(get_clauseinfo (joinrel), get_relid (innerrel)); d94 1 a96 1 d103 1 a103 1 a150 1 d153 4 a156 1 set_outerjoincost (path,LispNil); d179 1 a179 1 LispValue d183 11 a193 12 /* XXX - let form, maybe incorrect */ LispValue cheapest = LispNil; LispValue join_path = LispNil; foreach (join_path, join_paths) { if ( same(get_joinid(join_path),outer_relid) && ((null (cheapest) || path_is_cheaper(join_path,cheapest)))) { cheapest = join_path; } } return(cheapest); d220 9 a228 2 LispValue xmergeinfo = LispNil; MergePath temp_node ; d230 4 a233 1 foreach (xmergeinfo,mergeinfo_list) { d235 4 a238 4 LispValue outerkeys = extract_path_keys (joinmethod_keys(xmergeinfo), get_targetlist (outerrel), OUTER); d240 4 a243 9 LispValue innerkeys = extract_path_keys (joinmethod_keys(xmergeinfo), get_targetlist(innerrel), INNER); LispValue merge_pathkeys = new_join_pathkeys (outerkeys,get_targetlist(joinrel), joinmethod_clauses (xmergeinfo)); d304 11 a314 9 List outerpath; LispValue jp_list = LispNil; LispValue temp_node = LispNil; CInfo xmergeinfo; Expr clauses ; LispValue keyquals = LispNil; LispValue merge_pathkeys = LispNil; Path nestinnerpath; LispValue paths = LispNil; d316 12 a327 3 foreach(outerpath,outerpath_list) { LispValue outerpath_ordering = get_p_ordering ((Path)CAR(outerpath)); d329 88 a416 8 if ( outerpath_ordering ) { xmergeinfo = match_order_mergeinfo (outerpath_ordering,mergeinfo_list); } if (xmergeinfo ) { clauses = get_clause (xmergeinfo); } a417 91 if ( clauses ) { keyquals = match_pathkeys_joinkeys (get_keys (outerpath), joinmethod_keys (xmergeinfo), joinmethod_clauses (xmergeinfo), OUTER); if ( clauses ) { merge_pathkeys = new_join_pathkeys (get_keys (outerpath), get_targetlist (joinrel),clauses); } else { merge_pathkeys = get_keys (outerpath); } if (best_innerjoin && path_is_cheaper(best_innerjoin,cheapest_inner)) { nestinnerpath = best_innerjoin; } else { nestinnerpath = cheapest_inner; } paths = lispCons (create_nestloop_path (joinrel,outerrel, outerpath,nestinnerpath, merge_pathkeys), LispNil); if ( clauses && keyquals) { bool path_is_cheaper_than_sort; LispValue varkeys = LispNil; Path mergeinnerpath = match_paths_joinkeys (nth (0,keyquals), outerpath_ordering, get_pathlist (innerrel), INNER); path_is_cheaper_than_sort = (bool) (mergeinnerpath && (get_cost (mergeinnerpath) < (get_cost (cheapest_inner) + cost_sort (nth (0,keyquals) ,get_size(innerrel), get_width(innerrel), LispNil)))); if (!path_is_cheaper_than_sort) { varkeys = extract_path_keys (nth (0,keyquals), get_targetlist (innerrel), INNER); } /* Keep track of the cost of the outer path used with * this ordered inner path for later processing in * (match-unsorted-inner), since it isn't a sort and * thus wouldn't otherwise be considered. */ if(path_is_cheaper_than_sort) { set_outerjoincost (mergeinnerpath, get_cost (outerpath)); } else { mergeinnerpath = cheapest_inner; } temp_node = lispCons(create_mergesort_path(joinrel, get_size (outerrel), get_size (innerrel), get_width (outerrel), get_width (innerrel), outerpath, mergeinnerpath, merge_pathkeys, outerpath_ordering, nth (1,keyquals), LispNil,varkeys), paths); } else { temp_node = paths; } jp_list = nconc(jp_list,temp_node); } } return(jp_list); d450 2 a451 1 LispValue joinrel,outerrel,innerrel,innerpath_list,mergeinfo_list ; d454 10 a463 1 /* XXX was mapcan */ d465 54 a518 9 LispValue innerpath = LispNil; LispValue mp_list = LispNil; LispValue temp_node = LispNil; CInfo xmergeinfo; LispValue innerpath_ordering = get_ordering (innerpath); Expr clauses ; LispValue keyquals = LispNil; Cost temp1 ; bool temp2 ; d520 5 a524 51 if ( innerpath_ordering ) { xmergeinfo = match_order_mergeinfo (innerpath_ordering,mergeinfo_list); } if ( xmergeinfo ) { clauses = get_clause (xmergeinfo); } if ( clauses ) { keyquals = match_pathkeys_joinkeys (get_keys (innerpath), joinmethod_keys (xmergeinfo), joinmethod_clauses (xmergeinfo), INNER); } temp1 = get_cost(get_cheapestpath(outerrel)) + cost_sort(nth(0,keyquals), get_size(outerrel), get_width(outerrel), LispNil); temp2 = (bool) (null(get_outerjoincost(innerpath)) || (get_outerjoincost(innerpath) > temp1)); if ( clauses /* 'OuterJoinCost was set above in */ && keyquals /* (match-unsorted-outer) if it is applicable. */ && temp2) { LispValue outerkeys = extract_path_keys(nth (0,keyquals), get_targetlist (outerrel), OUTER); LispValue merge_pathkeys = new_join_pathkeys (outerkeys,get_targetlist (joinrel),clauses); temp_node = lispCons(create_mergesort_path(joinrel, get_size (outerrel), get_size (innerrel), get_width (outerrel), get_width (innerrel), get_cheapestpath(outerrel), innerpath,merge_pathkeys, innerpath_ordering, nth (1,keyquals), outerkeys,LispNil), LispNil); mp_list = nconc(mp_list,temp_node); } return(mp_list); d526 1 a526 1 d547 2 a548 1 LispValue joinrel,outerrel,innerrel,hashinfo_list ; d550 38 a587 33 /* XXX was mapCAR */ LispValue xhashinfo = LispNil; LispValue hjoin_list = LispNil; HashPath temp_node; foreach(xhashinfo,hashinfo_list) { LispValue outerkeys = extract_path_keys(joinmethod_keys(xhashinfo), get_targetlist (outerrel),OUTER); LispValue innerkeys = extract_path_keys(joinmethod_keys(xhashinfo), get_targetlist (innerrel),INNER); LispValue hash_pathkeys = new_join_pathkeys(outerkeys, get_targetlist(joinrel), joinmethod_clauses (xhashinfo)); temp_node = create_hashjoin_path(joinrel, get_size (outerrel), get_size (innerrel), get_width (outerrel), get_width (innerrel), get_cheapestpath (outerrel), get_cheapestpath (innerrel), hash_pathkeys, get_hashjoinoperator (xhashinfo), joinmethod_clauses (xhashinfo), outerkeys,innerkeys); hjoin_list = nappend1(hjoin_list,temp_node); } return(hjoin_list); @ 1.5 log @checkin for retrieve (x.all) @ text @d11 1 a11 1 /* RcsId("$Header: joinpath.c,v 1.4 89/08/01 14:39:56 goh Locked $"); */ d19 1 a19 1 #include "internal.h" d24 7 a30 9 #include "joinpath.h" #include "relnode.h" #include "mergeutils.h" #include "hashutils.h" #include "pathnode.h" #include "joinutils.h" #define OUTER 1 /* These should be moved */ #define INNER 0 @ 1.4 log @retrieve (x=1) checkin @ text @d11 1 a11 1 /* RcsId("$Header: joinpath.c,v 1.3 89/07/25 17:35:28 ong Exp $"); */ d314 1 a314 1 get_p_ordering ((Path)Contents(outerpath)); @ 1.3 log @Phase III @ text @d11 1 a11 1 /* RcsId("$Header: joinpath.c,v 1.2 89/07/21 11:51:58 ong Locked $"); */ d89 1 a89 1 group_clauses_by_order (get_clause_info (joinrel), d118 1 a118 1 get_cheapest_path d230 1 a230 1 get_tlist (outerrel), d235 1 a235 1 get_tlist(innerrel), d239 1 a239 1 new_join_pathkeys (outerkeys,get_tlist(joinrel), d247 2 a248 2 get_cheapest_path(outerrel), get_cheapest_path(innerrel), d250 1 a250 1 mergeinfo_ordering(xmergeinfo), d292 1 a292 1 LispValue d295 4 a298 2 LispValue joinrel,outerrel,innerrel,outerpath_list, cheapest_inner,best_innerjoin,mergeinfo_list ; d302 1 a302 1 LispValue outerpath = LispNil; d309 1 a309 1 LispValue nestinnerpath = LispNil; d313 2 a314 1 LispValue outerpath_ordering = get_ordering (outerpath); d335 1 a335 1 get_tlist (joinrel),clauses); d350 4 a353 3 list (create_nestloop_path (joinrel,outerrel, outerpath,nestinnerpath, merge_pathkeys)); d356 1 a356 1 if ( and (clauses,keyquals) ) { d376 1 a376 1 get_tlist (innerrel), d395 1 a395 1 temp_node = cons(create_mergesort_path(joinrel, d406 1 a406 1 paths); d480 2 a481 2 temp1 = get_cost(get_cheapest_path(outerrel)) + sort_cost(nth(0,keyquals), get_size(outerrel), d493 1 a493 1 get_tlist (outerrel), d496 1 a496 1 new_join_pathkeys (outerkeys,get_tlist (joinrel),clauses); d498 11 a508 10 temp_node = list(create_mergesort_path(joinrel, get_size (outerrel), get_size (innerrel), get_width (outerrel), get_width (innerrel), get_cheapest_path (outerrel), innerpath,merge_pathkeys, innerpath_ordering, nth (1,keyquals), outerkeys,LispNil)); d547 1 a547 1 get_tlist (outerrel),OUTER); d550 1 a550 1 get_tlist (innerrel),INNER); d553 1 a553 1 get_tlist(joinrel), d561 2 a562 2 get_cheapest_path (outerrel), get_cheapest_path (innerrel), d564 1 a564 1 hashinfo_op (xhashinfo), @ 1.2 log @Phase II checkin. NOTE: mergeinfo and hashinfo nodes have been merged in the generic Class defintion of CInfo nodes. @ text @d2 1 d11 1 a11 1 /* RcsId("$Header: joinpath.c,v 1.1 89/07/10 15:16:16 ong Locked $"); */ d64 1 a64 1 *find_all_join_paths (joinrels,previous_level_rels,nest_level) d95 1 a95 1 group_clauses_by_hashop(get_clause_info (joinrel), d356 1 a356 1 LispValue mergeinnerpath = @ 1.1 log @Initial revision @ text @d10 1 a10 1 /* RcsId("$Header: joinpath.c,v 1.1 89/04/27 21:04:20 ong Locked $"); */ d17 1 a17 1 d19 10 a28 1 #include "pg_lisp.h" d30 1 a30 1 #define OUTER 1 d33 2 a34 2 extern int _enable_hashjoin_; extern int _enable_mergesort_; a35 5 extern LispValue best_innerjoin(); extern LispValue sort_inner_and_outer(); extern LispValue match_unsorted_outer(); extern LispValue match_unsorted_inner(); extern LispValue hash_inner_and_outer(); d37 1 d55 3 a57 1 * d62 4 a65 3 LispValue find_all_join_paths (joinrels,previous_level_rels,nest_level) LispValue joinrels,previous_level_rels,nest_level ; d73 1 a73 1 LispValue joinrel = car (joinrels); d76 2 a77 2 LispValue innerrel = get_rel (innerrelid); LispValue outerrel = rel_member (remove d159 1 a159 1 find_all_join_paths (cdr (joinrels), d223 1 a223 1 LispValue temp_node = LispNil; d302 2 a303 2 LispValue xmergeinfo = LispNil; LispValue clauses = LispNil; d318 1 a318 1 clauses = joinmethod_clauses (xmergeinfo); d352 1 a352 1 LispValue path_is_cheaper_than_sort = LispNil; d361 7 a367 7 mergeinnerpath && (get_cost (mergeinnerpath) < (get_cost (cheapest_inner) + cost_sort (nth (0,keyquals) ,get_size(innerrel), get_width(innerrel), LispNil))); d451 1 a451 1 LispValue xmergeinfo = LispNil; d453 1 a453 1 LispValue clauses = LispNil; d455 2 a456 2 LispValue temp1 = LispNil; LispValue temp2 = LispNil; d464 1 a464 1 clauses = joinmethod_clauses (xmergeinfo); d479 2 a480 2 temp2 = null(get_outerjoincost(innerpath)) || (get_outerjoincost(innerpath) > temp1); d532 1 a532 1 /* XXX was mapcar */ d536 1 a536 1 LispValue temp_node = LispNil; @