* planner.c
* The query optimizer external interface.
*
- * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1996-2008, 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.210 2007/01/05 22:19:32 momjian Exp $
+ * $PostgreSQL: pgsql/src/backend/optimizer/plan/planner.c,v 1.236 2008/08/02 21:32:00 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 */
+/* GUC parameter */
+double cursor_tuple_fraction = DEFAULT_CURSOR_TUPLE_FRACTION;
+
+/* Hook for plugins to get control in planner() */
+planner_hook_type planner_hook = NULL;
/* Expression kind codes for preprocess_expression */
static double preprocess_limit(PlannerInfo *root,
double tuple_fraction,
int64 *offset_est, int64 *count_est);
-static bool choose_hashed_grouping(PlannerInfo *root, double tuple_fraction,
+static void preprocess_groupclause(PlannerInfo *root);
+static Oid *extract_grouping_ops(List *groupClause);
+static bool choose_hashed_grouping(PlannerInfo *root,
+ double tuple_fraction, double limit_tuples,
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
*
+ * To support loadable plugins that monitor or modify planner behavior,
+ * we provide a hook variable that lets a plugin get control before and
+ * after the standard planning process. The plugin would normally call
+ * standard_planner().
+ *
+ * Note to plugin authors: standard_planner() scribbles on its Query input,
+ * so you'd better copy that data structure if you want to plan more than once.
+ *
*****************************************************************************/
-Plan *
-planner(Query *parse, bool isCursor, int cursorOptions,
- ParamListInfo boundParams)
+PlannedStmt *
+planner(Query *parse, int cursorOptions, ParamListInfo boundParams)
{
+ PlannedStmt *result;
+
+ if (planner_hook)
+ result = (*planner_hook) (parse, cursorOptions, boundParams);
+ else
+ result = standard_planner(parse, cursorOptions, boundParams);
+ return result;
+}
+
+PlannedStmt *
+standard_planner(Query *parse, 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;
+
+ /* Cursor options may come from caller or from DECLARE CURSOR stmt */
+ if (parse->utilityStmt &&
+ IsA(parse->utilityStmt, DeclareCursorStmt))
+ cursorOptions |= ((DeclareCursorStmt *) parse->utilityStmt)->options;
/*
- * 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->rewindPlanIDs = NULL;
+ glob->finalrtable = NIL;
+ glob->relationOids = NIL;
+ glob->transientPlan = false;
/* Determine what fraction of the plan is likely to be scanned */
- if (isCursor)
+ if (cursorOptions & CURSOR_OPT_FAST_PLAN)
{
/*
* We have no real idea how many tuples the user will ultimately FETCH
- * from a cursor, but it seems a good bet that he doesn't want 'em
- * all. Optimize for 10% retrieval (you gotta better number? Should
- * this be a SETtable parameter?)
+ * from a cursor, but it is often the case that he doesn't want 'em
+ * all, or would prefer a fast-start plan anyway so that he can
+ * process some of the tuples sooner. Use a GUC parameter to decide
+ * what fraction to optimize for.
+ */
+ tuple_fraction = cursor_tuple_fraction;
+
+ /*
+ * We document cursor_tuple_fraction as simply being a fraction,
+ * which means the edge cases 0 and 1 have to be treated specially
+ * here. We convert 1 to 0 ("all the tuples") and 0 to a very small
+ * fraction.
*/
- tuple_fraction = 0.10;
+ if (tuple_fraction >= 1.0)
+ tuple_fraction = 0.0;
+ else if (tuple_fraction <= 0.0)
+ tuple_fraction = 1e-10;
}
else
{
}
/* 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
* backwards on demand. Add a Material node at the top at need.
*/
- if (isCursor && (cursorOptions & CURSOR_OPT_SCROLL))
+ if (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->transientPlan = glob->transientPlan;
+ result->planTree = top_plan;
+ result->rtable = glob->finalrtable;
+ result->resultRelations = root->resultRelations;
+ result->utilityStmt = parse->utilityStmt;
+ result->intoClause = parse->intoClause;
+ result->subplans = glob->subplans;
+ result->rewindPlanIDs = glob->rewindPlanIDs;
+ result->returningLists = root->returningLists;
+ result->rowMarks = parse->rowMarks;
+ result->relationOids = glob->relationOids;
+ 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;
/*
* Look for IN clauses at the top level of WHERE, and transform them into
* joins. Note that this step only handles IN clauses originally at top
- * level of WHERE; if we pull up any subqueries in the next step, their
- * INs are processed just before pulling them up.
+ * level of WHERE; if we pull up any subqueries below, their INs are
+ * processed just before pulling them up.
*/
if (parse->hasSubLinks)
parse->jointree->quals = pull_up_IN_clauses(root,
parse->jointree->quals);
+ /*
+ * Scan the rangetable for set-returning functions, and inline them
+ * if possible (producing subqueries that might get pulled up next).
+ * Recursion issues here are handled in the same way as for IN clauses.
+ */
+ inline_set_returning_functions(root);
+
/*
* Check to see if any subqueries in the rangetable can be merged into
* this query.
* 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);
-
- /* Return sort ordering info if caller wants it */
- if (subquery_pathkeys)
- *subquery_pathkeys = root->query_pathkeys;
+ if (list_length(glob->subplans) != num_old_subplans ||
+ root->query_level > 1)
+ SS_finalize_plan(root, plan, true);
- /* 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 (kind != EXPRKIND_VALUES &&
(root->parse->jointree->fromlist != NIL ||
kind == EXPRKIND_QUAL ||
- PlannerQueryLevel > 1))
- expr = eval_const_expressions(expr);
+ root->query_level > 1))
+ expr = eval_const_expressions(root, expr);
/*
* If it's a qual or havingQual, canonicalize it.
/* 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);
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,
+ {
+ root->resultRelations = list_make1_int(parentRTindex);
+ /* although dummy, it must have a valid tlist for executor */
+ tlist = preprocess_targetlist(root, parse->targetList);
+ return (Plan *) make_result(root,
+ tlist,
(Node *) list_make1(makeBoolConst(false,
false)),
NULL);
+ }
/*
* Planning might have modified the rangetable, due to changes of the
*/
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);
}
List *tlist = parse->targetList;
int64 offset_est = 0;
int64 count_est = 0;
+ double limit_tuples = -1.0;
Plan *result_plan;
List *current_pathkeys;
List *sort_pathkeys;
/* Tweak caller-supplied tuple_fraction if have LIMIT/OFFSET */
if (parse->limitCount || parse->limitOffset)
+ {
tuple_fraction = preprocess_limit(root, tuple_fraction,
&offset_est, &count_est);
+ /*
+ * If we have a known LIMIT, and don't have an unknown OFFSET, we can
+ * estimate the effects of using a bounded sort.
+ */
+ if (count_est > 0 && offset_est >= 0)
+ limit_tuples = (double) count_est + (double) offset_est;
+ }
+
if (parse->setOperations)
{
List *set_sortclauses;
* 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);
+ Assert(parse->distinctClause == NIL);
+ 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;
Path *best_path;
long numGroups = 0;
AggClauseCounts agg_counts;
- int numGroupCols = list_length(parse->groupClause);
+ int numGroupCols;
bool use_hashed_grouping = false;
MemSet(&agg_counts, 0, sizeof(AggClauseCounts));
+ /* Preprocess GROUP BY clause, if any */
+ if (parse->groupClause)
+ preprocess_groupclause(root);
+ numGroupCols = list_length(parse->groupClause);
+
/* Preprocess targetlist */
tlist = preprocess_targetlist(root, tlist);
/*
* Calculate pathkeys that represent grouping/ordering requirements.
* Stash them in PlannerInfo so that query_planner can canonicalize
- * them.
+ * them after EquivalenceClasses have been formed.
+ *
+ * Note: for the moment, DISTINCT is always implemented via sort/uniq,
+ * and we set the sort_pathkeys to be the more rigorous of the
+ * DISTINCT and ORDER BY requirements. This should be changed
+ * someday, but DISTINCT ON is a bit of a problem ...
*/
root->group_pathkeys =
- make_pathkeys_for_sortclauses(parse->groupClause, tlist);
- root->sort_pathkeys =
- make_pathkeys_for_sortclauses(parse->sortClause, tlist);
+ make_pathkeys_for_sortclauses(root,
+ parse->groupClause,
+ tlist,
+ false);
+ if (list_length(parse->distinctClause) > list_length(parse->sortClause))
+ root->sort_pathkeys =
+ make_pathkeys_for_sortclauses(root,
+ parse->distinctClause,
+ tlist,
+ false);
+ else
+ root->sort_pathkeys =
+ make_pathkeys_for_sortclauses(root,
+ parse->sortClause,
+ tlist,
+ false);
/*
* Will need actual number of aggregates for estimating costs.
* by ORDER BY --- but that might just leave us failing to exploit an
* available sort order at all. Needs more thought...)
*/
- if (parse->groupClause)
+ if (root->group_pathkeys)
root->query_pathkeys = root->group_pathkeys;
- else if (parse->sortClause)
+ else if (root->sort_pathkeys)
root->query_pathkeys = root->sort_pathkeys;
else
root->query_pathkeys = NIL;
* estimate the number of groups in the query, and canonicalize all
* the pathkeys.
*/
- query_planner(root, sub_tlist, tuple_fraction,
+ query_planner(root, sub_tlist, tuple_fraction, limit_tuples,
&cheapest_path, &sorted_path, &dNumGroups);
group_pathkeys = root->group_pathkeys;
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,
+ choose_hashed_grouping(root, tuple_fraction, limit_tuples,
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);
* Normal case --- create a plan according to query_planner's
* results.
*/
+ bool need_sort_for_grouping = false;
+
result_plan = create_plan(root, best_path);
current_pathkeys = best_path->pathkeys;
+ /* Detect if we'll need an explicit sort for grouping */
+ if (parse->groupClause && !use_hashed_grouping &&
+ !pathkeys_contained_in(group_pathkeys, current_pathkeys))
+ {
+ need_sort_for_grouping = true;
+ /*
+ * Always override query_planner's tlist, so that we don't
+ * sort useless data from a "physical" tlist.
+ */
+ need_tlist_eval = true;
+ }
+
/*
* create_plan() returns a plan with just a "flat" tlist of
* required Vars. Usually we need to insert the sub_tlist as the
*/
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);
if (parse->groupClause)
{
- if (!pathkeys_contained_in(group_pathkeys,
- current_pathkeys))
+ if (need_sort_for_grouping)
{
result_plan = (Plan *)
make_sort_from_groupcols(root,
aggstrategy,
numGroupCols,
groupColIdx,
+ groupOperators,
numGroups,
agg_counts.numAggs,
result_plan);
* Add an explicit sort if we couldn't make the path come out
* the way the GROUP node needs it.
*/
- if (!pathkeys_contained_in(group_pathkeys, current_pathkeys))
+ if (need_sort_for_grouping)
{
result_plan = (Plan *)
make_sort_from_groupcols(root,
(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 we were not able to make the plan come out in the right order, add
* an explicit sort step.
*/
- if (parse->sortClause)
+ if (sort_pathkeys)
{
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,
+ limit_tuples);
current_pathkeys = sort_pathkeys;
}
}
{
List *rlist;
- rlist = set_returning_clause_references(parse->returningList,
+ Assert(parse->resultRelation);
+ rlist = set_returning_clause_references(root->glob,
+ 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 (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;
}
+
+/*
+ * preprocess_groupclause - do preparatory work on GROUP BY clause
+ *
+ * The idea here is to adjust the ordering of the GROUP BY elements
+ * (which in itself is semantically insignificant) to match ORDER BY,
+ * thereby allowing a single sort operation to both implement the ORDER BY
+ * requirement and set up for a Unique step that implements GROUP BY.
+ *
+ * In principle it might be interesting to consider other orderings of the
+ * GROUP BY elements, which could match the sort ordering of other
+ * possible plans (eg an indexscan) and thereby reduce cost. We don't
+ * bother with that, though. Hashed grouping will frequently win anyway.
+ */
+static void
+preprocess_groupclause(PlannerInfo *root)
+{
+ Query *parse = root->parse;
+ List *new_groupclause;
+ bool partial_match;
+ ListCell *sl;
+ ListCell *gl;
+
+ /* If no ORDER BY, nothing useful to do here anyway */
+ if (parse->sortClause == NIL)
+ return;
+
+ /*
+ * Scan the ORDER BY clause and construct a list of matching GROUP BY
+ * items, but only as far as we can make a matching prefix.
+ *
+ * This code assumes that the sortClause contains no duplicate items.
+ */
+ new_groupclause = NIL;
+ foreach(sl, parse->sortClause)
+ {
+ SortGroupClause *sc = (SortGroupClause *) lfirst(sl);
+
+ foreach(gl, parse->groupClause)
+ {
+ SortGroupClause *gc = (SortGroupClause *) lfirst(gl);
+
+ if (equal(gc, sc))
+ {
+ new_groupclause = lappend(new_groupclause, gc);
+ break;
+ }
+ }
+ if (gl == NULL)
+ break; /* no match, so stop scanning */
+ }
+
+ /* Did we match all of the ORDER BY list, or just some of it? */
+ partial_match = (sl != NULL);
+
+ /* If no match at all, no point in reordering GROUP BY */
+ if (new_groupclause == NIL)
+ return;
+
+ /*
+ * Add any remaining GROUP BY items to the new list, but only if we
+ * were able to make a complete match. In other words, we only
+ * rearrange the GROUP BY list if the result is that one list is a
+ * prefix of the other --- otherwise there's no possibility of a
+ * common sort.
+ */
+ foreach(gl, parse->groupClause)
+ {
+ SortGroupClause *gc = (SortGroupClause *) lfirst(gl);
+
+ if (list_member_ptr(new_groupclause, gc))
+ continue; /* it matched an ORDER BY item */
+ if (partial_match)
+ return; /* give up, no common sort possible */
+ new_groupclause = lappend(new_groupclause, gc);
+ }
+
+ /* Success --- install the rearranged GROUP BY list */
+ Assert(list_length(parse->groupClause) == list_length(new_groupclause));
+ parse->groupClause = new_groupclause;
+}
+
+/*
+ * 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)
+ {
+ SortGroupClause *groupcl = (SortGroupClause *) lfirst(glitem);
+
+ groupOperators[colno] = groupcl->eqop;
+ Assert(OidIsValid(groupOperators[colno]));
+ colno++;
+ }
+
+ return groupOperators;
+}
+
/*
* choose_hashed_grouping - should we use hashed grouping?
*/
static bool
-choose_hashed_grouping(PlannerInfo *root, double tuple_fraction,
+choose_hashed_grouping(PlannerInfo *root,
+ double tuple_fraction, double limit_tuples,
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
/* Result of hashed agg is always unsorted */
if (root->sort_pathkeys)
cost_sort(&hashed_p, root, root->sort_pathkeys, hashed_p.total_cost,
- dNumGroups, cheapest_path_width);
+ dNumGroups, cheapest_path_width, limit_tuples);
if (sorted_path)
{
if (!pathkeys_contained_in(root->group_pathkeys, current_pathkeys))
{
cost_sort(&sorted_p, root, root->group_pathkeys, sorted_p.total_cost,
- cheapest_path_rows, cheapest_path_width);
+ cheapest_path_rows, cheapest_path_width, -1.0);
current_pathkeys = root->group_pathkeys;
}
if (root->sort_pathkeys &&
!pathkeys_contained_in(root->sort_pathkeys, current_pathkeys))
cost_sort(&sorted_p, root, root->sort_pathkeys, sorted_p.total_cost,
- dNumGroups, cheapest_path_width);
+ dNumGroups, cheapest_path_width, limit_tuples);
/*
* Now make the decision using the top-level tuple fraction. First we
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
foreach(gl, parse->groupClause)
{
- GroupClause *grpcl = (GroupClause *) lfirst(gl);
+ SortGroupClause *grpcl = (SortGroupClause *) lfirst(gl);
Node *groupexpr = get_sortgroupclause_expr(grpcl, tlist);
TargetEntry *te = NULL;
ListCell *sl;
foreach(gl, root->parse->groupClause)
{
- GroupClause *grpcl = (GroupClause *) lfirst(gl);
+ SortGroupClause *grpcl = (SortGroupClause *) lfirst(gl);
Node *groupexpr = get_sortgroupclause_expr(grpcl, tlist);
TargetEntry *te = NULL;
ListCell *sl;