/*------------------------------------------------------------------------- * * planmain.c-- * Routines to plan a single query * * Copyright (c) 1994, Regents of the University of California * * * IDENTIFICATION * $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.4 1997/04/29 04:32:50 vadim Exp $ * *------------------------------------------------------------------------- */ #include #include "postgres.h" #include "nodes/pg_list.h" #include "nodes/plannodes.h" #include "nodes/parsenodes.h" #include "nodes/relation.h" #include "nodes/makefuncs.h" #include "optimizer/planmain.h" #include "optimizer/internal.h" #include "optimizer/paths.h" #include "optimizer/clauses.h" #include "optimizer/keys.h" #include "optimizer/tlist.h" #include "optimizer/var.h" #include "optimizer/xfunc.h" #include "optimizer/cost.h" #include "tcop/dest.h" #include "utils/elog.h" #include "utils/palloc.h" #include "nodes/memnodes.h" #include "utils/mcxt.h" #include "utils/lsyscache.h" static Plan *subplanner(Query *root, List *flat_tlist, List *qual); static Result *make_result(List *tlist, Node *resconstantqual, Plan *subplan); static Plan *make_groupPlan(List **tlist, bool tuplePerGroup, List *groupClause, Plan *subplan); /* * 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 * * Returns a query plan. */ Plan * query_planner(Query *root, int command_type, List *tlist, List *qual) { List *constant_qual = NIL; List *flattened_tlist = NIL; List *level_tlist = NIL; Plan *subplan = (Plan*)NULL; Agg *aggplan = NULL; /* * A command without a target list or qualification is an error, * except for "delete foo". */ if (tlist==NIL && qual==NULL) { if (command_type == CMD_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 == CMD_NOTIFY) { return ((Plan*)make_seqscan(NIL, NIL, root->resultRelation, (Plan*)NULL)); } else return((Plan*)NULL); } /* * 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. */ qual = pull_constant_clauses(qual, &constant_qual); fix_opids(constant_qual); /* * Create a target list that consists solely of (resdom var) target * list entries, i.e., contains no arbitrary expressions. */ flattened_tlist = flatten_tlist(tlist); if (flattened_tlist) { level_tlist = flattened_tlist; } else { /* from old code. the logic is beyond me. - ay 2/95 */ level_tlist = tlist; } /* * 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 (flattened_tlist==NULL && qual==NULL) { switch (command_type) { case CMD_SELECT: case CMD_INSERT: return ((Plan*)make_result(tlist, (Node*)constant_qual, (Plan*)NULL)); break; case CMD_DELETE: case CMD_UPDATE: { SeqScan *scan = make_seqscan(tlist, (List *)NULL, root->resultRelation, (Plan*)NULL); if (constant_qual!=NULL) { return ((Plan*)make_result(tlist, (Node*)constant_qual, (Plan*)scan)); } else { return ((Plan*)scan); } } break; default: return ((Plan*)NULL); } } /* * Find the subplan (access path) and destructively modify the * target list of the newly created subplan to contain the appropriate * join references. */ subplan = subplanner(root, level_tlist, qual); set_tlist_references(subplan); /* * If we have a GROUP BY clause, insert a group node (with the appropriate * sort node.) */ if (root->groupClause != NULL) { bool tuplePerGroup; /* * decide whether how many tuples per group the Group node needs * to return. (Needs only one tuple per group if no aggregate is * present. Otherwise, need every tuple from the group to do the * aggregation.) */ tuplePerGroup = ( root->qry_aggs ) ? TRUE : FALSE; subplan = make_groupPlan(&tlist, tuplePerGroup, root->groupClause, subplan); } /* * If aggregate is present, insert the agg node */ if ( root->qry_aggs ) { aggplan = make_agg(tlist, root->qry_numAgg, root->qry_aggs); aggplan->plan.lefttree = subplan; /* * set the varno/attno entries to the appropriate references to * the result tuple of the subplans. (We need to set those in the * array of aggreg's in the Agg node also. Even though they're * pointers, after a few dozen's of copying, they're not the same as * those in the target list.) */ set_agg_tlist_references (aggplan); set_agg_agglist_references (aggplan); subplan = (Plan*)aggplan; tlist = aggplan->plan.targetlist; } /* * Build a result node linking the plan if we have constant quals */ if (constant_qual) { Plan *plan; plan = (Plan*)make_result(tlist, (Node*)constant_qual, subplan); /* * Change all varno's of the Result's node target list. */ set_result_tlist_references((Result*)plan); 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 * * But now nothing to do if there are GroupBy and/or Aggregates: * 1. make_groupPlan fixes tlist; 2. flatten_tlist_vars does nothing * with aggregates fixing only other entries (i.e. - GroupBy-ed and * so fixed by make_groupPlan). - vadim 04/05/97 */ if ( root->groupClause == NULL && aggplan == NULL ) { subplan->targetlist = flatten_tlist_vars(tlist, subplan->targetlist); } /* * Destructively modify the query plan's targetlist to add fjoin * lists to flatten functions that return sets of base types */ subplan->targetlist = generate_fjoin(subplan->targetlist); return (subplan); } /* * subplanner * * Subplanner creates an entire plan consisting of joins and scans * for processing a single level of attributes. * * flat-tlist is the flattened target list * qual is the qualification to be satisfied * * Returns a subplan. * */ static Plan * subplanner(Query *root, List *flat_tlist, List *qual) { 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.) */ root->base_relation_list_ = NIL; root->join_relation_list_ = NIL; initialize_base_rels_list(root, flat_tlist); initialize_base_rels_jinfo(root, qual); add_missing_vars_to_base_rels(root, flat_tlist); /* 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(root->base_relation_list_); final_relation_list = find_paths(root, root->base_relation_list_); if (final_relation_list) final_relation = (Rel*)lfirst (final_relation_list); else final_relation = (Rel*)NIL; #if 0 /* fix xfunc */ /* * Perform Predicate Migration on each path, to optimize and correctly * assess the cost of each before choosing the cheapest one. * -- JMH, 11/16/92 * * Needn't do so if the top rel is pruneable: that means there's no * expensive functions left to pull up. -- JMH, 11/22/92 */ if (XfuncMode != XFUNC_OFF && XfuncMode != XFUNC_NOPM && XfuncMode != XFUNC_NOPULL && !final_relation->pruneable) { List *pathnode; foreach(pathnode, final_relation->pathlist) { if (xfunc_do_predmig((Path*)lfirst(pathnode))) set_cheapest(final_relation, final_relation->pathlist); } } #endif /* * Determine the cheapest path and create a subplan corresponding to it. */ if (final_relation) { return (create_plan ((Path*)final_relation->cheapestpath)); }else { elog(NOTICE, "final relation is nil"); return(create_plan ((Path*)NULL)); } } /***************************************************************************** * *****************************************************************************/ static Result * make_result(List *tlist, Node *resconstantqual, Plan *subplan) { Result *node = makeNode(Result); Plan *plan = &node->plan; tlist = generate_fjoin(tlist); plan->cost = 0.0; plan->state = (EState *)NULL; plan->targetlist = tlist; plan->lefttree = subplan; plan->righttree = NULL; node->resconstantqual = resconstantqual; node->resstate = NULL; return(node); } /***************************************************************************** * *****************************************************************************/ static Plan * make_groupPlan(List **tlist, bool tuplePerGroup, List *groupClause, Plan *subplan) { List *sort_tlist; List *sl, *gl; List *glc = listCopy (groupClause); List *otles = NIL; /* list of removed non-GroupBy entries */ List *otlvars = NIL; /* list of var in them */ int otlvcnt; Sort *sortplan; Group *grpplan; int numCols; AttrNumber *grpColIdx; int keyno = 1; int last_resno = 1; numCols = length(groupClause); grpColIdx = (AttrNumber *)palloc(sizeof(AttrNumber)*numCols); sort_tlist = new_unsorted_tlist(*tlist); /* it's copy */ /* * Make template TL for subplan, Sort & Group: * 1. If there are aggregates (tuplePerGroup is true) then take * away non-GroupBy entries and re-set resno-s accordantly. * 2. Make grpColIdx * * Note: we assume that TLEs in *tlist are ordered in accordance * with their resdom->resno. */ foreach (sl, sort_tlist) { Resdom *resdom = NULL; TargetEntry *te = (TargetEntry *) lfirst (sl); foreach (gl, glc) { GroupClause *grpcl = (GroupClause*)lfirst(gl); if ( grpcl->entry->resdom->resno == te->resdom->resno ) { resdom = te->resdom; resdom->reskey = keyno; resdom->reskeyop = get_opcode (grpcl->grpOpoid); resdom->resno = last_resno; /* re-set */ grpColIdx[keyno-1] = last_resno++; keyno++; glc = lremove (lfirst (gl), glc); /* TLE found for it */ break; } } /* * Non-GroupBy entry: remove it from Group/Sort TL if there are * aggregates in query - it will be evaluated by Aggregate plan */ if ( resdom == NULL ) { if ( tuplePerGroup ) { otlvars = nconc (otlvars, pull_var_clause (te->expr)); otles = lcons (te, otles); sort_tlist = lremove (te, sort_tlist); } else te->resdom->resno = last_resno++; } } if ( length (glc) != 0 ) { elog(WARN, "group attribute disappeared from target list"); } /* * If non-GroupBy entries were removed from TL - we are to add Vars for * them to the end of TL if there are no such Vars in TL already. */ otlvcnt = length (otlvars); foreach (gl, otlvars) { Var *v = (Var*)lfirst (gl); if ( tlist_member (v, sort_tlist) == NULL ) { sort_tlist = lappend (sort_tlist, create_tl_element (v, last_resno)); last_resno++; } else /* already in TL */ otlvcnt--; } /* Now otlvcnt is number of Vars added in TL for non-GroupBy entries */ /* Make TL for subplan: substitute Vars from subplan TL into new TL */ sl = flatten_tlist_vars (sort_tlist, subplan->targetlist); subplan->targetlist = new_unsorted_tlist (sl); /* there */ /* * Make Sort/Group TL : * 1. make Var nodes (with varno = 1 and varnoold = -1) for all * functions, 'couse they will be evaluated by subplan; * 2. for real Vars: set varno = 1 and varattno to its resno in subplan */ foreach (sl, sort_tlist) { TargetEntry *te = (TargetEntry *) lfirst (sl); Resdom *resdom = te->resdom; Node *expr = te->expr; if ( IsA (expr, Var) ) { #if 0 /* subplanVar->resdom->resno expected to be = te->resdom->resno */ TargetEntry *subplanVar; subplanVar = match_varid ((Var*)expr, subplan->targetlist); ((Var*)expr)->varattno = subplanVar->resdom->resno; #endif ((Var*)expr)->varattno = te->resdom->resno; ((Var*)expr)->varno = 1; } else te->expr = (Node*) makeVar (1, resdom->resno, resdom->restype, -1, resdom->resno); } sortplan = make_sort(sort_tlist, _TEMP_RELATION_ID_, subplan, numCols); sortplan->plan.cost = subplan->cost; /* XXX assume no cost */ /* * make the Group node */ sort_tlist = copyObject (sort_tlist); grpplan = make_group(sort_tlist, tuplePerGroup, numCols, grpColIdx, sortplan); /* * Make TL for parent: "restore" non-GroupBy entries (if they * were removed) and set resno-s of others accordantly. */ sl = sort_tlist; sort_tlist = NIL; /* to be new parent TL */ foreach (gl, *tlist) { List *temp = NIL; TargetEntry *te = (TargetEntry *) lfirst (gl); foreach (temp, otles) /* Is it removed non-GroupBy entry ? */ { TargetEntry *ote = (TargetEntry *) lfirst (temp); if ( ote->resdom->resno == te->resdom->resno ) { otles = lremove (ote, otles); break; } } if ( temp == NIL ) /* It's "our" TLE - we're to return */ { /* it from Sort/Group plans */ TargetEntry *my = (TargetEntry *) lfirst (sl); /* get it */ sl = sl->next; /* prepare for the next "our" */ my = copyObject (my); my->resdom->resno = te->resdom->resno; /* order of parent TL */ sort_tlist = lappend (sort_tlist, my); continue; } /* else - it's TLE of an non-GroupBy entry */ sort_tlist = lappend (sort_tlist, copyObject(te)); } /* * Pure non-GroupBy entries Vars were at the end of Group' TL. * They shouldn't appear in parent TL, all others shouldn't * disappear. */ Assert ( otlvcnt == length (sl) ); Assert ( length (otles) == 0 ); *tlist = sort_tlist; return (Plan*)grpplan; }