* planner.c
* The query optimizer external interface.
*
- * Portions Copyright (c) 1996-2006, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
*
* IDENTIFICATION
- * $PostgreSQL: pgsql/src/backend/optimizer/plan/planner.c,v 1.208 2006/08/12 02:52:04 tgl Exp $
+ * $PostgreSQL: pgsql/src/backend/optimizer/plan/planner.c,v 1.215 2007/02/22 22:00:24 tgl Exp $
*
*-------------------------------------------------------------------------
*/
#include "parser/parse_expr.h"
#include "parser/parse_oper.h"
#include "parser/parsetree.h"
+#include "utils/lsyscache.h"
#include "utils/syscache.h"
-ParamListInfo PlannerBoundParamList = NULL; /* current boundParams */
-
-
/* Expression kind codes for preprocess_expression */
#define EXPRKIND_QUAL 0
#define EXPRKIND_TARGET 1
static double preprocess_limit(PlannerInfo *root,
double tuple_fraction,
int64 *offset_est, int64 *count_est);
+static Oid *extract_grouping_ops(List *groupClause);
static bool choose_hashed_grouping(PlannerInfo *root, double tuple_fraction,
Path *cheapest_path, Path *sorted_path,
- double dNumGroups, AggClauseCounts *agg_counts);
-static bool hash_safe_grouping(PlannerInfo *root);
+ Oid *groupOperators, double dNumGroups,
+ AggClauseCounts *agg_counts);
static List *make_subplanTargetList(PlannerInfo *root, List *tlist,
AttrNumber **groupColIdx, bool *need_tlist_eval);
static void locate_grouping_columns(PlannerInfo *root,
* Query optimizer entry point
*
*****************************************************************************/
-Plan *
+PlannedStmt *
planner(Query *parse, bool isCursor, int cursorOptions,
ParamListInfo boundParams)
{
+ PlannedStmt *result;
+ PlannerGlobal *glob;
double tuple_fraction;
- Plan *result_plan;
- Index save_PlannerQueryLevel;
- List *save_PlannerParamList;
- ParamListInfo save_PlannerBoundParamList;
+ PlannerInfo *root;
+ Plan *top_plan;
+ ListCell *lp,
+ *lr;
/*
- * The planner can be called recursively (an example is when
- * eval_const_expressions tries to pre-evaluate an SQL function). So,
- * these global state variables must be saved and restored.
- *
- * Query level and the param list cannot be moved into the per-query
- * PlannerInfo structure since their whole purpose is communication across
- * multiple sub-queries. Also, boundParams is explicitly info from outside
- * the query, and so is likewise better handled as a global variable.
- *
- * Note we do NOT save and restore PlannerPlanId: it exists to assign
- * unique IDs to SubPlan nodes, and we want those IDs to be unique for the
- * life of a backend. Also, PlannerInitPlan is saved/restored in
- * subquery_planner, not here.
+ * Set up global state for this planner invocation. This data is needed
+ * across all levels of sub-Query that might exist in the given command,
+ * so we keep it in a separate struct that's linked to by each per-Query
+ * PlannerInfo.
*/
- save_PlannerQueryLevel = PlannerQueryLevel;
- save_PlannerParamList = PlannerParamList;
- save_PlannerBoundParamList = PlannerBoundParamList;
+ glob = makeNode(PlannerGlobal);
- /* Initialize state for handling outer-level references and params */
- PlannerQueryLevel = 0; /* will be 1 in top-level subquery_planner */
- PlannerParamList = NIL;
- PlannerBoundParamList = boundParams;
+ glob->boundParams = boundParams;
+ glob->paramlist = NIL;
+ glob->subplans = NIL;
+ glob->subrtables = NIL;
+ glob->finalrtable = NIL;
/* Determine what fraction of the plan is likely to be scanned */
if (isCursor)
}
/* primary planning entry point (may recurse for subqueries) */
- result_plan = subquery_planner(parse, tuple_fraction, NULL);
-
- /* check we popped out the right number of levels */
- Assert(PlannerQueryLevel == 0);
+ top_plan = subquery_planner(glob, parse, 1, tuple_fraction, &root);
/*
* If creating a plan for a scrollable cursor, make sure it can run
*/
if (isCursor && (cursorOptions & CURSOR_OPT_SCROLL))
{
- if (!ExecSupportsBackwardScan(result_plan))
- result_plan = materialize_finished_plan(result_plan);
+ if (!ExecSupportsBackwardScan(top_plan))
+ top_plan = materialize_finished_plan(top_plan);
}
/* final cleanup of the plan */
- result_plan = set_plan_references(result_plan, parse->rtable);
-
- /* executor wants to know total number of Params used overall */
- result_plan->nParamExec = list_length(PlannerParamList);
+ Assert(glob->finalrtable == NIL);
+ top_plan = set_plan_references(glob, top_plan, root->parse->rtable);
+ /* ... and the subplans (both regular subplans and initplans) */
+ Assert(list_length(glob->subplans) == list_length(glob->subrtables));
+ forboth(lp, glob->subplans, lr, glob->subrtables)
+ {
+ Plan *subplan = (Plan *) lfirst(lp);
+ List *subrtable = (List *) lfirst(lr);
- /* restore state for outer planner, if any */
- PlannerQueryLevel = save_PlannerQueryLevel;
- PlannerParamList = save_PlannerParamList;
- PlannerBoundParamList = save_PlannerBoundParamList;
+ lfirst(lp) = set_plan_references(glob, subplan, subrtable);
+ }
- return result_plan;
+ /* build the PlannedStmt result */
+ result = makeNode(PlannedStmt);
+
+ result->commandType = parse->commandType;
+ result->canSetTag = parse->canSetTag;
+ result->planTree = top_plan;
+ result->rtable = glob->finalrtable;
+ result->resultRelations = root->resultRelations;
+ result->into = parse->into;
+ result->subplans = glob->subplans;
+ result->returningLists = root->returningLists;
+ result->rowMarks = parse->rowMarks;
+ result->nParamExec = list_length(glob->paramlist);
+
+ return result;
}
* Invokes the planner on a subquery. We recurse to here for each
* sub-SELECT found in the query tree.
*
+ * glob is the global state for the current planner run.
* parse is the querytree produced by the parser & rewriter.
+ * level is the current recursion depth (1 at the top-level Query).
* tuple_fraction is the fraction of tuples we expect will be retrieved.
* tuple_fraction is interpreted as explained for grouping_planner, below.
*
- * If subquery_pathkeys isn't NULL, it receives a list of pathkeys indicating
- * the output sort ordering of the completed plan.
+ * If subroot isn't NULL, we pass back the query's final PlannerInfo struct;
+ * among other things this tells the output sort ordering of the plan.
*
* Basically, this routine does the stuff that should only be done once
* per Query object. It then calls grouping_planner. At one time,
*--------------------
*/
Plan *
-subquery_planner(Query *parse, double tuple_fraction,
- List **subquery_pathkeys)
+subquery_planner(PlannerGlobal *glob, Query *parse,
+ Index level, double tuple_fraction,
+ PlannerInfo **subroot)
{
- List *saved_initplan = PlannerInitPlan;
- int saved_planid = PlannerPlanId;
+ int num_old_subplans = list_length(glob->subplans);
PlannerInfo *root;
Plan *plan;
List *newHaving;
ListCell *l;
- /* Set up for a new level of subquery */
- PlannerQueryLevel++;
- PlannerInitPlan = NIL;
-
/* Create a PlannerInfo data structure for this subquery */
root = makeNode(PlannerInfo);
root->parse = parse;
+ root->glob = glob;
+ root->query_level = level;
+ root->planner_cxt = CurrentMemoryContext;
+ root->init_plans = NIL;
+ root->eq_classes = NIL;
root->in_info_list = NIL;
root->append_rel_list = NIL;
* initPlan list and extParam/allParam sets for plan nodes, and attach the
* initPlans to the top plan node.
*/
- if (PlannerPlanId != saved_planid || PlannerQueryLevel > 1)
- SS_finalize_plan(plan, parse->rtable);
+ if (list_length(glob->subplans) != num_old_subplans ||
+ root->query_level > 1)
+ SS_finalize_plan(root, plan);
- /* Return sort ordering info if caller wants it */
- if (subquery_pathkeys)
- *subquery_pathkeys = root->query_pathkeys;
-
- /* Return to outer subquery context */
- PlannerQueryLevel--;
- PlannerInitPlan = saved_initplan;
- /* we do NOT restore PlannerPlanId; that's not an oversight! */
+ /* Return internal info if caller wants it */
+ if (subroot)
+ *subroot = root;
return plan;
}
/*
* If the query has any join RTEs, replace join alias variables with
* base-relation variables. We must do this before sublink processing,
- * else sublinks expanded out from join aliases wouldn't get processed.
- * We can skip it in VALUES lists, however, since they can't contain
- * any Vars at all.
+ * else sublinks expanded out from join aliases wouldn't get processed. We
+ * can skip it in VALUES lists, however, since they can't contain any Vars
+ * at all.
*/
if (root->hasJoinRTEs && kind != EXPRKIND_VALUES)
expr = flatten_join_alias_vars(root, expr);
* still must do it for quals (to get AND/OR flatness); and if we are in a
* subquery we should not assume it will be done only once.
*
- * For VALUES lists we never do this at all, again on the grounds that
- * we should optimize for one-time evaluation.
+ * For VALUES lists we never do this at all, again on the grounds that we
+ * should optimize for one-time evaluation.
*/
if (kind != EXPRKIND_VALUES &&
(root->parse->jointree->fromlist != NIL ||
kind == EXPRKIND_QUAL ||
- PlannerQueryLevel > 1))
+ root->query_level > 1))
expr = eval_const_expressions(expr);
/*
/* Expand SubLinks to SubPlans */
if (root->parse->hasSubLinks)
- expr = SS_process_sublinks(expr, (kind == EXPRKIND_QUAL));
+ expr = SS_process_sublinks(root, expr, (kind == EXPRKIND_QUAL));
/*
* XXX do not insert anything here unless you have grokked the comments in
*/
/* Replace uplevel vars with Param nodes (this IS possible in VALUES) */
- if (PlannerQueryLevel > 1)
- expr = SS_replace_correlation_vars(expr);
+ if (root->query_level > 1)
+ expr = SS_replace_correlation_vars(root, expr);
/*
* If it's a qual or havingQual, convert it to implicit-AND format. (We
subroot.in_info_list = (List *)
adjust_appendrel_attrs((Node *) root->in_info_list,
appinfo);
+ subroot.init_plans = NIL;
/* There shouldn't be any OJ info to translate, as yet */
Assert(subroot.oj_info_list == NIL);
subplan = grouping_planner(&subroot, 0.0 /* retrieve all tuples */ );
/*
- * If this child rel was excluded by constraint exclusion, exclude
- * it from the plan.
+ * If this child rel was excluded by constraint exclusion, exclude it
+ * from the plan.
*/
if (is_dummy_plan(subplan))
continue;
subplans = lappend(subplans, subplan);
+ /* Make sure any initplans from this rel get into the outer list */
+ root->init_plans = list_concat(root->init_plans, subroot.init_plans);
+
/* Build target-relations list for the executor */
resultRelations = lappend_int(resultRelations, appinfo->child_relid);
/* Build list of per-relation RETURNING targetlists */
if (parse->returningList)
{
- Assert(list_length(subroot.parse->returningLists) == 1);
+ Assert(list_length(subroot.returningLists) == 1);
returningLists = list_concat(returningLists,
- subroot.parse->returningLists);
+ subroot.returningLists);
}
}
- parse->resultRelations = resultRelations;
- parse->returningLists = returningLists;
+ root->resultRelations = resultRelations;
+ root->returningLists = returningLists;
/* Mark result as unordered (probably unnecessary) */
root->query_pathkeys = NIL;
* If we managed to exclude every child rel, return a dummy plan
*/
if (subplans == NIL)
- return (Plan *) make_result(tlist,
+ return (Plan *) make_result(root,
+ tlist,
(Node *) list_make1(makeBoolConst(false,
false)),
NULL);
*/
parse->rtable = rtable;
+ /* Suppress Append if there's only one surviving child rel */
+ if (list_length(subplans) == 1)
+ return (Plan *) linitial(subplans);
+
return (Plan *) make_append(subplans, true, tlist);
}
* operation's result. We have to do this before overwriting the sort
* key information...
*/
- current_pathkeys = make_pathkeys_for_sortclauses(set_sortclauses,
- result_plan->targetlist);
- current_pathkeys = canonicalize_pathkeys(root, current_pathkeys);
+ current_pathkeys = make_pathkeys_for_sortclauses(root,
+ set_sortclauses,
+ result_plan->targetlist,
+ true);
/*
* We should not need to call preprocess_targetlist, since we must be
/*
* Calculate pathkeys that represent result ordering requirements
*/
- sort_pathkeys = make_pathkeys_for_sortclauses(parse->sortClause,
- tlist);
- sort_pathkeys = canonicalize_pathkeys(root, sort_pathkeys);
+ sort_pathkeys = make_pathkeys_for_sortclauses(root,
+ parse->sortClause,
+ tlist,
+ true);
}
else
{
List *sub_tlist;
List *group_pathkeys;
AttrNumber *groupColIdx = NULL;
+ Oid *groupOperators = NULL;
bool need_tlist_eval = true;
QualCost tlist_cost;
Path *cheapest_path;
/*
* Calculate pathkeys that represent grouping/ordering requirements.
* Stash them in PlannerInfo so that query_planner can canonicalize
- * them.
+ * them after EquivalenceClasses have been formed.
*/
root->group_pathkeys =
- make_pathkeys_for_sortclauses(parse->groupClause, tlist);
+ make_pathkeys_for_sortclauses(root,
+ parse->groupClause,
+ tlist,
+ false);
root->sort_pathkeys =
- make_pathkeys_for_sortclauses(parse->sortClause, tlist);
+ make_pathkeys_for_sortclauses(root,
+ parse->sortClause,
+ tlist,
+ false);
/*
* Will need actual number of aggregates for estimating costs.
sort_pathkeys = root->sort_pathkeys;
/*
- * If grouping, decide whether we want to use hashed grouping.
+ * If grouping, extract the grouping operators and decide whether we
+ * want to use hashed grouping.
*/
if (parse->groupClause)
{
+ groupOperators = extract_grouping_ops(parse->groupClause);
use_hashed_grouping =
choose_hashed_grouping(root, tuple_fraction,
cheapest_path, sorted_path,
- dNumGroups, &agg_counts);
+ groupOperators, dNumGroups,
+ &agg_counts);
/* Also convert # groups to long int --- but 'ware overflow! */
numGroups = (long) Min(dNumGroups, (double) LONG_MAX);
*/
if (!is_projection_capable_plan(result_plan))
{
- result_plan = (Plan *) make_result(sub_tlist, NULL,
+ result_plan = (Plan *) make_result(root,
+ sub_tlist,
+ NULL,
result_plan);
}
else
* tuples) --- so make_agg() and make_group() are responsible
* for computing the added cost.
*/
- cost_qual_eval(&tlist_cost, sub_tlist);
+ cost_qual_eval(&tlist_cost, sub_tlist, root);
result_plan->startup_cost += tlist_cost.startup;
result_plan->total_cost += tlist_cost.startup +
tlist_cost.per_tuple * result_plan->plan_rows;
AGG_HASHED,
numGroupCols,
groupColIdx,
+ groupOperators,
numGroups,
agg_counts.numAggs,
result_plan);
aggstrategy,
numGroupCols,
groupColIdx,
+ groupOperators,
numGroups,
agg_counts.numAggs,
result_plan);
(List *) parse->havingQual,
numGroupCols,
groupColIdx,
+ groupOperators,
dNumGroups,
result_plan);
/* The Group node won't change sort ordering */
* this routine to avoid having to generate the plan in the
* first place.
*/
- result_plan = (Plan *) make_result(tlist,
+ result_plan = (Plan *) make_result(root,
+ tlist,
parse->havingQual,
NULL);
}
{
if (!pathkeys_contained_in(sort_pathkeys, current_pathkeys))
{
- result_plan = (Plan *)
- make_sort_from_sortclauses(root,
- parse->sortClause,
- result_plan);
+ result_plan = (Plan *) make_sort_from_pathkeys(root,
+ result_plan,
+ sort_pathkeys);
current_pathkeys = sort_pathkeys;
}
}
/*
* Deal with the RETURNING clause if any. It's convenient to pass the
- * returningList through setrefs.c now rather than at top level (if
- * we waited, handling inherited UPDATE/DELETE would be much harder).
+ * returningList through setrefs.c now rather than at top level (if we
+ * waited, handling inherited UPDATE/DELETE would be much harder).
*/
if (parse->returningList)
{
- List *rlist;
+ List *rlist;
+ Assert(parse->resultRelation);
rlist = set_returning_clause_references(parse->returningList,
result_plan,
parse->resultRelation);
- parse->returningLists = list_make1(rlist);
+ root->returningLists = list_make1(rlist);
}
+ else
+ root->returningLists = NIL;
+
+ /* Compute result-relations list if needed */
+ if (parse->resultRelation)
+ root->resultRelations = list_make1_int(parse->resultRelation);
+ else
+ root->resultRelations = NIL;
/*
* Return the actual output ordering in query_pathkeys for possible use by
{
if (IsA(plan, Result))
{
- List *rcqual = (List *) ((Result *) plan)->resconstantqual;
+ List *rcqual = (List *) ((Result *) plan)->resconstantqual;
if (list_length(rcqual) == 1)
{
- Const *constqual = (Const *) linitial(rcqual);
+ Const *constqual = (Const *) linitial(rcqual);
if (constqual && IsA(constqual, Const))
{
*/
if (parse->limitCount)
{
- est = estimate_expression_value(parse->limitCount);
+ est = estimate_expression_value(root, parse->limitCount);
if (est && IsA(est, Const))
{
if (((Const *) est)->constisnull)
if (parse->limitOffset)
{
- est = estimate_expression_value(parse->limitOffset);
+ est = estimate_expression_value(root, parse->limitOffset);
if (est && IsA(est, Const))
{
if (((Const *) est)->constisnull)
return tuple_fraction;
}
+/*
+ * extract_grouping_ops - make an array of the equality operator OIDs
+ * for the GROUP BY clause
+ */
+static Oid *
+extract_grouping_ops(List *groupClause)
+{
+ int numCols = list_length(groupClause);
+ int colno = 0;
+ Oid *groupOperators;
+ ListCell *glitem;
+
+ groupOperators = (Oid *) palloc(sizeof(Oid) * numCols);
+
+ foreach(glitem, groupClause)
+ {
+ GroupClause *groupcl = (GroupClause *) lfirst(glitem);
+
+ groupOperators[colno] = get_equality_op_for_ordering_op(groupcl->sortop);
+ if (!OidIsValid(groupOperators[colno])) /* shouldn't happen */
+ elog(ERROR, "could not find equality operator for ordering operator %u",
+ groupcl->sortop);
+ colno++;
+ }
+
+ return groupOperators;
+}
+
/*
* choose_hashed_grouping - should we use hashed grouping?
*/
static bool
choose_hashed_grouping(PlannerInfo *root, double tuple_fraction,
Path *cheapest_path, Path *sorted_path,
- double dNumGroups, AggClauseCounts *agg_counts)
+ Oid *groupOperators, double dNumGroups,
+ AggClauseCounts *agg_counts)
{
int numGroupCols = list_length(root->parse->groupClause);
double cheapest_path_rows;
List *current_pathkeys;
Path hashed_p;
Path sorted_p;
+ int i;
/*
* Check can't-do-it conditions, including whether the grouping operators
- * are hashjoinable.
+ * are hashjoinable. (We assume hashing is OK if they are marked
+ * oprcanhash. If there isn't actually a supporting hash function,
+ * the executor will complain at runtime.)
*
* Executor doesn't support hashed aggregation with DISTINCT aggregates.
* (Doing so would imply storing *all* the input values in the hash table,
return false;
if (agg_counts->numDistinctAggs != 0)
return false;
- if (!hash_safe_grouping(root))
- return false;
+ for (i = 0; i < numGroupCols; i++)
+ {
+ if (!op_hashjoinable(groupOperators[i]))
+ return false;
+ }
/*
* Don't do it if it doesn't look like the hashtable will fit into
return false;
}
-/*
- * hash_safe_grouping - are grouping operators hashable?
- *
- * We assume hashed aggregation will work if the datatype's equality operator
- * is marked hashjoinable.
- */
-static bool
-hash_safe_grouping(PlannerInfo *root)
-{
- ListCell *gl;
-
- foreach(gl, root->parse->groupClause)
- {
- GroupClause *grpcl = (GroupClause *) lfirst(gl);
- TargetEntry *tle = get_sortgroupclause_tle(grpcl,
- root->parse->targetList);
- Operator optup;
- bool oprcanhash;
-
- optup = equality_oper(exprType((Node *) tle->expr), true);
- if (!optup)
- return false;
- oprcanhash = ((Form_pg_operator) GETSTRUCT(optup))->oprcanhash;
- ReleaseSysCache(optup);
- if (!oprcanhash)
- return false;
- }
- return true;
-}
-
/*---------------
* make_subplanTargetList
* Generate appropriate target list when grouping is required.
* pass down only c,d,a+b, but it's not really worth the trouble to
* eliminate simple var references from the subplan. We will avoid doing
* the extra computation to recompute a+b at the outer level; see
- * replace_vars_with_subplan_refs() in setrefs.c.)
+ * fix_upper_expr() in setrefs.c.)
*
* If we are grouping or aggregating, *and* there are no non-Var grouping
* expressions, then the returned tlist is effectively dummy; we do not