head 1.32; access; symbols Version_2_1:1.17 C_Demo_1:1.11 Retrieve_x_qual:1.7 Retrieve_x_all:1.6 Retrieve_x_1:1.5; locks; strict; comment @ * @; 1.32 date 92.07.12.10.57.31; author joey; state Exp; branches; next 1.31; 1.31 date 92.07.08.04.57.02; author joey; state Exp; branches; next 1.30; 1.30 date 92.03.31.23.13.02; author mer; state Exp; branches; next 1.29; 1.29 date 91.11.17.20.39.50; author mer; state Exp; branches; next 1.28; 1.28 date 91.11.15.16.27.02; author hong; state Exp; branches; next 1.27; 1.27 date 91.11.08.00.21.06; author mer; state Exp; branches; next 1.26; 1.26 date 91.11.07.22.00.32; author mer; state Exp; branches; next 1.25; 1.25 date 91.10.16.23.05.31; author mer; state Exp; branches; next 1.24; 1.24 date 91.08.23.16.58.30; author kemnitz; state Exp; branches; next 1.23; 1.23 date 91.06.21.17.43.33; author hong; state Exp; branches; next 1.22; 1.22 date 91.05.29.23.49.54; author hong; state Exp; branches; next 1.21; 1.21 date 91.05.23.18.29.13; author kemnitz; state Exp; branches; next 1.20; 1.20 date 91.05.14.17.36.33; author kemnitz; state Exp; branches; next 1.19; 1.19 date 91.04.24.19.41.54; author kemnitz; state Exp; branches; next 1.18; 1.18 date 91.04.05.01.18.58; author hong; state Exp; branches; next 1.17; 1.17 date 90.09.25.16.35.39; author kemnitz; state Exp; branches; next 1.16; 1.16 date 90.06.06.11.16.58; author ong; state Exp; branches; next 1.15; 1.15 date 90.06.06.10.18.20; author ong; state Exp; branches; next 1.14; 1.14 date 90.05.30.18.56.43; author cimarron; state Exp; branches; next 1.13; 1.13 date 89.10.13.17.58.41; author hong; state Exp; branches; next 1.12; 1.12 date 89.09.29.14.48.30; author hong; state Exp; branches; next 1.11; 1.11 date 89.09.05.17.17.20; author mao; state C_Demo_1; branches; next 1.10; 1.10 date 89.09.02.13.44.23; author ong; state Exp; branches; next 1.9; 1.9 date 89.08.23.16.02.37; author ong; state Exp; branches; next 1.8; 1.8 date 89.08.05.20.31.41; author goh; state Exp; branches; next 1.7; 1.7 date 89.08.04.14.27.16; author goh; state Exp; branches; next 1.6; 1.6 date 89.08.04.13.23.14; author goh; state Exp; branches; next 1.5; 1.5 date 89.08.01.14.39.50; author goh; state Exp; branches; next 1.4; 1.4 date 89.07.25.17.35.24; author ong; state Exp; branches; next 1.3; 1.3 date 89.07.21.09.01.54; author ong; state Exp; branches; next 1.2; 1.2 date 89.07.20.18.01.21; author ong; state Exp; branches; next 1.1; 1.1 date 89.07.10.15.16.06; author ong; state Exp; branches; next ; desc @stuff for indices @ 1.32 log @CInfo->clause is now a LispValue, not an Expr @ text @ /* * FILE * indxpath * * DESCRIPTION * Routines to determine which indices are usable for * scanning a given relation * */ /* RcsId("$Header: /private/joey/pg/src/planner/path/RCS/indxpath.c,v 1.31 1992/07/08 04:57:02 joey Exp joey $"); */ /* * EXPORTS * find-index-paths */ #include #include "tmp/postgres.h" #include "access/att.h" #include "nodes/pg_lisp.h" #include "nodes/relation.h" #include "nodes/relation.a.h" #include "utils/lsyscache.h" #include "planner/internal.h" #include "planner/indxpath.h" #include "planner/clauses.h" #include "planner/clauseinfo.h" #include "planner/cfi.h" #include "planner/costsize.h" #include "planner/pathnode.h" #include "planner/xfunc.h" /* * find-index-paths * * Finds all possible index paths by determining which indices in the * list 'indices' are usable. * * To be usable, an index must match against either a set of * restriction clauses or join clauses. * * Note that the current implementation requires that there exist * matching clauses for every key in the index (i.e., no partial * matches are allowed). * * If an index can't be used with restriction clauses, but its keys * match those of the result sort order (according to information stored * within 'sortkeys'), then the index is also considered. * * 'rel' is the relation entry to which these index paths correspond * 'indices' is a list of possible index paths * 'clauseinfo-list' is a list of restriction clauseinfo nodes for 'rel' * 'joininfo-list' is a list of joininfo nodes for 'rel' * 'sortkeys' is a node describing the result sort order (from * (find_sortkeys)) * * Returns a list of index nodes. * */ /* .. find_index_paths, find_rel_paths */ LispValue find_index_paths (rel,indices,clauseinfo_list,joininfo_list,sortkeys) Rel rel; LispValue indices,clauseinfo_list,joininfo_list,sortkeys ; { LispValue scanclausegroups = LispNil; LispValue scanpaths = LispNil; Rel index = (Rel)NULL; LispValue joinclausegroups = LispNil; LispValue joinpaths = LispNil; LispValue sortpath = LispNil; LispValue retval = LispNil; LispValue temp = LispNil; LispValue add_index_paths(); if(!consp(indices)) return(NULL); index = (Rel)CAR (indices); /* 1. If this index has only one key, try matching it against * subclauses of an 'or' clause. The fields of the clauseinfo * nodes are marked with lists of the matching indices no path * are actually created. * * XXX NOTE: Currently btrees dos not support indices with * > 1 key, so the following test will always be true for * now but we have decided not to support index-scans * on disjunction . -- lp */ if (SingleAttributeIndex(index)) { match_index_orclauses (rel, index, CAR(get_indexkeys(index)), CAR(get_classlist(index)), clauseinfo_list); } /* 2. If the keys of this index match any of the available * restriction clauses, then create pathnodes corresponding * to each group of usable clauses. */ scanclausegroups = group_clauses_by_indexkey (rel, index, get_indexkeys(index), get_classlist(index), clauseinfo_list, false); scanpaths = LispNil; if (consp (scanclausegroups)) scanpaths = create_index_paths (rel, index, scanclausegroups, false); /* 3. If this index can be used with any join clause, then * create pathnodes for each group of usable clauses. An * index can be used with a join clause if its ordering is * useful for a mergejoin, or if the index can possibly be * used for scanning the inner relation of a nestloop join. */ joinclausegroups = indexable_joinclauses(rel,index,joininfo_list); joinpaths = LispNil; if (consp (joinclausegroups)) { LispValue new_join_paths = create_index_paths(rel, index, joinclausegroups, true); LispValue innerjoin_paths = index_innerjoin(rel,joinclausegroups,index); set_innerjoin (rel,nconc (get_innerjoin(rel), innerjoin_paths)); joinpaths = new_join_paths; } /* 4. If this particular index hasn't already been used above, * then check to see if it can be used for ordering a * user-specified sort. If it can, add a pathnode for the * sorting scan. */ sortpath = LispNil; if ( valid_sortkeys(sortkeys) && null(scanclausegroups) && null(joinclausegroups) && (CInteger(get_relid((SortKey)sortkeys)) == CInteger(CAR(get_relids(rel)))) && equal_path_path_ordering(get_sortorder((SortKey)sortkeys), get_ordering(index)) && equal ((Node)get_sortkeys((SortKey)sortkeys), (Node)get_indexkeys (index)) ) { sortpath = lispCons((LispValue)create_index_path(rel, index, LispNil, false), LispNil); } /* * Some sanity checks to make sure that * the indexpath is valid. */ if (!null(scanpaths)) retval = add_index_paths(retval,scanpaths); if ( !null(joinpaths) ) retval = add_index_paths(retval,joinpaths); if (!null(sortpath)) retval = add_index_paths(retval,sortpath); if (!null((temp = find_index_paths (rel, CDR (indices), clauseinfo_list, joininfo_list,sortkeys)))) { retval = append (retval,temp); } return retval; } /* function end */ /* ---- ROUTINES TO MATCH 'OR' CLAUSES ---- */ /* * match-index-orclauses * * Attempt to match an index against subclauses within 'or' clauses. * If the index does match, then the clause is marked with information * about the index. * * Essentially, this adds 'index' to the list of indices in the * ClauseInfo field of each of the clauses which it matches. * * 'rel' is the node of the relation on which the index is defined. * 'index' is the index node. * 'indexkey' is the (single) key of the index * 'class' is the class of the operator corresponding to 'indexkey'. * 'clauseinfo-list' is the list of available restriction clauses. * * Returns nothing. * */ /* .. find-index-paths */ void match_index_orclauses (rel,index,indexkey,xclass,clauseinfo_list) Rel rel,index; LispValue indexkey,xclass,clauseinfo_list ; { CInfo clauseinfo = (CInfo)NULL; LispValue i = LispNil; foreach (i, clauseinfo_list) { clauseinfo = (CInfo)CAR(i); if ( valid_or_clause((LispValue)clauseinfo)) { /* Mark the 'or' clause with a list of indices which * match each of its subclauses. The list is * generated by adding 'index' to the existing * list where appropriate. */ set_indexids (clauseinfo, match_index_orclause (rel,index,indexkey, xclass, get_orclauseargs ((List)get_clause(clauseinfo)), get_indexids (clauseinfo))); } } } /* function end */ /* * match_index_operand() * * Generalize test for a match between an existing index's key * and the operand on the rhs of a restriction clause. Now check * for functional indices as well. */ bool match_index_to_operand(indexkey, operand, rel, index) LispValue indexkey; LispValue operand; Rel rel; Rel index; { /* * Normal index. */ if (index->indproc == InvalidObjectId) return match_indexkey_operand(indexkey, operand, rel); /* * functional index check */ return (function_index_operand(operand, rel, index)); } /* * match-index-orclause * * Attempts to match an index against the subclauses of an 'or' clause. * * A match means that: * (1) the operator within the subclause can be used with one * of the index's operator classes, and * (2) there is a usable key that matches the variable within a * sargable clause. * * 'or-clauses' are the remaining subclauses within the 'or' clause * 'other-matching-indices' is the list of information on other indices * that have already been matched to subclauses within this * particular 'or' clause (i.e., a list previously generated by * this routine) * * Returns a list of the form ((a b c) (d e f) nil (g h) ...) where * a,b,c are nodes of indices that match the first subclause in * 'or-clauses', d,e,f match the second subclause, no indices * match the third, g,h match the fourth, etc. */ /* .. match-index-orclauses */ LispValue match_index_orclause (rel,index,indexkey,xclass, or_clauses,other_matching_indices) Rel rel,index; LispValue indexkey,xclass,or_clauses,other_matching_indices ; { /* XXX - lisp mapCAR -- may be wrong. */ LispValue clause = LispNil; LispValue matched_indices = other_matching_indices; LispValue index_list = LispNil; LispValue clist; LispValue ind; if (!matched_indices) matched_indices = lispCons(LispNil, LispNil); for (clist = or_clauses, ind = matched_indices; clist; clist = CDR(clist), ind = CDR(ind)) { clause = CAR(clist); if (is_clause (clause) && op_class(get_opno((Oper)get_op(clause)),CInteger(xclass)) && match_index_to_operand (indexkey, get_leftop(clause), rel, index) && IsA(get_rightop (clause),Const)) { matched_indices = lispCons((LispValue)index, matched_indices); index_list = nappend1(index_list, matched_indices); } } return(index_list); } /* function end */ /* ---- ROUTINES TO CHECK RESTRICTIONS ---- */ /* * DoneMatchingIndexKeys() - MACRO * * Determine whether we should continue matching index keys in a clause. * Depends on if there are more to match or if this is a functional index. * In the latter case we stop after the first match since the there can * be only key (i.e. the function's return value) and the attributes in * keys list represent the arguments to the function. -mer 3 Oct. 1991 */ #define DoneMatchingIndexKeys(indexkeys, index) \ ((CDR (indexkeys) == LispNil) || \ (CInteger(CADR(indexkeys)) == 0) || \ (get_indproc(index) != InvalidObjectId)) /* * group-clauses-by-indexkey * * Determines whether there are clauses which will match each and every * one of the remaining keys of an index. * * 'rel' is the node of the relation corresponding to the index. * 'indexkeys' are the remaining index keys to be matched. * 'classes' are the classes of the index operators on those keys. * 'clauses' is either: * (1) the list of available restriction clauses on a single * relation, or * (2) a list of join clauses between 'rel' and a fixed set of * relations, * depending on the value of 'join'. * 'startlist' is a list of those clause nodes that have matched the keys * that have already been checked. * 'join' is a flag indicating that the clauses being checked are join * clauses. * * Returns all possible groups of clauses that will match (given that * one or more clauses can match any of the remaining keys). * E.g., if you have clauses A, B, and C, ((A B) (A C)) might be * returned for an index with 2 keys. * */ /* .. find-index-paths, group-clauses-by-indexkey, indexable-joinclauses */ LispValue group_clauses_by_indexkey (rel,index,indexkeys,classes,clauseinfo_list,join) Rel rel,index; LispValue indexkeys,classes,clauseinfo_list; bool join; { LispValue curCinfo = LispNil; CInfo matched_clause = (CInfo)NULL; LispValue retlist = LispNil; LispValue clausegroup = LispNil; if ( !consp (clauseinfo_list) ) return LispNil; foreach (curCinfo,clauseinfo_list) { CInfo temp = (CInfo)CAR(curCinfo); LispValue curIndxKey = indexkeys; LispValue curClass = classes; do { /* * If we can't find any matching clauses for the first of * the remaining keys, give up. */ matched_clause = match_clause_to_indexkey (rel, index, CAR(curIndxKey), CAR(curClass), temp, join); if ( !matched_clause ) break; clausegroup = cons ((LispValue)matched_clause,clausegroup); curIndxKey = CDR(curIndxKey); curClass = CDR(curClass); } while ( !DoneMatchingIndexKeys(indexkeys, index) ); } if (consp(clausegroup)) return(lispCons(clausegroup,LispNil)); return LispNil; } /* * IndexScanableClause () MACRO * * Generalize condition on which we match a clause with an index. * Now we can match with functional indices. */ #define IndexScanableOperand(opnd, indkeys, rel, index) \ ((index->indproc == InvalidObjectId) ? \ equal_indexkey_var(indkeys,opnd) : \ function_index_operand(opnd,rel,index)) /* * match_clause_to-indexkey * * Finds the first of a relation's available restriction clauses that * matches a key of an index. * * To match, the clause must: * (1) be in the form (op var const) if the clause is a single- * relation clause, and * (2) contain an operator which is in the same class as the index * operator for this key. * * If the clause being matched is a join clause, then 'join' is t. * * Returns a single clauseinfo node corresponding to the matching * clause. * * NOTE: returns nil if clause is an or_clause. * */ /* .. group-clauses-by-indexkey */ CInfo match_clause_to_indexkey (rel,index,indexkey,xclass,clauseInfo,join) Rel rel,index; LispValue indexkey,xclass; CInfo clauseInfo; bool join; { LispValue clause = get_clause (clauseInfo); Var leftop = get_leftop (clause); Var rightop = get_rightop (clause); ObjectId join_op = InvalidObjectId; bool isIndexable = false; if ( or_clause (clause)) return ((CInfo)NULL); /* * If this is not a join clause, check for clauses of the form: * (operator var/func constant) and (operator constant var/func) */ if(!join) { ObjectId restrict_op = InvalidObjectId; /* * Check for standard s-argable clause */ if (IsA(rightop,Const)) { restrict_op = get_opno((Oper)get_op(clause)); isIndexable = ( op_class(restrict_op, CInteger(xclass)) && IndexScanableOperand((LispValue)leftop,indexkey,rel,index) ); } /* * Must try to commute the clause to standard s-arg format. */ else if (IsA(leftop,Const)) { restrict_op = get_commutator(get_opno((Oper)get_op(clause))); if ( (restrict_op != InvalidObjectId) && op_class(restrict_op, CInteger(xclass)) && IndexScanableOperand((LispValue)rightop,indexkey,rel,index) ) { isIndexable = true; /* * In place list modification. * (op const var/func) -> (op var/func const) */ /* BUG! Old version: CommuteClause(clause, restrict_op); */ CommuteClause(clause); } } } /* * Check for an indexable scan on one of the join relations. * clause is of the form (operator var/func var/func) */ else { if (match_index_to_operand (indexkey,rightop,rel,index)) join_op = get_commutator(get_opno((Oper)get_op(clause))); else if (match_index_to_operand (indexkey,leftop,rel,index)) join_op = get_opno((Oper)get_op(clause)); if ( join_op && op_class(join_op,CInteger(xclass)) && join_clause_p(clause)) { isIndexable = true; /* * If we're using the operand's commutator we must * commute the clause. */ if ( join_op != get_opno((Oper)get_op(clause)) ) CommuteClause(clause); } } if (isIndexable) return(clauseInfo); return(NULL); } /* ---- ROUTINES TO CHECK JOIN CLAUSES ---- */ /* * indexable-joinclauses * * Finds all groups of join clauses from among 'joininfo-list' that can * be used in conjunction with 'index'. * * The first clause in the group is marked as having the other relation * in the join clause as its outer join relation. * * Returns a list of these clause groups. * */ /* .. find-index-paths */ LispValue indexable_joinclauses (rel,index,joininfo_list) Rel rel,index; List joininfo_list ; { /* XXX Lisp Mapcan -- may be wrong */ JInfo joininfo = (JInfo)NULL; LispValue cg_list = LispNil; LispValue i = LispNil; LispValue clausegroups = LispNil; foreach(i,joininfo_list) { joininfo = (JInfo)CAR(i); clausegroups = group_clauses_by_indexkey (rel, index, get_indexkeys(index), get_classlist (index), get_jinfoclauseinfo(joininfo), true); if ( consp (clausegroups)) { set_cinfojoinid((CInfo)CAAR(clausegroups), get_otherrels(joininfo)); } cg_list = nconc(cg_list,clausegroups); } return(cg_list); } /* function end */ /* ---- PATH CREATION UTILITIES ---- */ /* * index-innerjoin * * Creates index path nodes corresponding to paths to be used as inner * relations in nestloop joins. * * 'clausegroup-list' is a list of list of clauseinfo nodes which can use * 'index' on their inner relation. * * Returns a list of index pathnodes. * */ /* .. find-index-paths */ LispValue index_innerjoin (rel,clausegroup_list,index) Rel rel; List clausegroup_list; Rel index ; { LispValue clausegroup = LispNil; LispValue cg_list = LispNil; LispValue i = LispNil; LispValue relattvals = LispNil; List pagesel = LispNil; IndexPath pathnode = (IndexPath)NULL; Cost temp_selec; Count temp_pages; foreach(i,clausegroup_list) { clausegroup = CAR(i); pathnode = RMakeIndexPath(); relattvals = get_joinvars (CAR(get_relids(rel)),clausegroup); pagesel = index_selectivity (CInteger(CAR(get_relids (index))), get_classlist (index), get_opnos (clausegroup), CInteger(getrelid (CInteger(CAR (get_relids (rel))), _query_range_table_)), CAR (relattvals), CADR (relattvals), CADDR (relattvals), length (clausegroup)); set_pathtype((Path)pathnode,T_IndexScan); set_parent((Path)pathnode,rel); set_indexid(pathnode,get_relids (index)); set_indexqual(pathnode,clausegroup); set_joinid((Path)pathnode,get_cinfojoinid((CInfo)CAR(clausegroup))); temp_pages = (int)CDouble(CAR(pagesel)); temp_selec = CDouble(CADR(pagesel)); set_path_cost ((Path)pathnode,cost_index( (ObjectId)CInteger(CAR(get_relids (index))), temp_pages, temp_selec, get_pages (rel), get_tuples (rel), get_pages (index), get_tuples (index), true)); /* copy clauseinfo list into path for expensive function processing -- JMH, 7/7/92 */ set_locclauseinfo(pathnode, set_difference(CopyObject(get_clauseinfo(rel)), clausegroup, LispNil)); /* add in cost for expensive functions! -- JMH, 7/7/92 */ set_path_cost((Path)pathnode, get_path_cost((Path)pathnode) + xfunc_get_path_cost(pathnode)); cg_list = nappend1(cg_list,(LispValue)pathnode); } return(cg_list); } /* function end */ /* * create-index-paths * * Creates a list of index path nodes for each group of clauses * (restriction or join) that can be used in conjunction with an index. * * 'rel' is the relation for which 'index' is defined * 'clausegroup-list' is the list of clause groups (lists of clauseinfo * nodes) grouped by mergesortorder * 'join' is a flag indicating whether or not the clauses are join * clauses * * Returns a list of new index path nodes. * */ /* .. find-index-paths */ LispValue create_index_paths (rel,index,clausegroup_list,join) Rel rel, index; LispValue clausegroup_list; bool join; { /* XXX Mapcan */ LispValue clausegroup = LispNil; LispValue ip_list = LispNil; LispValue temp = LispTrue; LispValue i = LispNil; LispValue j = LispNil; IndexPath temp_path; foreach(i,clausegroup_list) { CInfo clauseinfo; LispValue temp_node = LispNil; bool temp = true; clausegroup = CAR(i); foreach (j,clausegroup) { clauseinfo = (CInfo)CAR(j); if ( !(join_clause_p(get_clause(clauseinfo)) && equal_path_merge_ordering ( get_ordering(index), get_mergesortorder (clauseinfo)))) { temp = false; } } if ( !join || temp ) { /* restriction, ordering scan */ temp_path = create_index_path (rel,index,clausegroup,join); temp_node = lispCons ((LispValue)temp_path, LispNil); ip_list = nconc(ip_list,temp_node); } } return(ip_list); } /* function end */ bool indexpath_useless(p, plist) IndexPath p; List plist; { LispValue x; IndexPath path; List qual; if (get_indexqual(p)) return false; foreach (x, plist) { path = (IndexPath)CAR(x); qual = get_indexqual(path); set_indexqual(path, LispNil); if (equal((Node)p, (Node)path)) { set_indexqual(path, qual); return true; } set_indexqual(path, qual); } return false; } List add_index_paths(indexpaths, new_indexpaths) List indexpaths, new_indexpaths; { LispValue x; IndexPath path; List retlist; extern int testFlag; if (!testFlag) return append(indexpaths, new_indexpaths); retlist = indexpaths; foreach (x, new_indexpaths) { path = (IndexPath)CAR(x); if (!indexpath_useless(path, retlist)) retlist = nappend1(retlist, (LispValue)path); } return retlist; } bool function_index_operand(funcOpnd, rel, index) LispValue funcOpnd; Rel rel; Rel index; { ObjectId heapRelid = CInteger(CAR(get_relids(rel))); Func function = (Func)get_function(funcOpnd); LispValue funcargs = get_funcargs(funcOpnd); LispValue indexKeys = get_indexkeys(index); LispValue arg; /* * sanity check, make sure we know what we're dealing with here. */ if ( !((consp(funcOpnd) && function) && IsA(function,Func)) ) return false; if (get_funcid(function) != get_indproc(index)) return false; /* * Check that the arguments correspond to the same arguments used * to create the functional index. To do this we must check that * 1. refer to the right relatiion. * 2. the args have the right attr. numbers in the right order. * * * Check all args refer to the correct relation (i.e. the one with * the functional index defined on it (rel). To do this we can * simply compare range table entry numbers, they must be the same. */ foreach (arg, funcargs) { if (heapRelid != get_varno((Var)CAR(arg))) return false; } /* * check attr numbers and order. */ foreach (arg, funcargs) { int curKey; if (indexKeys == LispNil) return (false); curKey = CInteger(CAR(indexKeys)); indexKeys = CDR (indexKeys); if (get_varattno((Var)CAR(arg)) != curKey) return (false); } /* * We have passed all the tests. */ return true; } bool SingleAttributeIndex(index) Rel index; { /* * Non-functional indices. */ /* * return false for now as I don't know if we support index scans * on disjunction and the code doesn't work */ return (false); #if 0 if (index->indproc == InvalidObjectId) { switch (length(get_indexkeys(index))) { case 0: return false; case 1: return true; /* * The list of index keys currently always has 8 elements. * It is a SingleAttributeIndex if the second element on * are invalid. It suffices to just check the 2nd -mer Oct 21 1991 */ default: return (CInteger(CADR(get_indexkeys(index))) == InvalidObjectId); } } /* * We have a functional index which is a single attr index */ return true; #endif } @ 1.31 log @set up locclauseinfo and add xfunc to path_cost in index_innerjoin @ text @d11 1 a11 1 /* RcsId("$Header: /private/joey/pg/src/planner/path/RCS/indxpath.c,v 1.30 1992/03/31 23:13:02 mer Exp joey $"); */ d470 3 a472 3 Expr clause = get_clause (clauseInfo); Var leftop = get_leftop ((LispValue)clause); Var rightop = get_rightop ((LispValue)clause); d476 1 a476 1 if ( or_clause ((LispValue)clause)) d492 1 a492 1 restrict_op = get_opno((Oper)get_op((LispValue)clause)); d503 1 a503 1 restrict_op = get_commutator(get_opno((Oper)get_op((LispValue)clause))); d514 4 a517 1 CommuteClause(clause, restrict_op); d529 1 a529 1 join_op = get_commutator(get_opno((Oper)get_op((LispValue)clause))); d532 1 a532 1 join_op = get_opno((Oper)get_op((LispValue)clause)); d543 1 a543 1 if ( join_op != get_opno((Oper)get_op((LispValue)clause)) ) @ 1.30 log @change accessor functions into macros @ text @d11 1 a11 1 /* RcsId("$Header: /users/mer/pg/src/planner/path/RCS/indxpath.c,v 1.29 1991/11/17 20:39:50 mer Exp mer $"); */ d35 1 d669 11 @ 1.29 log @prototyping @ text @d11 1 a11 1 /* RcsId("$Header: /users/mer/postgres/src/planner/path/RCS/indxpath.c,v 1.28 1991/11/15 16:27:02 hong Exp mer $"); */ d811 1 a811 1 if (heapRelid != get_varno(CAR(arg))) d827 1 a827 1 if (get_varattno(CAR(arg)) != curKey) @ 1.28 log @planner prototyping @ text @d11 1 a11 1 /* RcsId("$Header: RCS/indxpath.c,v 1.27 91/11/08 00:21:06 mer Exp $"); */ d162 2 a163 1 && equal (get_sortkeys((SortKey)sortkeys), get_indexkeys (index)) ) d165 1 a165 1 sortpath = lispCons(create_index_path(rel, d327 1 a327 1 matched_indices = lispCons(index, matched_indices); d416 1 a416 1 clausegroup = cons (matched_clause,clausegroup); d669 1 a669 1 cg_list = nappend1(cg_list,pathnode); d726 1 a726 1 lispCons (temp_path, d748 1 a748 1 if (equal(p, path)) { d772 1 a772 1 retlist = nappend1(retlist, path); @ 1.27 log @fix warning @ text @d11 1 a11 1 /* RcsId("$Header: /users/mer/postgres/src/planner/path/RCS/indxpath.c,v 1.26 1991/11/07 22:00:32 mer Exp mer $"); */ a35 2 extern IndexPath RMakeIndexPath(); d158 3 a160 2 && (get_relid(sortkeys) == get_relid(rel)) && equal_path_path_ordering(get_sortorder(sortkeys), d162 1 a162 1 && equal (get_sortkeys(sortkeys), get_indexkeys (index)) ) d167 1 a167 1 LispNil), d222 2 a223 1 LispValue rel,index,indexkey,xclass,clauseinfo_list ; d230 1 a230 1 if ( valid_or_clause (clauseinfo)) { d241 1 a241 1 (get_clause(clauseinfo)), d300 2 a301 1 LispValue rel,index,indexkey,xclass,or_clauses,other_matching_indices ; d319 1 a319 1 op_class(get_opno(get_op (clause)),CInteger(xclass)) && d469 2 a470 2 Var leftop = get_leftop (clause); Var rightop = get_rightop (clause); d474 1 a474 1 if ( or_clause (clause)) d490 1 a490 1 restrict_op = get_opno(get_op(clause)); d493 1 a493 1 IndexScanableOperand(leftop,indexkey,rel,index) ); d501 1 a501 1 restrict_op = get_commutator(get_opno(get_op(clause))); d505 1 a505 1 IndexScanableOperand(rightop,indexkey,rel,index) ) d524 1 a524 1 join_op = get_commutator (get_opno (get_op (clause))); d527 1 a527 1 join_op = get_opno (get_op (clause)); d538 1 a538 1 if ( join_op != get_opno(get_op(clause)) ) d571 2 a572 1 LispValue rel,index,joininfo_list ; d592 1 a592 1 set_cinfojoinid (CAAR(clausegroups), d650 5 a654 5 set_pathtype (pathnode,T_IndexScan); set_parent (pathnode,rel); set_indexid (pathnode,get_relids (index)); set_indexqual (pathnode,clausegroup); set_joinid (pathnode,get_cinfojoinid (CAR (clausegroup))); d659 2 a660 1 set_path_cost (pathnode,cost_index (CInteger(CAR(get_relids (index))), d706 1 a706 1 LispValue clauseinfo = LispNil; d713 1 a713 5 clauseinfo = CAR(j); /* if (consp (clauseinfo)) clauseinfo = CAR(clauseinfo); */ @ 1.26 log @code cleanup and partial support for index scans on disjunctive clauses @ text @d11 1 a11 1 /* RcsId("$Header: /users/mer/postgres/src/planner/path/RCS/indxpath.c,v 1.25 1991/10/16 23:05:31 mer Exp mer $"); */ d851 1 d873 1 @ 1.25 log @add functional index support and clean up affected routines also add fixes for commuting clauses in index scans where necessary @ text @d11 1 a11 1 /* RcsId("$Header: /users/mer/postgres/src/planner/path/RCS/indxpath.c,v 1.24 1991/08/23 16:58:30 kemnitz Exp mer $"); */ d66 1 a66 1 /* .. find-index-paths, find-rel-paths */ d76 1 a76 1 Rel index = (Rel)NULL; d82 1 a82 1 List add_index_paths(); d84 2 a85 1 if(consp (indices)) { d87 1 a87 10 /* 1. If this index has only one key, try matching it against * subclauses of an 'or' clause. The fields of the clauseinfo * nodes are marked with lists of the matching indices no path * are actually created. * * XXX NOTE: Currently btrees dos not support indices with * > 1 key, so the following test will always be true for * now but we have decided not to support index-scans * on disjunction . -- lp */ d89 10 a98 1 if ( 1 == length (get_indexkeys (CAR (indices)))) { d100 6 a105 4 match_index_orclauses (rel,CAR (indices), CAR ( get_indexkeys (CAR (indices))), CAR (get_classlist(CAR (indices))), d107 1 a107 12 } index = (Rel)CAR (indices); /* 2. If the keys of this index match any of the available * restriction clauses, then create pathnodes corresponding * to each group of usable clauses. */ scanclausegroups = group_clauses_by_indexkey (rel,index,get_indexkeys (index), get_classlist (index),clauseinfo_list, false); d109 4 d114 13 a126 5 scanpaths = LispNil; if ( consp (scanclausegroups) ) scanpaths = create_index_paths (rel,index, scanclausegroups, false); d128 6 a133 6 /* 3. If this index can be used with any join clause, then * create pathnodes for each group of usable clauses. An * index can be used with a join clause if its ordering is * useful for a mergejoin, or if the index can possibly be * used for scanning the inner relation of a nestloop join. */ d135 14 a148 13 joinclausegroups = indexable_joinclauses (rel,index,joininfo_list); joinpaths = LispNil; if ( consp (joinclausegroups) ) { LispValue new_join_paths = create_index_paths (rel,index,joinclausegroups, true); LispValue innerjoin_paths = index_innerjoin (rel,joinclausegroups,index); set_innerjoin (rel,nconc (get_innerjoin(rel), innerjoin_paths)); joinpaths = new_join_paths; } d150 5 a154 5 /* 4. If this particular index hasn't already been used above, * then check to see if it can be used for ordering a * user-specified sort. If it can, add a pathnode for the * sorting scan. */ d156 15 a170 11 sortpath = LispNil; if ( valid_sortkeys(sortkeys) && null(scanclausegroups) && null(joinclausegroups) && (get_relid(sortkeys) == get_relid(rel)) && equal_path_path_ordering(get_sortorder (sortkeys), get_ordering (index)) && equal (get_sortkeys(sortkeys),get_indexkeys (index))) { sortpath =lispCons (create_index_path (rel,index, LispNil, LispNil), LispNil); } d172 10 a181 10 /* * Some sanity checks to make sure that * the indexpath is valid. */ if (!null(scanpaths)) retval = add_index_paths(retval,scanpaths); if ( !null(joinpaths) ) retval = add_index_paths(retval,joinpaths); if (!null(sortpath)) retval = add_index_paths(retval,sortpath); d183 5 a187 4 if (!null((temp = find_index_paths (rel, CDR (indices), clauseinfo_list, joininfo_list,sortkeys)))) d189 3 a192 3 return(retval); } return(NULL); a236 7 /* * if get_indexids is not nil, it implies that that * clause has already been matched with a previous index. */ if (!get_indexids (clauseinfo)) d243 2 a244 2 } } a292 3 * * NOTE: Currently we have only 1 key. so the list will look like * ((abc) nil nil ...) or just ((abc)) d306 5 a310 1 LispValue i = LispNil; d312 5 a316 2 foreach (i,or_clauses) { clause = CAR(i); a327 4 } /* else { index_list = nappend1(index_list,matched_indices); a328 1 */ d833 37 @ 1.24 log @got to compile with gcc (-traditional) @ text @d11 1 a11 1 /* RcsId("$Header: RCS/indxpath.c,v 1.23 91/06/21 17:43:33 hong Exp Locker: kemnitz $"); */ d115 1 a115 1 LispNil,LispNil); d244 25 d312 4 a315 3 match_indexkey_operand (indexkey, get_leftop (clause), rel) && d335 14 d379 4 a382 5 group_clauses_by_indexkey (rel,index,indexkeys,classes,clauseinfo_list, matched_clauseinfo_list,join) Rel rel,index; LispValue indexkeys,classes,clauseinfo_list, matched_clauseinfo_list,join ; d384 31 a414 5 LispValue i = LispNil; CInfo temp = (CInfo)NULL; CInfo matched_clause = (CInfo)NULL; LispValue clausegroup = LispNil; LispValue retlist = LispNil; d416 2 a417 1 if ( consp (clauseinfo_list) ) { d419 4 a422 3 foreach (i,clauseinfo_list) { clausegroup = LispNil; temp = (CInfo)CAR(i); d424 10 a433 37 /* If we can't find any matching clauses for the first of * the remaining keys, give up now. */ matched_clause = match_clauses_to_indexkey (rel,index, CAR(indexkeys), CAR(classes), lispCons(temp,LispNil), join); if ( matched_clause ) { LispValue new_matched_clauseinfo_list = cons (matched_clause,matched_clauseinfo_list); if ( CDR (indexkeys) && CInteger(CADR(indexkeys)) != 0) { clausegroup = group_clauses_by_indexkey (rel,index, CDR (indexkeys), CDR (classes), lispCons(temp,LispNil), new_matched_clauseinfo_list, join); } else { clausegroup = new_matched_clauseinfo_list; /* lispCons (new_matched_clauseinfo_list,LispNil); */ } } if(consp(clausegroup)) retlist = nappend1(retlist,CAR(clausegroup)); } if (null(retlist)) return (LispNil); return(lispCons(retlist,LispNil)); } return(LispNil); } /* function end */ d436 1 a436 1 * match-clauses-to-indexkey d459 1 a459 1 match_clauses_to_indexkey (rel,index,indexkey,xclass,clauses,join) d461 3 a463 1 LispValue indexkey,xclass,clauses,join ; d465 16 a480 12 /* XXX lisp find-if function --- may be wrong */ CInfo clauseinfo = (CInfo)NULL; LispValue i = LispNil; Expr clause = (Expr)NULL; Var leftop = (Var)NULL; Var rightop = (Var)NULL; LispValue clist = LispNil; foreach(i,clauses) { ObjectId join_op = 0; bool temp1 = false ; bool temp2 =false; d482 10 a491 4 clauseinfo = (CInfo)CAR(i); clause = get_clause (clauseinfo); leftop = get_leftop (clause); rightop = get_rightop (clause); d493 20 a512 2 if ( or_clause (clause)) return ((CInfo)NULL); d514 7 a520 4 if(null (join)) { ; } else if (match_indexkey_operand (indexkey,rightop,rel)) { d522 2 a523 2 } else if (match_indexkey_operand (indexkey,leftop,rel)) { d525 20 a544 18 } temp1 = (bool) (join_op == 0 /* (op var const) */ && op_class(get_opno(get_op(clause)),CInteger(xclass)) && ( (qual_clause_p(clause) && equal_indexkey_var(indexkey,leftop)) || function_index_clause_p(clause,rel,index))); temp2 = (bool) (join_op && op_class(join_op,CInteger(xclass)) && join_clause_p(clause)); if (temp1 || temp2) return(clauseinfo); /* clist = lispCons(clauseinfo,clist); */ } return(NULL); /* return(clist); */ } /* function end */ d580 2 a581 1 group_clauses_by_indexkey (rel,index, d585 2 a586 3 LispNil, LispTrue); d773 60 @ 1.23 log @fixed a problem that cause weird behaviors in planner @ text @d11 1 a11 1 /* RcsId("$Header: RCS/indxpath.c,v 1.22 91/05/29 23:49:54 hong Exp Locker: hong $"); */ d22 1 a22 1 #include "nodes/pg_lisp.h"; d28 1 a28 1 #include "planner/internal.h"; @ 1.22 log @some new functions for wei's experiments. @ text @d11 1 a11 1 /* RcsId("$Header: RCS/indxpath.c,v 1.19 91/04/24 19:41:54 kemnitz Exp $"); */ d687 1 d689 2 @ 1.21 log @got rid of lint warning "has return(e); and return;" @ text @d11 1 a11 1 /* RcsId("$Header: RCS/indxpath.c,v 1.20 91/05/14 17:36:33 kemnitz Exp Locker: kemnitz $"); */ d82 1 d168 1 a168 1 retval = append (retval,scanpaths); d170 1 a170 1 retval = append(retval,joinpaths); d172 1 a172 1 retval = append (retval,sortpath); d182 1 a182 1 return(NULL); d657 39 @ 1.20 log @find_index_paths should return NULL if it gets a null list of indices. @ text @d11 1 a11 1 /* RcsId("$Header: RCS/indxpath.c,v 1.19 91/04/24 19:41:54 kemnitz Exp Locker: hong $"); */ d466 1 @ 1.19 log @replaced null(double) with FLOAT_IS_ZERO(double) @ text @d11 1 a11 1 /* RcsId("$Header: RCS/indxpath.c,v 1.18 91/04/05 01:18:58 hong Exp Locker: kemnitz $"); */ d181 1 @ 1.18 log @cost_index() sometimes needs know whether the indexscan is as the inner path of a nestloop join @ text @d11 1 a11 1 /* RcsId("$Header: RCS/indxpath.c,v 1.17 90/09/25 16:35:39 kemnitz Exp Locker: hong $"); */ d152 1 a152 2 null(joinclausegroups) && equal(get_relid(sortkeys), get_relid (rel)) && @ 1.17 log @Updating from revision 1.16 to revision 1.17 @ text @d11 1 a11 1 /* RcsId("$Header: RCS/indxpath.c,v 1.17 90/08/14 11:09:52 cimarron Exp $"); */ d584 1 a584 1 get_tuples (index))); @ 1.16 log @minor fix for index joins. @ text @d11 1 a11 1 /* RcsId("$Header: RCS/indxpath.c,v 1.15 90/06/06 10:18:20 ong Exp Locker: ong $"); */ d17 1 d19 9 a27 3 #include "pg_lisp.h"; #include "relation.h" #include "relation.a.h" a30 1 #include "lsyscache.h" a32 1 #include @ 1.15 log @merged Cim's changes with my changes to support conjunctive index quals. lp @ text @d11 1 a11 1 /* RcsId("$Header: RCS/indxpath.c,v 1.13 89/10/13 17:58:41 hong Exp Locker: ong $"); */ d553 1 a553 1 index_selectivity (CAR((LispValue)get_relids (index)), @ 1.14 log @CreateNode(Foo) --> RMakeFoo() change @ text @d1 1 a30 4 /* ---------------- * IndexPath creator declaration * ---------------- */ d76 1 d84 5 d91 8 a98 7 if ( 1 == length (get_indexkeys (CAR (indices)))) { match_index_orclauses (rel,CAR (indices), CAR ( get_indexkeys (CAR (indices))), CAR (get_classlist(CAR (indices))), clauseinfo_list); } d109 3 a111 1 LispNil,LispNil); d157 17 a173 8 retval = append (scanpaths,joinpaths); retval = append (retval,sortpath); retval = append (retval, find_index_paths (rel, CDR (indices), clauseinfo_list, joininfo_list,sortkeys)); d221 7 a227 1 d260 2 d280 1 a280 1 op_class(get_opno(get_op (clause)),xclass) && d285 4 a288 2 index_list = nappend1(index_list, lispCons (index,matched_indices)); d290 1 d292 1 a292 1 index_list = nappend1(index_list,matched_indices); d294 1 d339 6 d346 5 a350 1 d355 1 a355 1 CInfo matched_clause = d359 2 a360 1 clauseinfo_list,join); a363 1 LispValue clausegroup = LispNil; d370 1 a370 1 clauseinfo_list, d375 2 a376 2 clausegroup = lispCons (new_matched_clauseinfo_list,LispNil); a377 18 if ( consp (clausegroup) ) { return (nconc (clausegroup, /* See if other clauses can be used for */ /* these remaining keys by ignoring the one */ /* that was just used (i.e., find all */ /* possible solutions). */ group_clauses_by_indexkey (rel,index, indexkeys, classes, remove (matched_clause, clauseinfo_list), matched_clauseinfo_list, join))); } d379 4 d384 1 d386 1 a386 1 return (LispNil); d405 2 d423 1 d435 3 d447 1 a447 1 d459 3 a461 1 } d556 3 a558 2 getrelid (CInteger(CAR(get_relids (rel))), _query_range_table_), d619 1 a619 1 CInfo clauseinfo = (CInfo)NULL; d626 5 a630 1 clauseinfo = (CInfo)CAR(j); @ 1.13 log @some fixes for mergejoins @ text @a0 1 d10 1 a10 1 /* RcsId("$Header: RCS/indxpath.c,v 1.12 89/09/29 14:48:30 hong Exp Locker: hong $"); */ d30 6 d517 1 a517 1 pathnode = CreateNode(IndexPath); @ 1.12 log @some fixes for index joins, now index joins work @ text @d11 1 a11 1 /* RcsId("$Header: RCS/indxpath.c,v 1.11 89/09/05 17:17:20 mao C_Demo_1 Locker: hong $"); */ d29 1 d138 1 a138 1 equal_path_path_ordering(get_ordering (sortkeys), d578 1 d598 1 d600 2 a601 3 lispCons (create_index_path (rel,index, clausegroup,join), LispNil); @ 1.11 log @Working version of C-only demo @ text @d11 1 a11 1 /* RcsId("$Header: RCS/indxpath.c,v 1.10 89/09/02 13:44:23 ong Exp $"); */ d419 1 a419 1 !zerop(join_op) && join_clause_p(clause)); d468 1 a468 1 set_joinid (CAAR(clausegroups), d505 1 a505 1 Path pathnode = (Path)NULL; d511 1 a511 1 pathnode = CreateNode(Path); d518 1 a518 1 getrelid (get_relid (rel), d529 1 a529 1 set_joinid (pathnode,get_joinid (CAR (clausegroup))); d534 1 a534 1 set_cost (pathnode,cost_index (CInteger(CAR(get_relids (index))), @ 1.10 log @#included costsize.h @ text @d11 1 a11 1 /* RcsId("$Header: RCS/indxpath.c,v 1.9 89/08/23 16:02:37 ong Exp Locker: ong $"); */ @ 1.9 log @planner supports all but rules and mergesort @ text @d11 1 a11 1 /* RcsId("$Header: /n/hermes/usr6/postgres/ong/postgres/src/planner/path/RCS/indxpath.c,v 1.8 89/08/05 20:31:41 goh Exp Locker: ong $"); */ d28 1 @ 1.8 log @fixed include path problem @ text @d11 1 a11 1 /* RcsId("$Header: indxpath.c,v 1.7 89/08/04 14:27:16 goh Locked $"); */ d27 1 a28 5 /* #define INDEXSCAN 1 #define List LispValue */ d61 2 a62 1 LispValue rel,indices,clauseinfo_list,joininfo_list,sortkeys ; d65 9 a73 6 LispValue scanclausegroups = LispNil; LispValue scanpaths = LispNil; LispValue index = LispNil; LispValue joinclausegroups = LispNil; LispValue joinpaths = LispNil; LispValue sortpath = LispNil; d75 5 a79 7 if(consp (indices)) { /* 1. If this index has only one key, try matching it against * subclauses of an 'or' clause. The fields of the clauseinfo * nodes are marked with lists of the matching indices no path * are actually created. */ d81 13 a93 7 if ( 1 == length (get_indexkeys (CAR (indices)))) { match_index_orclauses (rel,CAR (indices), CAR ( get_indexkeys (CAR (indices))), CAR (get_classlist(CAR (indices))), clauseinfo_list); } d95 9 a103 5 index = CAR (indices); /* 2. If the keys of this index match any of the available * restriction clauses, then create pathnodes corresponding * to each group of usable clauses. */ d105 6 a110 9 scanclausegroups = group_clauses_by_indexkey (rel,index,get_indexkeys (index), get_classlist (index),clauseinfo_list, LispNil,LispNil); scanpaths = LispNil; if ( consp (scanclausegroups) ) scanpaths = create_index_paths (rel,index, scanclausegroups, LispNil); d112 13 a124 6 /* 3. If this index can be used with any join clause, then * create pathnodes for each group of usable clauses. An * index can be used with a join clause if its ordering is * useful for a mergejoin, or if the index can possibly be * used for scanning the inner relation of a nestloop join. */ d126 5 a130 13 joinclausegroups = indexable_joinclauses (rel,index,joininfo_list); joinpaths = LispNil; if ( consp (joinclausegroups) ) { LispValue new_join_paths = create_index_paths (rel,index,joinclausegroups, LispTrue); LispValue innerjoin_paths = index_innerjoin (rel,joinclausegroups,index); set_innerjoin (rel,nconc (get_innerjoin(rel), innerjoin_paths)); joinpaths = new_join_paths; } d132 10 a141 16 /* 4. If this particular index hasn't already been used above, * then check to see if it can be used for ordering a * user-specified sort. If it can, add a pathnode for the * sorting scan. */ sortpath = LispNil; if ( valid_sortkeys(sortkeys) && null(scanclausegroups) && null(joinclausegroups) && equal(get_relid(sortkeys), get_relid (rel)) && equal_path_path_ordering(get_ordering (sortkeys), get_ordering (index)) && equal (get_sortkeys(sortkeys),get_indexkeys (index))) { sortpath =lispCons (create_index_path (rel,index, LispNil, LispNil), d143 1 a143 1 } d145 7 a151 7 return (append (scanpaths,joinpaths,sortpath, find_index_paths (rel, CDR (indices), clauseinfo_list, joininfo_list,sortkeys))); } } /* function end */ d153 3 d157 1 d187 14 a200 11 LispValue clauseinfo; foreach (clauseinfo, clauseinfo_list) { if ( valid_or_clause (clauseinfo)) { /* Mark the 'or' clause with a list of indices which * match each of its subclauses. The list is * generated by adding 'index' to the existing * list where appropriate. */ set_indexids (clauseinfo, d241 22 a262 4 /* XXX - lisp mapCAR -- may be wrong. */ LispValue clause = LispNil; LispValue matched_indices = other_matching_indices; LispValue index_list = LispNil; a263 16 foreach (clause,or_clauses) { if (is_clause (clause) && op_class(get_opno(get_op (clause)),xclass) && match_indexkey_operand (indexkey, get_leftop (clause), rel) && IsA(get_rightop (clause),Const)) { index_list = nappend1(index_list, lispCons (index,matched_indices)); } else { index_list = nappend1(index_list,matched_indices); } } return(index_list); d301 2 a302 1 LispValue rel,index,indexkeys,classes,clauseinfo_list, d305 21 a325 20 if ( consp (clauseinfo_list) ) { /* If we can't find any matching clauses for the first of * the remaining keys, give up now. */ CInfo matched_clause = match_clauses_to_indexkey (rel,index, CAR(indexkeys), CAR(classes), clauseinfo_list,join); if ( matched_clause ) { LispValue new_matched_clauseinfo_list = cons (matched_clause,matched_clauseinfo_list); LispValue clausegroup = LispNil; if ( CDR (indexkeys) ) { clausegroup = group_clauses_by_indexkey (rel,index, CDR (indexkeys), CDR (classes), d327 7 a333 7 new_matched_clauseinfo_list, join); } else { clausegroup = lispCons (new_matched_clauseinfo_list,LispNil); } d335 7 a341 2 if ( consp (clausegroup) ) { return (nconc (clausegroup, d343 9 a351 14 /* See if other clauses can be used for */ /* these remaining keys by ignoring the one */ /* that was just used (i.e., find all */ /* possible solutions). */ group_clauses_by_indexkey (rel,index, indexkeys, classes, remove (matched_clause, clauseinfo_list), matched_clauseinfo_list, join))); } d353 3 a355 3 return (LispNil); } return (LispNil); d381 2 a382 1 LispValue rel,index,indexkey,xclass,clauses,join ; d384 26 a409 18 /* XXX lisp find-if function --- may be wrong */ LispValue clauseinfo = LispNil; foreach(clauseinfo,clauses) { Expr clause = get_clause (clauseinfo); Var leftop = get_leftop (clause); Var rightop = get_rightop (clause); ObjectId join_op; bool temp1 ; bool temp2 ; if(null (join)) { ; } else if (match_indexkey_operand (indexkey,rightop,rel)) { join_op = get_commutator (get_opno (get_op (clause))); } else if (match_indexkey_operand (indexkey,leftop,rel)) { join_op = get_opno (get_op (clause)); } d411 5 a415 5 temp1 = (bool) (null(join_op) /* (op var const) */ && op_class(get_opno(get_op(clause)),xclass) && ( (qual_clause_p(clause) && equal_indexkey_var(indexkey,leftop)) || function_index_clause_p(clause,rel,index))); d417 2 a418 2 temp2 = (bool) (join_op && op_class(join_op,xclass) && !zerop(join_op) && join_clause_p(clause)); d420 3 a422 3 if (temp1 || temp2) return((CInfo)clauseinfo); } d451 4 a454 2 LispValue joininfo = LispNil; LispValue cg_list = LispNil; d456 9 a464 8 foreach(joininfo,joininfo_list) { LispValue clausegroups = group_clauses_by_indexkey (rel,index, get_indexkeys(index), get_classlist (index), get_clauseinfo(joininfo), LispNil, LispTrue); d466 7 a472 7 if ( consp (clausegroups)) { set_joinid (CAAR(clausegroups), get_otherrels(joininfo)); } cg_list = nconc(cg_list,clausegroups); } return(cg_list); d495 3 a497 2 LispValue rel,clausegroup_list,index ; d501 22 a522 4 /* XXX MapCAR function */ foreach(clausegroup,clausegroup_list) { Path pathnode = CreateNode(Path); d524 5 a528 25 LispValue relattvals = get_joinvars (get_relid (rel),clausegroup); LispValue pagesel = index_selectivity (CAR((LispValue)get_indexid (index)), get_classlist (index), get_opnos (clausegroup), getrelid (get_relid (rel), _query_range_table_), CAR (relattvals), CADR (relattvals), CADDR (relattvals), length (clausegroup)); set_pathtype (pathnode,T_IndexScan); set_parent (pathnode,rel); set_indexid (pathnode,get_indexid (index)); set_indexqual (pathnode,clausegroup); set_joinid (pathnode,get_joinid (CAR (clausegroup))); set_cost (pathnode,cost_index (nth (0,get_indexid (index)), floor (nth (0,pagesel)), (int)(nth (1,pagesel)), get_pages (rel), get_tuples (rel), get_pages (index), get_tuples (index))); d530 12 a541 1 cg_list = nappend1(cg_list,pathnode); d544 1 a544 1 } /* function end */ d566 3 a568 1 LispValue rel,index,clausegroup_list,join ; d574 2 d577 16 a592 3 foreach(clausegroup,clausegroup_list) { LispValue clauseinfo = LispNil; LispValue temp_node = LispNil; d594 6 a599 15 foreach (clauseinfo,clausegroup) { if ( !(join_clause_p(get_clause(clauseinfo)) && equal_path_merge_ordering ( get_ordering(index), get_mergesortorder (clauseinfo)))) { return(LispNil); } } if ( !join || temp ) { /* restriction, ordering scan */ temp_node = lispCons (create_index_path (rel,index, clausegroup,join), LispNil); ip_list = nconc(ip_list,temp_node); d601 1 a601 1 } @ 1.7 log @reorganised header files @ text @d11 1 a11 1 /* RcsId("$Header: indxpath.c,v 1.6 89/08/04 13:23:14 goh Locked $"); */ d24 1 a24 1 #include "planner/lsyscache.h" @ 1.6 log @checkin for retrieve (x.all) @ text @d11 1 a11 1 /* RcsId("$Header: indxpath.c,v 1.5 89/08/01 14:39:50 goh Locked $"); */ a18 1 #include "internal.h"; d21 6 a26 4 #include "indxpath.h" #include "clauses.h" #include "lsyscache.h" #include "clauseinfo.h" d29 3 a31 1 /* #include "cfi.h" - where index_selectivity is defined */ a32 4 extern LispValue index_selectivity(); /* for now */ #define INDEXSCAN 1 #define List LispValue d497 1 a497 1 set_pathtype (pathnode,INDEXSCAN); @ 1.5 log @retrieve (x=1) checkin @ text @d11 1 a11 1 /* RcsId("$Header: indxpath.c,v 1.4 89/07/25 17:35:24 ong Exp $"); */ @ 1.4 log @Phase III @ text @d11 1 a11 1 /* RcsId("$Header: indxpath.c,v 1.3 89/07/21 09:01:54 ong Locked $"); */ d142 4 a145 3 sortpath =list (create_index_path (rel,index, LispNil, LispNil)); d196 1 a196 1 set_index (clauseinfo, d248 1 a248 1 constant_p (get_rightop (clause))) { d324 1 a324 1 list (new_matched_clauseinfo_list); d379 2 a380 2 LispValue leftop = get_leftop (clause); LispValue rightop = get_rightop (clause); d448 1 a448 1 get_other_rels(joininfo)); d488 1 a488 1 index_selectivity (nth (0,get_indexid (index)), d558 3 a560 2 list (create_index_path (rel,index, clausegroup,join)); @ 1.3 log @put the include files in theright order. NOTE: routine get_class is defined in relation.l, but seems to have been droppped in the new class definition. @ text @d11 1 a11 1 /* RcsId("$Header: indxpath.c,v 1.2 89/07/20 18:01:21 ong Exp $"); */ d67 1 d88 1 a88 2 CAR ((LispValue)get_class (CAR (indices))), d100 1 a100 1 get_class (index),clauseinfo_list, d182 1 a182 1 *match_index_orclauses (rel,index,indexkey,xclass,clauseinfo_list) d200 1 a200 1 get_index (clauseinfo))); d237 2 a238 1 LispValue clause,matched_indices; d240 1 a240 1 d249 1 a249 1 cons (index,matched_indices)); d327 1 a327 1 nconc (clausegroup, d334 5 a338 4 group_clauses_by_indexkey (rel,index, indexkeys, classes, remove (matched_clause, d341 1 a341 1 join)); d344 1 d346 1 d440 2 a441 2 get_class (index), get_clause_info(joininfo), d474 2 a475 2 LispValue clausegroup_list,index ; int rel; d482 2 a483 3 Path pathnode = MakePath(LispNil, LispNil, 0,0,0,0,0); d488 1 a488 1 get_class (index), d504 1 a504 1 nth (1,pagesel), @ 1.2 log @Phase II checkin. for some reason, the compiler doesn't know that LispValue and List are the same. So, I typecasted some functions to stop it from complaining. @ text @d11 1 a11 1 /* RcsId("$Header: indxpath.c,v 1.1 89/07/10 15:16:06 ong Locked $"); */ d18 1 a19 1 #include "pg_lisp.h"; d85 1 a85 1 CAR ((LispValue) get_indexkeys @ 1.1 log @Initial revision @ text @d11 1 a11 1 /* RcsId("$Header: indxpath.c,v 1.1 89/04/27 21:04:18 ong Locked $"); */ d20 6 a26 7 extern LispValue match_index_orclause(); extern LispValue group_clauses_by_indexkey(); extern LispValue match_clauses_to_indexkey(); extern LispValue indexable_joinclauses(); extern LispValue create_index_paths(); extern LispValue index_innerjoin(); extern void *match_index_orclauses(); d28 4 d33 1 a33 1 d76 6 d83 69 a151 72 /* 1. If this index has only one key, try matching it against * subclauses of an 'or' clause. The fields of the clauseinfo * nodes are marked with lists of the matching indices no path * are actually created. */ if ( 1 == length (get_indexkeys (car (indices)))) { match_index_orclauses (rel,car (indices), car (get_indexkeys (car (indices))), car (get_class (car (indices))), clauseinfo_list); } index = car (indices); /* 2. If the keys of this index match any of the available * restriction clauses, then create pathnodes corresponding * to each group of usable clauses. */ scanclausegroups = group_clauses_by_indexkey (rel,index,get_indexkeys (index), get_class (index),clauseinfo_list, LispNil,LispNil); scanpaths = LispNil; if ( consp (scanclausegroups) ) scanpaths = create_index_paths (rel,index, scanclausegroups, LispNil); /* 3. If this index can be used with any join clause, then * create pathnodes for each group of usable clauses. An * index can be used with a join clause if its ordering is * useful for a mergejoin, or if the index can possibly be * used for scanning the inner relation of a nestloop join. */ joinclausegroups = indexable_joinclauses (rel,index,joininfo_list); joinpaths = LispNil; if ( consp (joinclausegroups) ) { LispValue new_join_paths = create_index_paths (rel,index,joinclausegroups, LispTrue); LispValue innerjoin_paths = index_innerjoin (rel,joinclausegroups,index); set_innerjoin (rel,nconc (get_innerjoin(rel), innerjoin_paths)); joinpaths = new_join_paths; } /* 4. If this particular index hasn't already been used above, * then check to see if it can be used for ordering a * user-specified sort. If it can, add a pathnode for the * sorting scan. */ sortpath = LispNil; if ( valid_sortkeys(sortkeys) && null(scanclausegroups) && null(joinclausegroups) && equal(get_relid(sortkeys), get_relid (rel)) && equal_path_path_ordering(get_ordering (sortkeys), get_ordering (index)) && equal (get_sortkeys(sortkeys),get_indexkeys (index))) { sortpath =list (create_index_path (rel,index, LispNil, LispNil)); } append (scanpaths,joinpaths,sortpath, find_index_paths (rel,cdr (indices),clauseinfo_list, joininfo_list,sortkeys)); d153 1 a153 1 } /* function end */ d183 1 a183 1 LispValue rel,index,indexkey,xclass,clauseinfo_list ; d185 18 a202 20 LispValue clauseinfo; foreach (clauseinfo, clauseinfo_list) { if ( valid_or_clause (clauseinfo)) { /* Mark the 'or' clause with a list of indices which * match each of its subclauses. The list is * generated by adding 'index' to the existing * list where appropriate. */ set_index (clauseinfo, match_index_orclause (rel,index,indexkey, xclass, get_orclauseargs( get_clause(clauseinfo) ), get_index (clauseinfo) )); } } d236 3 a238 3 /* XXX - lisp mapcar -- may be wrong. */ LispValue clause,matched_indices; LispValue index_list = LispNil; d240 16 a255 16 foreach (clause,or_clauses) { if (is_clause (clause) && op_class(get_opno(get_op (clause)),xclass) && match_indexkey_operand (indexkey, get_leftop (clause), rel) && constant_p (get_rightop (clause))) { index_list = nappend1(index_list, cons (index,matched_indices)); } else { index_list = nappend1(index_list,matched_indices); } } return(index_list); d296 21 a316 22 if ( consp (clauseinfo_list) ) { /* If we can't find any matching clauses for the first of * the remaining keys, give up now. */ /* XXX - let form, maybe incorrect */ LispValue matched_clause = match_clauses_to_indexkey (rel,index, car(indexkeys), car(classes), clauseinfo_list,join); if ( matched_clause ) { LispValue new_matched_clauseinfo_list = cons (matched_clause,matched_clauseinfo_list); LispValue clausegroup = LispNil; if ( cdr (indexkeys) ) { clausegroup = group_clauses_by_indexkey (rel,index, cdr (indexkeys), cdr (classes), clauseinfo_list, d318 6 a323 6 join); } else { clausegroup = list (new_matched_clauseinfo_list); } d325 2 a326 2 if ( consp (clausegroup) ) { nconc (clausegroup, d328 4 a331 4 /* See if other clauses can be used for */ /* these remaining keys by ignoring the one */ /* that was just used (i.e., find all */ /* possible solutions). */ d333 10 a342 10 group_clauses_by_indexkey (rel,index, indexkeys, classes, remove (matched_clause, clauseinfo_list), matched_clauseinfo_list, join)); } } } d366 1 a366 1 LispValue d371 23 a393 17 LispValue clauseinfo = LispNil; foreach(clauseinfo,clauses) { LispValue clause = get_clause (clauseinfo); LispValue leftop = get_leftop (clause); LispValue rightop = get_rightop (clause); LispValue join_op = LispNil; LispValue temp1 = LispNil; LispValue temp2 = LispNil; if(null (join)) { join_op = LispNil; /* don't need it */ } else if (match_indexkey_operand (indexkey,rightop,rel)) { join_op = get_commutator (get_opno (get_op (clause))); } else if (match_indexkey_operand (indexkey,leftop,rel)) { join_op = get_opno (get_op (clause)); } d395 6 a400 13 temp1 = null(join_op) /* (op var const) */ && op_class(get_opno(get_op(clause)),xclass) && ( (qual_clause_p(clause) && equal_indexkey_var(indexkey,leftop)) /* also (op (func ... ) const) XXX FUNCS */ || function_index_clause_p(clause,rel,index)); temp2 = join_op && op_class(join_op,xclass) && !zerop(join_op) && join_clause_p(clause); if (temp1 || temp2) return(clauseinfo); } d429 2 a430 2 LispValue joininfo = LispNil; LispValue cg_list = LispNil; d432 8 a439 8 foreach(joininfo,joininfo_list) { LispValue clausegroups = group_clauses_by_indexkey (rel,index, get_indexkeys(index), get_class (index), get_clause_info(joininfo), LispNil, LispTrue); d441 7 a447 7 if ( consp (clausegroups)) { set_joinid (caar(clausegroups), get_other_rels(joininfo)); } cg_list = nconc(cg_list,clausegroups); } return(cg_list); d470 2 a471 1 LispValue rel,clausegroup_list,index ; d473 7 a479 2 LispValue clausegroup = LispNil; LispValue cg_list = LispNil; d481 25 a505 15 /* XXX Mapcar function */ foreach(clausegroup,clausegroup_list) { LispValue pathnode = create_node ("Path"); LispValue relattvals = get_joinvars (get_relid (rel),clausegroup); LispValue pagesel = index_selectivity (nth (0,get_indexid (index)), get_class (index), get_opnos (clausegroup), getrelid (get_relid (rel), _query_range_table_), nth (0,relattvals), nth (1,relattvals), nth (2,relattvals), length (clausegroup)); d507 3 a509 16 set_pathtype (pathnode,INDEXSCAN); set_parent (pathnode,rel); set_indexid (pathnode,get_indexid (index)); set_indexqual (pathnode,clausegroup); set_joinid (pathnode,get_joinid (car (clausegroup))); set_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))); cg_list = nappend1(cg_list,pathnode); } return(cg_list); d534 4 a537 4 /* XXX Mapcan */ LispValue clausegroup = LispNil; LispValue ip_list = LispNil; LispValue temp = LispTrue; d539 12 a550 3 foreach(clausegroup,clausegroup_list) { LispValue clauseinfo = LispNil; LispValue temp_node = LispNil; d552 8 a559 17 foreach (clauseinfo,clausegroup) { if ( !(join_clause_p(get_clause(clauseinfo)) && equal_path_merge_ordering( get_ordering(index), get_mergesortorder (clauseinfo)))) { return(LispNil); } } if ( !join || temp ) { /* restriction, ordering scan */ temp_node = list (create_index_path (rel,index, clausegroup,join)); ip_list = nconc(ip_list,temp_node); } } return(ip_list); @