/* * FILE * planmain * * DESCRIPTION * Routines to plan a single query * */ /* RcsId ("$Header: /private/postgres/src/planner/plan/RCS/planmain.c,v 1.39 1992/07/23 15:37:36 joey Exp $"); */ /* * EXPORTS * Plan query_planner(); */ #include "nodes/pg_lisp.h" #include "nodes/plannodes.h" #include "nodes/plannodes.a.h" #include "nodes/relation.h" #include "nodes/relation.a.h" #include "parser/parse.h" #include "planner/internal.h" #include "planner/allpaths.h" #include "planner/clause.h" #include "planner/createplan.h" #include "planner/keys.h" #include "planner/planmain.h" #include "planner/setrefs.h" #include "planner/sortresult.h" #include "planner/sortresult.h" #include "planner/tlist.h" #include "tcop/dest.h" #include "utils/log.h" #include "nodes/mnodes.h" #include "utils/mcxt.h" extern int testFlag; /* * query_planner * * Routine to create a query plan. It does so by first creating a * subplan for the topmost level of attributes in the query. Then, * it modifies all target list and qualifications to consider the next * level of nesting and creates a plan for this modified query by * recursively calling itself. The two pieces are then merged together * by creating a result node that indicates which attributes should * be placed where and any relation level qualifications to be * satisfied. * * 'command-type' is the query command, e.g., retrieve, delete, etc. * 'tlist' is the target list of the query * 'qual' is the qualification of the query * 'currentlevel' is the current nesting level * 'maxlevel' is the maximum nesting level in this query * * Returns a query plan. * */ /* .. init-query-planner, query_planner */ Plan query_planner (command_type,tlist,qual,currentlevel,maxlevel) int command_type; List tlist,qual; int currentlevel; int maxlevel ; { LispValue constant_qual = LispNil; LispValue sortkeys = LispNil; LispValue flattened_tlist = LispNil; List level_tlist = LispNil; List result_of_flatten_tlist = LispNil; List agg_tlist = LispNil; List all_but_agg_tlist = LispNil; int aggidnum = -17; /* okay, a hack on uniquness */ Plan thePlan = (Plan)NULL; Plan subplan = (Plan)NULL; List subtlist = LispNil; Plan restplan = (Plan)NULL; List resttlist = LispNil; List relation_level_clauses = LispNil; Plan plan = (Plan)NULL; /* For the topmost nesting level, */ /* 1. Pull out any non-variable qualifications so these can be put in */ /* the topmost result node. The opids for the remaining */ /* qualifications will be changed to regprocs later. */ /* ------ * NOTE: we used to have one field called 'opno' in the Oper * nodes which used to be also be called 'opid' in some comments. * This field was either the pg_operator oid, or the * regproc oid. However now we have two separate * fields, the 'opno' (pg_operator oid) and the 'opid' (pg_proc * oid) so things are a little bit more clear now... [sp.] * ------ */ /* 2. Determine the keys on which the result is to be sorted. */ /* 3. Create a target list that consists solely of (resdom var) target */ /* list entries, i.e., contains no arbitrary expressions. */ if ( currentlevel == 1) { /* A command without a target list or qualification is an error, */ /* except for "delete foo". */ if (null (tlist) && null (qual)) { if ( command_type == DELETE || /* Total hack here. I don't know how to handle statements like notify in action bodies. Notify doesn't return anything but scans a system table. */ command_type == NOTIFY) { return ((Plan)make_seqscan(LispNil, LispNil, (Index)CInteger(_query_result_relation_), (Plan)NULL)); } else return((Plan)NULL); } constant_qual = pull_constant_clauses (qual); qual = nset_difference (qual,constant_qual); fix_opids (constant_qual); sortkeys = relation_sortkeys (tlist); /* flatten_tlist will now return (var, aggs, rest) */ result_of_flatten_tlist = flatten_tlist(tlist); flattened_tlist = CAR(result_of_flatten_tlist); agg_tlist = CADR(result_of_flatten_tlist); result_of_flatten_tlist = CDR(result_of_flatten_tlist); all_but_agg_tlist = CADR(result_of_flatten_tlist); if (flattened_tlist) level_tlist = flattened_tlist; else if (tlist) level_tlist = all_but_agg_tlist; /* orig_tlist minus the aggregates */ else level_tlist = (List)NULL; } if(agg_tlist) { if(all_but_agg_tlist) { thePlan = query_planner(command_type, all_but_agg_tlist, qual, currentlevel, maxlevel); } else { /* all we have are aggregates */ thePlan = (Plan)make_agg(CAR(agg_tlist), --aggidnum); /* also, there should never be a case by now where we neither * have aggs nor all_but_aggs */ agg_tlist = CDR(agg_tlist); } if(agg_tlist != NULL) { /* are there any aggs left */ thePlan = make_aggplan(thePlan, agg_tlist, aggidnum); } return(thePlan); } /* A query may have a non-variable target list and a non-variable */ /* qualification only under certain conditions: */ /* - the query creates all-new tuples, or */ /* - the query is a replace (a scan must still be done in this case). */ if ((0 == maxlevel || (1 == currentlevel && null (flattened_tlist))) && null (qual)) { switch (command_type) { case RETRIEVE : case APPEND : return ((Plan)make_result (tlist, LispNil, constant_qual, (Plan)NULL, (Plan)NULL)); break; case DELETE : case REPLACE : { /* XXX - let form, maybe incorrect */ SeqScan scan = make_seqscan (tlist, LispNil, (Index)CInteger( _query_result_relation_), (Plan)NULL); if ( consp (constant_qual) ) { return ((Plan)make_result (tlist, LispNil, constant_qual, (Plan)scan, (Plan)NULL)); } else { return ((Plan)scan); } } break; default: /* return nil */ return((Plan)NULL); } } /* Find the subplan (access path) for attributes at this nesting level */ /* and destructively modify the target list of the newly created */ /* subplan to contain the appropriate join references. */ subplan = subplanner (level_tlist, tlist, qual, currentlevel, sortkeys); subtlist = get_qptargetlist (subplan); set_tlist_references (subplan); /* If there are further nesting levels, call the planner again to */ /* create subplans for lower levels of nesting. Modify the target */ /* list and qualifications to reflect the new nesting level. */ if (currentlevel != maxlevel) { elog(WARN, "level mismatch -- should never happen with new nested dot parsing scheme!"); } /* Build a result node linking the plan for deeper nesting levels and */ /* the subplan for this level. Note that a plan that has no right */ /* subtree may still have relation level and constant quals, so we */ /* still have to build an appropriate result node. */ relation_level_clauses = pull_relation_level_clauses (qual); if ( restplan || relation_level_clauses || constant_qual) { List resttlist = LispNil; List subtlist = LispNil; Plan plan; if ( restplan ) resttlist = get_qptargetlist (restplan); subtlist = get_qptargetlist (subplan); plan = (Plan)make_result (new_result_tlist (tlist, subtlist, resttlist, currentlevel, valid_sortkeys(sortkeys)), new_result_qual(relation_level_clauses, subtlist, resttlist, currentlevel), constant_qual, subplan, restplan); /* * Change all varno's of the Result's node target list. */ set_result_tlist_references((Result)plan); if ( valid_numkeys (sortkeys) ) return (sort_level_result (plan, CInteger(sortkeys))); else return (plan); } /* * fix up the flattened target list of the plan root node so that * expressions are evaluated. this forces expression evaluations * that may involve expensive function calls to be delayed to * the very last stage of query execution. this could be bad. * but it is joey's responsibility to optimally push these * expressions down the plan tree. -- Wei */ set_qptargetlist (subplan, flatten_tlist_vars (tlist, get_qptargetlist (subplan))); /* * Destructively modify the query plan's targetlist to add fjoin * lists to flatten functions that return sets of base types */ set_qptargetlist(subplan, generate_fjoin(get_qptargetlist(subplan))); /* If a sort is required, explicitly sort this subplan since: */ /* there is only one level of attributes in this query, and */ /*the sort spans across expressions and/or multiple relations and so */ /* indices were not considered in planning the sort. */ if ( valid_numkeys (sortkeys) ) return (sort_level_result (subplan,CInteger(sortkeys))); else return (subplan); } /* function end */ /* * subplanner * * Subplanner creates an entire plan consisting of joins and scans * for processing a single level of attributes. Nested attributes are * transparent (i.e., essentially ignored) from here on. * * 'flat-tlist' is the flattened target list * --which now is of the form (vars, aggs)--, jc * 'original-tlist' is the unflattened target list * 'qual' is the qualification to be satisfied * 'level' is the current nesting level * * Returns a subplan. * */ /* .. query_planner */ Plan subplanner (flat_tlist,original_tlist,qual,level,sortkeys) LispValue flat_tlist,original_tlist,qual,sortkeys ; int level; { Rel final_relation; List final_relation_list; /* Initialize the targetlist and qualification, adding entries to */ /* *query-relation-list* as relation references are found (e.g., in the */ /* qualification, the targetlist, etc.) */ _base_relation_list_ = LispNil; _join_relation_list_ = LispNil; initialize_targetlist (flat_tlist); initialize_qualification (qual); /* Find all possible scan and join paths. */ /* Mark all the clauses and relations that can be processed using special */ /* join methods, then do the exhaustive path search. */ initialize_join_clause_info (_base_relation_list_); final_relation_list = find_paths (_base_relation_list_, level, sortkeys); if (final_relation_list) final_relation = (Rel)CAR (final_relation_list); else final_relation = (Rel)LispNil; /* If we want a sorted result and indices could have been used to do so, */ /* then explicitly sort those paths that weren't sorted by indices so we */ /* can determine whether using the implicit sort (index) is better than an */ /* explicit one. */ if ( valid_sortkeys (sortkeys)) { sort_relation_paths (get_pathlist (final_relation), sortkeys, final_relation, compute_targetlist_width(original_tlist)); } /* Determine the cheapest path and create a subplan corresponding to it. */ if (final_relation) { if (testFlag) { List planlist = LispNil; List pathlist = LispNil; LispValue x; Path path; Plan plan; Choose chooseplan; pathlist = get_pathlist(final_relation); foreach (x, pathlist) { path = (Path)CAR(x); plan = create_plan(path); planlist = nappend1(planlist, (LispValue)plan); } chooseplan = RMakeChoose(); set_chooseplanlist(chooseplan, planlist); set_qptargetlist((Plan)chooseplan, get_qptargetlist(plan)); return (Plan)chooseplan; } return (create_plan ((Path)get_cheapestpath (final_relation))); } else { printf(" Warn: final relation is nil \n"); return(create_plan ((Path)NULL)); } } /* function end */ Result make_result( tlist,resrellevelqual,resconstantqual,left,right) List tlist; List resrellevelqual,resconstantqual; Plan left,right; { Result node = RMakeResult(); tlist = generate_fjoin(tlist); set_cost((Plan) node, 0.0); set_fragment((Plan) node, 0); set_state((Plan) node, NULL); set_qptargetlist((Plan)node, tlist); set_qpqual((Plan) node, LispNil); set_lefttree((Plan)node, (PlanPtr)left); set_righttree((Plan)node, (PlanPtr)right); set_resrellevelqual(node, resrellevelqual); set_resconstantqual(node, resconstantqual); set_resstate(node, NULL); return(node); } /* for modifying in case of aggregates. * we know that there are aggregates in the tlist*/ Plan make_aggplan(subplan, agg_tlist, aggidnum) Plan subplan; List agg_tlist; int aggidnum; { List agg_tl_entry = LispNil; List add_to_tl = LispNil; NestLoop joinnode = (NestLoop)NULL; LispValue entry = LispNil; List level_tlist = LispNil; Agg aggnode; /* extern search_quals(); */ /* we're assuming that subplan is not null from the caller*/ agg_tl_entry = CAR(agg_tlist); aggnode = make_agg(agg_tl_entry, --aggidnum); set_qptargetlist(subplan, nconc(get_qptargetlist(subplan), get_qptargetlist((Plan)aggnode))); level_tlist = get_qptargetlist(subplan); joinnode = make_nestloop(level_tlist, LispNil, (Plan)aggnode, subplan); /* inner tree is the aggregate, outer tree is the rest of * the plan. quals are nil here since we don't have aggregate * functions yet. */ if(CDR(agg_tlist)) { /* is this the last agg_tlist entry? */ /* if not */ return make_aggplan((Plan)joinnode, CDR(agg_tlist), aggidnum); /* XXX jc. type problem with joinnode and Plan subplan? */ } else { /* if so */ return((Plan) joinnode); } } bool plan_isomorphic(p1, p2) Plan p1, p2; { if (p1 == NULL) return (p2 == NULL); if (p2 == NULL) return (p1 == NULL); if (IsA(p1,Join) && IsA(p2,Join)) { return (plan_isomorphic(get_lefttree(p1), get_lefttree(p2)) && plan_isomorphic(get_righttree(p1), get_righttree(p2))); } if (IsA(p1,Scan) && IsA(p2,Scan)) { if (get_scanrelid((Scan)p1) == get_scanrelid((Scan)p2)) if (get_scanrelid((Scan)p1) == _TEMP_RELATION_ID_) return plan_isomorphic(get_lefttree(p1), get_lefttree(p2)); else return true; else if (get_scanrelid((Scan)p1) == _TEMP_RELATION_ID_) return plan_isomorphic(get_lefttree(p1), p2); else if (get_scanrelid((Scan)p2) == _TEMP_RELATION_ID_) return plan_isomorphic(p1, get_lefttree(p2)); return false; } if (IsA(p1,Temp) || IsA(p1,Hash) || (IsA(p1,Scan) && get_scanrelid((Scan)p1) == _TEMP_RELATION_ID_)) return plan_isomorphic(get_lefttree(p1), p2); if (IsA(p2,Temp) || IsA(p2,Hash) || (IsA(p2,Scan) && get_scanrelid((Scan)p2) == _TEMP_RELATION_ID_)) return plan_isomorphic(p1, get_lefttree(p2)); return false; } List group_planlist(planlist) List planlist; { List plangroups = LispNil; Plan p1, p2; List plist; List g, x; plist = planlist; while (!lispNullp(plist)) { p1 = (Plan)CAR(plist); g = lispCons((LispValue)p1, LispNil); foreach (x, CDR(plist)) { p2 = (Plan)CAR(x); if (plan_isomorphic(p1, p2)) { g = nappend1(g, (LispValue)p2); } } plist = nset_difference(plist, g); plangroups = nappend1(plangroups, g); } return plangroups; } bool allNestLoop(plan) Plan plan; { if (plan == NULL) return true; if (IsA(plan,Temp) || (IsA(plan,Scan) && get_scanrelid((Scan)plan) == _TEMP_RELATION_ID_)) return allNestLoop(get_lefttree(plan)); if (IsA(plan,NestLoop)) { return allNestLoop(get_lefttree(plan)) && allNestLoop(get_righttree(plan)); } if (IsA(plan,Join)) return false; return true; } Plan pickNestLoopPlan(plangroup) List plangroup; { LispValue x; Plan p; foreach (x, plangroup) { p = (Plan)CAR(x); if (allNestLoop(p)) return p; } return NULL; } void setPlanStats(p1, p2) Plan p1, p2; { if (p1 == NULL || p2 == NULL) return; if (IsA(p1,Join) && IsA(p2,Join)) { set_plan_size(p2, get_plan_size(p1)); setPlanStats(get_lefttree(p1), get_lefttree(p2)); /* setPlanStats(get_righttree(p1), get_righttree(p2)); */ return; } if (IsA(p1,Temp) || IsA(p1,Hash) || (IsA(p1,Scan) && get_scanrelid((Scan)p1) == _TEMP_RELATION_ID_)) { setPlanStats(get_lefttree(p1), p2); return; } if (IsA(p2,Temp) || IsA(p2,Hash) || (IsA(p2,Scan) && get_scanrelid((Scan)p2) == _TEMP_RELATION_ID_)) { set_plan_size(p2, get_plan_size(p1)); setPlanStats(p1, get_lefttree(p2)); return; } if (IsA(p1,Scan) && IsA(p2,Scan)) { set_plan_size(p2, get_plan_size(p1)); return; } return; } void resetPlanStats(p) Plan p; { if (p == NULL) return; set_plan_size(p, 0); if (IsA(p,Join)) { resetPlanStats(get_lefttree(p)); resetPlanStats(get_righttree(p)); return; } if (IsA(p,Scan)) { if (get_scanrelid((Scan)p) == _TEMP_RELATION_ID_) resetPlanStats(get_lefttree(p)); return; } resetPlanStats(get_lefttree(p)); return; } void setPlanGroupStats(plan, planlist) Plan plan; List planlist; { List x; Plan p; foreach (x, planlist) { p = (Plan)CAR(x); setPlanStats(plan, p); } } bool _exec_collect_stats_ = false; /* * XXX mao speaking: * * i assume that this routine is used by some planner wizard to * collect actual plan execution costs, and that it's not run * during ordinary postgres processing. the planner shouldn't * be executing queries directly, right? */ List setRealPlanStats(parsetree, planlist) List parsetree; List planlist; { List plangroups; List plangroup; LispValue x; List ordered_planlist; Plan nlplan; _exec_collect_stats_ = true; plangroups = group_planlist(planlist); ordered_planlist = LispNil; foreach (x, plangroups) { plangroup = CAR(x); nlplan = pickNestLoopPlan(plangroup); if (nlplan == NULL) { elog(NOTICE, "no nestloop plan in plan group!"); break; } if (IsA(nlplan,Join)) { resetPlanStats(nlplan); p_plan(nlplan); ResetUsage(); ProcessQuery(parsetree, nlplan, (char *) NULL, (ObjectId *) NULL, 0, None); ShowUsage(); plangroup = nLispRemove(plangroup, (LispValue)nlplan); setPlanGroupStats(nlplan, plangroup); } else { ordered_planlist = plangroup; break; } ordered_planlist = nconc(ordered_planlist, plangroup); } _exec_collect_stats_ = false; return ordered_planlist; } bool plan_contain_redundant_hashjoin(plan) Plan plan; { Plan outerplan, innerplan; int outerpages, innerpages; if (plan == NULL) return false; if (IsA(plan,HashJoin)) { outerplan = (Plan) get_lefttree(plan); innerplan = (Plan) get_lefttree((Plan)get_righttree(plan)); outerpages = page_size(get_plan_size(outerplan), get_plan_width(outerplan)); innerpages = page_size(get_plan_size(innerplan), get_plan_width(innerplan)); if (!IsA(outerplan,Join) && outerpages < innerpages) return true; } if (IsA(plan,Join)) return plan_contain_redundant_hashjoin(get_lefttree(plan)) || plan_contain_redundant_hashjoin(get_righttree(plan)); if (IsA(plan,Temp) || IsA(plan,Hash) || (IsA(plan,Scan) && get_scanrelid((Scan)plan) == _TEMP_RELATION_ID_)) return plan_contain_redundant_hashjoin(get_lefttree(plan)); return false; } List pruneHashJoinPlans(planlist) List planlist; { LispValue x; Plan plan; List retlist; retlist = LispNil; foreach (x, planlist) { plan = (Plan)CAR(x); if (!plan_contain_redundant_hashjoin(plan)) retlist = nappend1(retlist, (LispValue)plan); } return retlist; }