1 /*-------------------------------------------------------------------------
4 * The query optimizer external interface.
6 * Portions Copyright (c) 1996-2012, PostgreSQL Global Development Group
7 * Portions Copyright (c) 1994, Regents of the University of California
11 * src/backend/optimizer/plan/planner.c
13 *-------------------------------------------------------------------------
20 #include "access/htup_details.h"
21 #include "executor/executor.h"
22 #include "executor/nodeAgg.h"
23 #include "miscadmin.h"
24 #include "nodes/makefuncs.h"
25 #ifdef OPTIMIZER_DEBUG
26 #include "nodes/print.h"
28 #include "optimizer/clauses.h"
29 #include "optimizer/cost.h"
30 #include "optimizer/pathnode.h"
31 #include "optimizer/paths.h"
32 #include "optimizer/plancat.h"
33 #include "optimizer/planmain.h"
34 #include "optimizer/planner.h"
35 #include "optimizer/prep.h"
36 #include "optimizer/subselect.h"
37 #include "optimizer/tlist.h"
38 #include "parser/analyze.h"
39 #include "parser/parsetree.h"
40 #include "rewrite/rewriteManip.h"
41 #include "utils/rel.h"
45 double cursor_tuple_fraction = DEFAULT_CURSOR_TUPLE_FRACTION;
47 /* Hook for plugins to get control in planner() */
48 planner_hook_type planner_hook = NULL;
51 /* Expression kind codes for preprocess_expression */
52 #define EXPRKIND_QUAL 0
53 #define EXPRKIND_TARGET 1
54 #define EXPRKIND_RTFUNC 2
55 #define EXPRKIND_RTFUNC_LATERAL 3
56 #define EXPRKIND_VALUES 4
57 #define EXPRKIND_VALUES_LATERAL 5
58 #define EXPRKIND_LIMIT 6
59 #define EXPRKIND_APPINFO 7
60 #define EXPRKIND_PHV 8
63 static Node *preprocess_expression(PlannerInfo *root, Node *expr, int kind);
64 static void preprocess_qual_conditions(PlannerInfo *root, Node *jtnode);
65 static Plan *inheritance_planner(PlannerInfo *root);
66 static Plan *grouping_planner(PlannerInfo *root, double tuple_fraction);
67 static void preprocess_rowmarks(PlannerInfo *root);
68 static double preprocess_limit(PlannerInfo *root,
69 double tuple_fraction,
70 int64 *offset_est, int64 *count_est);
71 static void preprocess_groupclause(PlannerInfo *root);
72 static bool choose_hashed_grouping(PlannerInfo *root,
73 double tuple_fraction, double limit_tuples,
74 double path_rows, int path_width,
75 Path *cheapest_path, Path *sorted_path,
76 double dNumGroups, AggClauseCosts *agg_costs);
77 static bool choose_hashed_distinct(PlannerInfo *root,
78 double tuple_fraction, double limit_tuples,
79 double path_rows, int path_width,
80 Cost cheapest_startup_cost, Cost cheapest_total_cost,
81 Cost sorted_startup_cost, Cost sorted_total_cost,
82 List *sorted_pathkeys,
83 double dNumDistinctRows);
84 static List *make_subplanTargetList(PlannerInfo *root, List *tlist,
85 AttrNumber **groupColIdx, bool *need_tlist_eval);
86 static int get_grouping_column_index(Query *parse, TargetEntry *tle);
87 static void locate_grouping_columns(PlannerInfo *root,
90 AttrNumber *groupColIdx);
91 static List *postprocess_setop_tlist(List *new_tlist, List *orig_tlist);
92 static List *select_active_windows(PlannerInfo *root, WindowFuncLists *wflists);
93 static List *add_volatile_sort_exprs(List *window_tlist, List *tlist,
95 static List *make_pathkeys_for_window(PlannerInfo *root, WindowClause *wc,
96 List *tlist, bool canonicalize);
97 static void get_column_info_for_window(PlannerInfo *root, WindowClause *wc,
99 int numSortCols, AttrNumber *sortColIdx,
101 AttrNumber **partColIdx,
104 AttrNumber **ordColIdx,
108 /*****************************************************************************
110 * Query optimizer entry point
112 * To support loadable plugins that monitor or modify planner behavior,
113 * we provide a hook variable that lets a plugin get control before and
114 * after the standard planning process. The plugin would normally call
115 * standard_planner().
117 * Note to plugin authors: standard_planner() scribbles on its Query input,
118 * so you'd better copy that data structure if you want to plan more than once.
120 *****************************************************************************/
122 planner(Query *parse, int cursorOptions, ParamListInfo boundParams)
127 result = (*planner_hook) (parse, cursorOptions, boundParams);
129 result = standard_planner(parse, cursorOptions, boundParams);
134 standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams)
138 double tuple_fraction;
144 /* Cursor options may come from caller or from DECLARE CURSOR stmt */
145 if (parse->utilityStmt &&
146 IsA(parse->utilityStmt, DeclareCursorStmt))
147 cursorOptions |= ((DeclareCursorStmt *) parse->utilityStmt)->options;
150 * Set up global state for this planner invocation. This data is needed
151 * across all levels of sub-Query that might exist in the given command,
152 * so we keep it in a separate struct that's linked to by each per-Query
155 glob = makeNode(PlannerGlobal);
157 glob->boundParams = boundParams;
158 glob->subplans = NIL;
159 glob->subroots = NIL;
160 glob->rewindPlanIDs = NULL;
161 glob->finalrtable = NIL;
162 glob->finalrowmarks = NIL;
163 glob->resultRelations = NIL;
164 glob->relationOids = NIL;
165 glob->invalItems = NIL;
166 glob->nParamExec = 0;
168 glob->lastRowMarkId = 0;
169 glob->transientPlan = false;
171 /* Determine what fraction of the plan is likely to be scanned */
172 if (cursorOptions & CURSOR_OPT_FAST_PLAN)
175 * We have no real idea how many tuples the user will ultimately FETCH
176 * from a cursor, but it is often the case that he doesn't want 'em
177 * all, or would prefer a fast-start plan anyway so that he can
178 * process some of the tuples sooner. Use a GUC parameter to decide
179 * what fraction to optimize for.
181 tuple_fraction = cursor_tuple_fraction;
184 * We document cursor_tuple_fraction as simply being a fraction, which
185 * means the edge cases 0 and 1 have to be treated specially here. We
186 * convert 1 to 0 ("all the tuples") and 0 to a very small fraction.
188 if (tuple_fraction >= 1.0)
189 tuple_fraction = 0.0;
190 else if (tuple_fraction <= 0.0)
191 tuple_fraction = 1e-10;
195 /* Default assumption is we need all the tuples */
196 tuple_fraction = 0.0;
199 /* primary planning entry point (may recurse for subqueries) */
200 top_plan = subquery_planner(glob, parse, NULL,
201 false, tuple_fraction, &root);
204 * If creating a plan for a scrollable cursor, make sure it can run
205 * backwards on demand. Add a Material node at the top at need.
207 if (cursorOptions & CURSOR_OPT_SCROLL)
209 if (!ExecSupportsBackwardScan(top_plan))
210 top_plan = materialize_finished_plan(top_plan);
213 /* final cleanup of the plan */
214 Assert(glob->finalrtable == NIL);
215 Assert(glob->finalrowmarks == NIL);
216 Assert(glob->resultRelations == NIL);
217 top_plan = set_plan_references(root, top_plan);
218 /* ... and the subplans (both regular subplans and initplans) */
219 Assert(list_length(glob->subplans) == list_length(glob->subroots));
220 forboth(lp, glob->subplans, lr, glob->subroots)
222 Plan *subplan = (Plan *) lfirst(lp);
223 PlannerInfo *subroot = (PlannerInfo *) lfirst(lr);
225 lfirst(lp) = set_plan_references(subroot, subplan);
228 /* build the PlannedStmt result */
229 result = makeNode(PlannedStmt);
231 result->commandType = parse->commandType;
232 result->queryId = parse->queryId;
233 result->hasReturning = (parse->returningList != NIL);
234 result->hasModifyingCTE = parse->hasModifyingCTE;
235 result->canSetTag = parse->canSetTag;
236 result->transientPlan = glob->transientPlan;
237 result->planTree = top_plan;
238 result->rtable = glob->finalrtable;
239 result->resultRelations = glob->resultRelations;
240 result->utilityStmt = parse->utilityStmt;
241 result->subplans = glob->subplans;
242 result->rewindPlanIDs = glob->rewindPlanIDs;
243 result->rowMarks = glob->finalrowmarks;
244 result->relationOids = glob->relationOids;
245 result->invalItems = glob->invalItems;
246 result->nParamExec = glob->nParamExec;
252 /*--------------------
254 * Invokes the planner on a subquery. We recurse to here for each
255 * sub-SELECT found in the query tree.
257 * glob is the global state for the current planner run.
258 * parse is the querytree produced by the parser & rewriter.
259 * parent_root is the immediate parent Query's info (NULL at the top level).
260 * hasRecursion is true if this is a recursive WITH query.
261 * tuple_fraction is the fraction of tuples we expect will be retrieved.
262 * tuple_fraction is interpreted as explained for grouping_planner, below.
264 * If subroot isn't NULL, we pass back the query's final PlannerInfo struct;
265 * among other things this tells the output sort ordering of the plan.
267 * Basically, this routine does the stuff that should only be done once
268 * per Query object. It then calls grouping_planner. At one time,
269 * grouping_planner could be invoked recursively on the same Query object;
270 * that's not currently true, but we keep the separation between the two
271 * routines anyway, in case we need it again someday.
273 * subquery_planner will be called recursively to handle sub-Query nodes
274 * found within the query's expressions and rangetable.
276 * Returns a query plan.
277 *--------------------
280 subquery_planner(PlannerGlobal *glob, Query *parse,
281 PlannerInfo *parent_root,
282 bool hasRecursion, double tuple_fraction,
283 PlannerInfo **subroot)
285 int num_old_subplans = list_length(glob->subplans);
292 /* Create a PlannerInfo data structure for this subquery */
293 root = makeNode(PlannerInfo);
296 root->query_level = parent_root ? parent_root->query_level + 1 : 1;
297 root->parent_root = parent_root;
298 root->plan_params = NIL;
299 root->planner_cxt = CurrentMemoryContext;
300 root->init_plans = NIL;
301 root->cte_plan_ids = NIL;
302 root->eq_classes = NIL;
303 root->append_rel_list = NIL;
304 root->rowMarks = NIL;
305 root->hasInheritedTarget = false;
307 root->hasRecursion = hasRecursion;
309 root->wt_param_id = SS_assign_special_param(root);
311 root->wt_param_id = -1;
312 root->non_recursive_plan = NULL;
315 * If there is a WITH list, process each WITH query and build an initplan
316 * SubPlan structure for it.
319 SS_process_ctes(root);
322 * Look for ANY and EXISTS SubLinks in WHERE and JOIN/ON clauses, and try
323 * to transform them into joins. Note that this step does not descend
324 * into subqueries; if we pull up any subqueries below, their SubLinks are
325 * processed just before pulling them up.
327 if (parse->hasSubLinks)
328 pull_up_sublinks(root);
331 * Scan the rangetable for set-returning functions, and inline them if
332 * possible (producing subqueries that might get pulled up next).
333 * Recursion issues here are handled in the same way as for SubLinks.
335 inline_set_returning_functions(root);
338 * Check to see if any subqueries in the jointree can be merged into this
341 parse->jointree = (FromExpr *)
342 pull_up_subqueries(root, (Node *) parse->jointree);
345 * If this is a simple UNION ALL query, flatten it into an appendrel. We
346 * do this now because it requires applying pull_up_subqueries to the leaf
347 * queries of the UNION ALL, which weren't touched above because they
348 * weren't referenced by the jointree (they will be after we do this).
350 if (parse->setOperations)
351 flatten_simple_union_all(root);
354 * Detect whether any rangetable entries are RTE_JOIN kind; if not, we can
355 * avoid the expense of doing flatten_join_alias_vars(). Also check for
356 * outer joins --- if none, we can skip reduce_outer_joins(). And check
357 * for LATERAL RTEs, too. This must be done after we have done
358 * pull_up_subqueries(), of course.
360 root->hasJoinRTEs = false;
361 root->hasLateralRTEs = false;
362 hasOuterJoins = false;
363 foreach(l, parse->rtable)
365 RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
367 if (rte->rtekind == RTE_JOIN)
369 root->hasJoinRTEs = true;
370 if (IS_OUTER_JOIN(rte->jointype))
371 hasOuterJoins = true;
374 root->hasLateralRTEs = true;
378 * Preprocess RowMark information. We need to do this after subquery
379 * pullup (so that all non-inherited RTEs are present) and before
380 * inheritance expansion (so that the info is available for
381 * expand_inherited_tables to examine and modify).
383 preprocess_rowmarks(root);
386 * Expand any rangetable entries that are inheritance sets into "append
387 * relations". This can add entries to the rangetable, but they must be
388 * plain base relations not joins, so it's OK (and marginally more
389 * efficient) to do it after checking for join RTEs. We must do it after
390 * pulling up subqueries, else we'd fail to handle inherited tables in
393 expand_inherited_tables(root);
396 * Set hasHavingQual to remember if HAVING clause is present. Needed
397 * because preprocess_expression will reduce a constant-true condition to
398 * an empty qual list ... but "HAVING TRUE" is not a semantic no-op.
400 root->hasHavingQual = (parse->havingQual != NULL);
402 /* Clear this flag; might get set in distribute_qual_to_rels */
403 root->hasPseudoConstantQuals = false;
406 * Do expression preprocessing on targetlist and quals, as well as other
407 * random expressions in the querytree. Note that we do not need to
408 * handle sort/group expressions explicitly, because they are actually
409 * part of the targetlist.
411 parse->targetList = (List *)
412 preprocess_expression(root, (Node *) parse->targetList,
415 parse->returningList = (List *)
416 preprocess_expression(root, (Node *) parse->returningList,
419 preprocess_qual_conditions(root, (Node *) parse->jointree);
421 parse->havingQual = preprocess_expression(root, parse->havingQual,
424 foreach(l, parse->windowClause)
426 WindowClause *wc = (WindowClause *) lfirst(l);
428 /* partitionClause/orderClause are sort/group expressions */
429 wc->startOffset = preprocess_expression(root, wc->startOffset,
431 wc->endOffset = preprocess_expression(root, wc->endOffset,
435 parse->limitOffset = preprocess_expression(root, parse->limitOffset,
437 parse->limitCount = preprocess_expression(root, parse->limitCount,
440 root->append_rel_list = (List *)
441 preprocess_expression(root, (Node *) root->append_rel_list,
444 /* Also need to preprocess expressions within RTEs */
445 foreach(l, parse->rtable)
447 RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
450 if (rte->rtekind == RTE_SUBQUERY)
453 * We don't want to do all preprocessing yet on the subquery's
454 * expressions, since that will happen when we plan it. But if it
455 * contains any join aliases of our level, those have to get
456 * expanded now, because planning of the subquery won't do it.
457 * That's only possible if the subquery is LATERAL.
459 if (rte->lateral && root->hasJoinRTEs)
460 rte->subquery = (Query *)
461 flatten_join_alias_vars(root, (Node *) rte->subquery);
463 else if (rte->rtekind == RTE_FUNCTION)
465 /* Preprocess the function expression fully */
466 kind = rte->lateral ? EXPRKIND_RTFUNC_LATERAL : EXPRKIND_RTFUNC;
467 rte->funcexpr = preprocess_expression(root, rte->funcexpr, kind);
469 else if (rte->rtekind == RTE_VALUES)
471 /* Preprocess the values lists fully */
472 kind = rte->lateral ? EXPRKIND_VALUES_LATERAL : EXPRKIND_VALUES;
473 rte->values_lists = (List *)
474 preprocess_expression(root, (Node *) rte->values_lists, kind);
479 * In some cases we may want to transfer a HAVING clause into WHERE. We
480 * cannot do so if the HAVING clause contains aggregates (obviously) or
481 * volatile functions (since a HAVING clause is supposed to be executed
482 * only once per group). Also, it may be that the clause is so expensive
483 * to execute that we're better off doing it only once per group, despite
484 * the loss of selectivity. This is hard to estimate short of doing the
485 * entire planning process twice, so we use a heuristic: clauses
486 * containing subplans are left in HAVING. Otherwise, we move or copy the
487 * HAVING clause into WHERE, in hopes of eliminating tuples before
488 * aggregation instead of after.
490 * If the query has explicit grouping then we can simply move such a
491 * clause into WHERE; any group that fails the clause will not be in the
492 * output because none of its tuples will reach the grouping or
493 * aggregation stage. Otherwise we must have a degenerate (variable-free)
494 * HAVING clause, which we put in WHERE so that query_planner() can use it
495 * in a gating Result node, but also keep in HAVING to ensure that we
496 * don't emit a bogus aggregated row. (This could be done better, but it
497 * seems not worth optimizing.)
499 * Note that both havingQual and parse->jointree->quals are in
500 * implicitly-ANDed-list form at this point, even though they are declared
504 foreach(l, (List *) parse->havingQual)
506 Node *havingclause = (Node *) lfirst(l);
508 if (contain_agg_clause(havingclause) ||
509 contain_volatile_functions(havingclause) ||
510 contain_subplans(havingclause))
512 /* keep it in HAVING */
513 newHaving = lappend(newHaving, havingclause);
515 else if (parse->groupClause)
517 /* move it to WHERE */
518 parse->jointree->quals = (Node *)
519 lappend((List *) parse->jointree->quals, havingclause);
523 /* put a copy in WHERE, keep it in HAVING */
524 parse->jointree->quals = (Node *)
525 lappend((List *) parse->jointree->quals,
526 copyObject(havingclause));
527 newHaving = lappend(newHaving, havingclause);
530 parse->havingQual = (Node *) newHaving;
533 * If we have any outer joins, try to reduce them to plain inner joins.
534 * This step is most easily done after we've done expression
538 reduce_outer_joins(root);
541 * Do the main planning. If we have an inherited target relation, that
542 * needs special processing, else go straight to grouping_planner.
544 if (parse->resultRelation &&
545 rt_fetch(parse->resultRelation, parse->rtable)->inh)
546 plan = inheritance_planner(root);
549 plan = grouping_planner(root, tuple_fraction);
550 /* If it's not SELECT, we need a ModifyTable node */
551 if (parse->commandType != CMD_SELECT)
553 List *returningLists;
557 * Set up the RETURNING list-of-lists, if needed.
559 if (parse->returningList)
560 returningLists = list_make1(parse->returningList);
562 returningLists = NIL;
565 * If there was a FOR UPDATE/SHARE clause, the LockRows node will
566 * have dealt with fetching non-locked marked rows, else we need
567 * to have ModifyTable do that.
572 rowMarks = root->rowMarks;
574 plan = (Plan *) make_modifytable(parse->commandType,
576 list_make1_int(parse->resultRelation),
580 SS_assign_special_param(root));
585 * If any subplans were generated, or if there are any parameters to worry
586 * about, build initPlan list and extParam/allParam sets for plan nodes,
587 * and attach the initPlans to the top plan node.
589 if (list_length(glob->subplans) != num_old_subplans ||
590 root->glob->nParamExec > 0)
591 SS_finalize_plan(root, plan, true);
593 /* Return internal info if caller wants it */
601 * preprocess_expression
602 * Do subquery_planner's preprocessing work for an expression,
603 * which can be a targetlist, a WHERE clause (including JOIN/ON
604 * conditions), a HAVING clause, or a few other things.
607 preprocess_expression(PlannerInfo *root, Node *expr, int kind)
610 * Fall out quickly if expression is empty. This occurs often enough to
611 * be worth checking. Note that null->null is the correct conversion for
612 * implicit-AND result format, too.
618 * If the query has any join RTEs, replace join alias variables with
619 * base-relation variables. We must do this before sublink processing,
620 * else sublinks expanded out from join aliases would not get processed.
621 * We can skip it in non-lateral RTE functions and VALUES lists, however,
622 * since they can't contain any Vars of the current query level.
624 if (root->hasJoinRTEs &&
625 !(kind == EXPRKIND_RTFUNC || kind == EXPRKIND_VALUES))
626 expr = flatten_join_alias_vars(root, expr);
629 * Simplify constant expressions.
631 * Note: an essential effect of this is to convert named-argument function
632 * calls to positional notation and insert the current actual values of
633 * any default arguments for functions. To ensure that happens, we *must*
634 * process all expressions here. Previous PG versions sometimes skipped
635 * const-simplification if it didn't seem worth the trouble, but we can't
638 * Note: this also flattens nested AND and OR expressions into N-argument
639 * form. All processing of a qual expression after this point must be
640 * careful to maintain AND/OR flatness --- that is, do not generate a tree
641 * with AND directly under AND, nor OR directly under OR.
643 expr = eval_const_expressions(root, expr);
646 * If it's a qual or havingQual, canonicalize it.
648 if (kind == EXPRKIND_QUAL)
650 expr = (Node *) canonicalize_qual((Expr *) expr);
652 #ifdef OPTIMIZER_DEBUG
653 printf("After canonicalize_qual()\n");
658 /* Expand SubLinks to SubPlans */
659 if (root->parse->hasSubLinks)
660 expr = SS_process_sublinks(root, expr, (kind == EXPRKIND_QUAL));
663 * XXX do not insert anything here unless you have grokked the comments in
664 * SS_replace_correlation_vars ...
667 /* Replace uplevel vars with Param nodes (this IS possible in VALUES) */
668 if (root->query_level > 1)
669 expr = SS_replace_correlation_vars(root, expr);
672 * If it's a qual or havingQual, convert it to implicit-AND format. (We
673 * don't want to do this before eval_const_expressions, since the latter
674 * would be unable to simplify a top-level AND correctly. Also,
675 * SS_process_sublinks expects explicit-AND format.)
677 if (kind == EXPRKIND_QUAL)
678 expr = (Node *) make_ands_implicit((Expr *) expr);
684 * preprocess_qual_conditions
685 * Recursively scan the query's jointree and do subquery_planner's
686 * preprocessing work on each qual condition found therein.
689 preprocess_qual_conditions(PlannerInfo *root, Node *jtnode)
693 if (IsA(jtnode, RangeTblRef))
695 /* nothing to do here */
697 else if (IsA(jtnode, FromExpr))
699 FromExpr *f = (FromExpr *) jtnode;
702 foreach(l, f->fromlist)
703 preprocess_qual_conditions(root, lfirst(l));
705 f->quals = preprocess_expression(root, f->quals, EXPRKIND_QUAL);
707 else if (IsA(jtnode, JoinExpr))
709 JoinExpr *j = (JoinExpr *) jtnode;
711 preprocess_qual_conditions(root, j->larg);
712 preprocess_qual_conditions(root, j->rarg);
714 j->quals = preprocess_expression(root, j->quals, EXPRKIND_QUAL);
717 elog(ERROR, "unrecognized node type: %d",
718 (int) nodeTag(jtnode));
722 * preprocess_phv_expression
723 * Do preprocessing on a PlaceHolderVar expression that's been pulled up.
725 * If a LATERAL subquery references an output of another subquery, and that
726 * output must be wrapped in a PlaceHolderVar because of an intermediate outer
727 * join, then we'll push the PlaceHolderVar expression down into the subquery
728 * and later pull it back up during find_lateral_references, which runs after
729 * subquery_planner has preprocessed all the expressions that were in the
730 * current query level to start with. So we need to preprocess it then.
733 preprocess_phv_expression(PlannerInfo *root, Expr *expr)
735 return (Expr *) preprocess_expression(root, (Node *) expr, EXPRKIND_PHV);
739 * inheritance_planner
740 * Generate a plan in the case where the result relation is an
743 * We have to handle this case differently from cases where a source relation
744 * is an inheritance set. Source inheritance is expanded at the bottom of the
745 * plan tree (see allpaths.c), but target inheritance has to be expanded at
746 * the top. The reason is that for UPDATE, each target relation needs a
747 * different targetlist matching its own column set. Fortunately,
748 * the UPDATE/DELETE target can never be the nullable side of an outer join,
749 * so it's OK to generate the plan this way.
751 * Returns a query plan.
754 inheritance_planner(PlannerInfo *root)
756 Query *parse = root->parse;
757 int parentRTindex = parse->resultRelation;
758 List *final_rtable = NIL;
759 int save_rel_array_size = 0;
760 RelOptInfo **save_rel_array = NULL;
761 List *subplans = NIL;
762 List *resultRelations = NIL;
763 List *returningLists = NIL;
768 * We generate a modified instance of the original Query for each target
769 * relation, plan that, and put all the plans into a list that will be
770 * controlled by a single ModifyTable node. All the instances share the
771 * same rangetable, but each instance must have its own set of subquery
772 * RTEs within the finished rangetable because (1) they are likely to get
773 * scribbled on during planning, and (2) it's not inconceivable that
774 * subqueries could get planned differently in different cases. We need
775 * not create duplicate copies of other RTE kinds, in particular not the
776 * target relations, because they don't have either of those issues. Not
777 * having to duplicate the target relations is important because doing so
778 * (1) would result in a rangetable of length O(N^2) for N targets, with
779 * at least O(N^3) work expended here; and (2) would greatly complicate
780 * management of the rowMarks list.
782 foreach(lc, root->append_rel_list)
784 AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
789 /* append_rel_list contains all append rels; ignore others */
790 if (appinfo->parent_relid != parentRTindex)
794 * We need a working copy of the PlannerInfo so that we can control
795 * propagation of information back to the main copy.
797 memcpy(&subroot, root, sizeof(PlannerInfo));
800 * Generate modified query with this rel as target. We first apply
801 * adjust_appendrel_attrs, which copies the Query and changes
802 * references to the parent RTE to refer to the current child RTE,
803 * then fool around with subquery RTEs.
805 subroot.parse = (Query *)
806 adjust_appendrel_attrs(root,
811 * The rowMarks list might contain references to subquery RTEs, so
812 * make a copy that we can apply ChangeVarNodes to. (Fortunately, the
813 * executor doesn't need to see the modified copies --- we can just
814 * pass it the original rowMarks list.)
816 subroot.rowMarks = (List *) copyObject(root->rowMarks);
819 * Add placeholders to the child Query's rangetable list to fill the
820 * RT indexes already reserved for subqueries in previous children.
821 * These won't be referenced, so there's no need to make them very
824 while (list_length(subroot.parse->rtable) < list_length(final_rtable))
825 subroot.parse->rtable = lappend(subroot.parse->rtable,
826 makeNode(RangeTblEntry));
829 * If this isn't the first child Query, generate duplicates of all
830 * subquery RTEs, and adjust Var numbering to reference the
831 * duplicates. To simplify the loop logic, we scan the original rtable
832 * not the copy just made by adjust_appendrel_attrs; that should be OK
833 * since subquery RTEs couldn't contain any references to the target
836 if (final_rtable != NIL)
841 foreach(lr, parse->rtable)
843 RangeTblEntry *rte = (RangeTblEntry *) lfirst(lr);
845 if (rte->rtekind == RTE_SUBQUERY)
850 * The RTE can't contain any references to its own RT
851 * index, so we can save a few cycles by applying
852 * ChangeVarNodes before we append the RTE to the
855 newrti = list_length(subroot.parse->rtable) + 1;
856 ChangeVarNodes((Node *) subroot.parse, rti, newrti, 0);
857 ChangeVarNodes((Node *) subroot.rowMarks, rti, newrti, 0);
858 rte = copyObject(rte);
859 subroot.parse->rtable = lappend(subroot.parse->rtable,
866 /* We needn't modify the child's append_rel_list */
867 /* There shouldn't be any OJ or LATERAL info to translate, as yet */
868 Assert(subroot.join_info_list == NIL);
869 Assert(subroot.lateral_info_list == NIL);
870 /* and we haven't created PlaceHolderInfos, either */
871 Assert(subroot.placeholder_list == NIL);
872 /* hack to mark target relation as an inheritance partition */
873 subroot.hasInheritedTarget = true;
876 subplan = grouping_planner(&subroot, 0.0 /* retrieve all tuples */ );
879 * If this child rel was excluded by constraint exclusion, exclude it
880 * from the result plan.
882 if (is_dummy_plan(subplan))
885 subplans = lappend(subplans, subplan);
888 * If this is the first non-excluded child, its post-planning rtable
889 * becomes the initial contents of final_rtable; otherwise, append
890 * just its modified subquery RTEs to final_rtable.
892 if (final_rtable == NIL)
893 final_rtable = subroot.parse->rtable;
895 final_rtable = list_concat(final_rtable,
896 list_copy_tail(subroot.parse->rtable,
897 list_length(final_rtable)));
900 * We need to collect all the RelOptInfos from all child plans into
901 * the main PlannerInfo, since setrefs.c will need them. We use the
902 * last child's simple_rel_array (previous ones are too short), so we
903 * have to propagate forward the RelOptInfos that were already built
904 * in previous children.
906 Assert(subroot.simple_rel_array_size >= save_rel_array_size);
907 for (rti = 1; rti < save_rel_array_size; rti++)
909 RelOptInfo *brel = save_rel_array[rti];
912 subroot.simple_rel_array[rti] = brel;
914 save_rel_array_size = subroot.simple_rel_array_size;
915 save_rel_array = subroot.simple_rel_array;
917 /* Make sure any initplans from this rel get into the outer list */
918 root->init_plans = subroot.init_plans;
920 /* Build list of target-relation RT indexes */
921 resultRelations = lappend_int(resultRelations, appinfo->child_relid);
923 /* Build list of per-relation RETURNING targetlists */
924 if (parse->returningList)
925 returningLists = lappend(returningLists,
926 subroot.parse->returningList);
929 /* Mark result as unordered (probably unnecessary) */
930 root->query_pathkeys = NIL;
933 * If we managed to exclude every child rel, return a dummy plan; it
934 * doesn't even need a ModifyTable node.
938 /* although dummy, it must have a valid tlist for executor */
941 tlist = preprocess_targetlist(root, parse->targetList);
942 return (Plan *) make_result(root,
944 (Node *) list_make1(makeBoolConst(false,
950 * Put back the final adjusted rtable into the master copy of the Query.
952 parse->rtable = final_rtable;
953 root->simple_rel_array_size = save_rel_array_size;
954 root->simple_rel_array = save_rel_array;
957 * If there was a FOR UPDATE/SHARE clause, the LockRows node will have
958 * dealt with fetching non-locked marked rows, else we need to have
959 * ModifyTable do that.
964 rowMarks = root->rowMarks;
966 /* And last, tack on a ModifyTable node to do the UPDATE/DELETE work */
967 return (Plan *) make_modifytable(parse->commandType,
973 SS_assign_special_param(root));
976 /*--------------------
978 * Perform planning steps related to grouping, aggregation, etc.
979 * This primarily means adding top-level processing to the basic
980 * query plan produced by query_planner.
982 * tuple_fraction is the fraction of tuples we expect will be retrieved
984 * tuple_fraction is interpreted as follows:
985 * 0: expect all tuples to be retrieved (normal case)
986 * 0 < tuple_fraction < 1: expect the given fraction of tuples available
987 * from the plan to be retrieved
988 * tuple_fraction >= 1: tuple_fraction is the absolute number of tuples
989 * expected to be retrieved (ie, a LIMIT specification)
991 * Returns a query plan. Also, root->query_pathkeys is returned as the
992 * actual output ordering of the plan (in pathkey format).
993 *--------------------
996 grouping_planner(PlannerInfo *root, double tuple_fraction)
998 Query *parse = root->parse;
999 List *tlist = parse->targetList;
1000 int64 offset_est = 0;
1001 int64 count_est = 0;
1002 double limit_tuples = -1.0;
1004 List *current_pathkeys;
1005 double dNumGroups = 0;
1006 bool use_hashed_distinct = false;
1007 bool tested_hashed_distinct = false;
1009 /* Tweak caller-supplied tuple_fraction if have LIMIT/OFFSET */
1010 if (parse->limitCount || parse->limitOffset)
1012 tuple_fraction = preprocess_limit(root, tuple_fraction,
1013 &offset_est, &count_est);
1016 * If we have a known LIMIT, and don't have an unknown OFFSET, we can
1017 * estimate the effects of using a bounded sort.
1019 if (count_est > 0 && offset_est >= 0)
1020 limit_tuples = (double) count_est + (double) offset_est;
1023 if (parse->setOperations)
1025 List *set_sortclauses;
1028 * If there's a top-level ORDER BY, assume we have to fetch all the
1029 * tuples. This might be too simplistic given all the hackery below
1030 * to possibly avoid the sort; but the odds of accurate estimates here
1031 * are pretty low anyway.
1033 if (parse->sortClause)
1034 tuple_fraction = 0.0;
1037 * Construct the plan for set operations. The result will not need
1038 * any work except perhaps a top-level sort and/or LIMIT. Note that
1039 * any special work for recursive unions is the responsibility of
1040 * plan_set_operations.
1042 result_plan = plan_set_operations(root, tuple_fraction,
1046 * Calculate pathkeys representing the sort order (if any) of the set
1047 * operation's result. We have to do this before overwriting the sort
1048 * key information...
1050 current_pathkeys = make_pathkeys_for_sortclauses(root,
1052 result_plan->targetlist,
1056 * We should not need to call preprocess_targetlist, since we must be
1057 * in a SELECT query node. Instead, use the targetlist returned by
1058 * plan_set_operations (since this tells whether it returned any
1059 * resjunk columns!), and transfer any sort key information from the
1062 Assert(parse->commandType == CMD_SELECT);
1064 tlist = postprocess_setop_tlist(copyObject(result_plan->targetlist),
1068 * Can't handle FOR UPDATE/SHARE here (parser should have checked
1069 * already, but let's make sure).
1071 if (parse->rowMarks)
1073 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
1074 errmsg("SELECT FOR UPDATE/SHARE is not allowed with UNION/INTERSECT/EXCEPT")));
1077 * Calculate pathkeys that represent result ordering requirements
1079 Assert(parse->distinctClause == NIL);
1080 root->sort_pathkeys = make_pathkeys_for_sortclauses(root,
1087 /* No set operations, do regular planning */
1089 double sub_limit_tuples;
1090 AttrNumber *groupColIdx = NULL;
1091 bool need_tlist_eval = true;
1092 Path *cheapest_path;
1096 AggClauseCosts agg_costs;
1100 bool use_hashed_grouping = false;
1101 WindowFuncLists *wflists = NULL;
1102 List *activeWindows = NIL;
1104 MemSet(&agg_costs, 0, sizeof(AggClauseCosts));
1106 /* A recursive query should always have setOperations */
1107 Assert(!root->hasRecursion);
1109 /* Preprocess GROUP BY clause, if any */
1110 if (parse->groupClause)
1111 preprocess_groupclause(root);
1112 numGroupCols = list_length(parse->groupClause);
1114 /* Preprocess targetlist */
1115 tlist = preprocess_targetlist(root, tlist);
1118 * Locate any window functions in the tlist. (We don't need to look
1119 * anywhere else, since expressions used in ORDER BY will be in there
1120 * too.) Note that they could all have been eliminated by constant
1121 * folding, in which case we don't need to do any more work.
1123 if (parse->hasWindowFuncs)
1125 wflists = find_window_functions((Node *) tlist,
1126 list_length(parse->windowClause));
1127 if (wflists->numWindowFuncs > 0)
1128 activeWindows = select_active_windows(root, wflists);
1130 parse->hasWindowFuncs = false;
1134 * Generate appropriate target list for subplan; may be different from
1135 * tlist if grouping or aggregation is needed.
1137 sub_tlist = make_subplanTargetList(root, tlist,
1138 &groupColIdx, &need_tlist_eval);
1141 * Do aggregate preprocessing, if the query has any aggs.
1143 * Note: think not that we can turn off hasAggs if we find no aggs. It
1144 * is possible for constant-expression simplification to remove all
1145 * explicit references to aggs, but we still have to follow the
1146 * aggregate semantics (eg, producing only one output row).
1151 * Collect statistics about aggregates for estimating costs. Note:
1152 * we do not attempt to detect duplicate aggregates here; a
1153 * somewhat-overestimated cost is okay for our present purposes.
1155 count_agg_clauses(root, (Node *) tlist, &agg_costs);
1156 count_agg_clauses(root, parse->havingQual, &agg_costs);
1159 * Preprocess MIN/MAX aggregates, if any. Note: be careful about
1160 * adding logic between here and the optimize_minmax_aggregates
1161 * call. Anything that is needed in MIN/MAX-optimizable cases
1162 * will have to be duplicated in planagg.c.
1164 preprocess_minmax_aggregates(root, tlist);
1168 * Calculate pathkeys that represent grouping/ordering requirements.
1169 * Stash them in PlannerInfo so that query_planner can canonicalize
1170 * them after EquivalenceClasses have been formed. The sortClause is
1171 * certainly sort-able, but GROUP BY and DISTINCT might not be, in
1172 * which case we just leave their pathkeys empty.
1174 if (parse->groupClause &&
1175 grouping_is_sortable(parse->groupClause))
1176 root->group_pathkeys =
1177 make_pathkeys_for_sortclauses(root,
1182 root->group_pathkeys = NIL;
1184 /* We consider only the first (bottom) window in pathkeys logic */
1185 if (activeWindows != NIL)
1187 WindowClause *wc = (WindowClause *) linitial(activeWindows);
1189 root->window_pathkeys = make_pathkeys_for_window(root,
1195 root->window_pathkeys = NIL;
1197 if (parse->distinctClause &&
1198 grouping_is_sortable(parse->distinctClause))
1199 root->distinct_pathkeys =
1200 make_pathkeys_for_sortclauses(root,
1201 parse->distinctClause,
1205 root->distinct_pathkeys = NIL;
1207 root->sort_pathkeys =
1208 make_pathkeys_for_sortclauses(root,
1214 * Figure out whether we want a sorted result from query_planner.
1216 * If we have a sortable GROUP BY clause, then we want a result sorted
1217 * properly for grouping. Otherwise, if we have window functions to
1218 * evaluate, we try to sort for the first window. Otherwise, if
1219 * there's a sortable DISTINCT clause that's more rigorous than the
1220 * ORDER BY clause, we try to produce output that's sufficiently well
1221 * sorted for the DISTINCT. Otherwise, if there is an ORDER BY
1222 * clause, we want to sort by the ORDER BY clause.
1224 * Note: if we have both ORDER BY and GROUP BY, and ORDER BY is a
1225 * superset of GROUP BY, it would be tempting to request sort by ORDER
1226 * BY --- but that might just leave us failing to exploit an available
1227 * sort order at all. Needs more thought. The choice for DISTINCT
1228 * versus ORDER BY is much easier, since we know that the parser
1229 * ensured that one is a superset of the other.
1231 if (root->group_pathkeys)
1232 root->query_pathkeys = root->group_pathkeys;
1233 else if (root->window_pathkeys)
1234 root->query_pathkeys = root->window_pathkeys;
1235 else if (list_length(root->distinct_pathkeys) >
1236 list_length(root->sort_pathkeys))
1237 root->query_pathkeys = root->distinct_pathkeys;
1238 else if (root->sort_pathkeys)
1239 root->query_pathkeys = root->sort_pathkeys;
1241 root->query_pathkeys = NIL;
1244 * Figure out whether there's a hard limit on the number of rows that
1245 * query_planner's result subplan needs to return. Even if we know a
1246 * hard limit overall, it doesn't apply if the query has any
1247 * grouping/aggregation operations.
1249 if (parse->groupClause ||
1250 parse->distinctClause ||
1252 parse->hasWindowFuncs ||
1253 root->hasHavingQual)
1254 sub_limit_tuples = -1.0;
1256 sub_limit_tuples = limit_tuples;
1259 * Generate the best unsorted and presorted paths for this Query (but
1260 * note there may not be any presorted path). query_planner will also
1261 * estimate the number of groups in the query, and canonicalize all
1264 query_planner(root, sub_tlist, tuple_fraction, sub_limit_tuples,
1265 &cheapest_path, &sorted_path, &dNumGroups);
1268 * Extract rowcount and width estimates for possible use in grouping
1269 * decisions. Beware here of the possibility that
1270 * cheapest_path->parent is NULL (ie, there is no FROM clause).
1272 if (cheapest_path->parent)
1274 path_rows = cheapest_path->parent->rows;
1275 path_width = cheapest_path->parent->width;
1279 path_rows = 1; /* assume non-set result */
1280 path_width = 100; /* arbitrary */
1283 if (parse->groupClause)
1286 * If grouping, decide whether to use sorted or hashed grouping.
1288 use_hashed_grouping =
1289 choose_hashed_grouping(root,
1290 tuple_fraction, limit_tuples,
1291 path_rows, path_width,
1292 cheapest_path, sorted_path,
1293 dNumGroups, &agg_costs);
1294 /* Also convert # groups to long int --- but 'ware overflow! */
1295 numGroups = (long) Min(dNumGroups, (double) LONG_MAX);
1297 else if (parse->distinctClause && sorted_path &&
1298 !root->hasHavingQual && !parse->hasAggs && !activeWindows)
1301 * We'll reach the DISTINCT stage without any intermediate
1302 * processing, so figure out whether we will want to hash or not
1303 * so we can choose whether to use cheapest or sorted path.
1305 use_hashed_distinct =
1306 choose_hashed_distinct(root,
1307 tuple_fraction, limit_tuples,
1308 path_rows, path_width,
1309 cheapest_path->startup_cost,
1310 cheapest_path->total_cost,
1311 sorted_path->startup_cost,
1312 sorted_path->total_cost,
1313 sorted_path->pathkeys,
1315 tested_hashed_distinct = true;
1319 * Select the best path. If we are doing hashed grouping, we will
1320 * always read all the input tuples, so use the cheapest-total path.
1321 * Otherwise, trust query_planner's decision about which to use.
1323 if (use_hashed_grouping || use_hashed_distinct || !sorted_path)
1324 best_path = cheapest_path;
1326 best_path = sorted_path;
1329 * Check to see if it's possible to optimize MIN/MAX aggregates. If
1330 * so, we will forget all the work we did so far to choose a "regular"
1331 * path ... but we had to do it anyway to be able to tell which way is
1334 result_plan = optimize_minmax_aggregates(root,
1338 if (result_plan != NULL)
1341 * optimize_minmax_aggregates generated the full plan, with the
1342 * right tlist, and it has no sort order.
1344 current_pathkeys = NIL;
1349 * Normal case --- create a plan according to query_planner's
1352 bool need_sort_for_grouping = false;
1354 result_plan = create_plan(root, best_path);
1355 current_pathkeys = best_path->pathkeys;
1357 /* Detect if we'll need an explicit sort for grouping */
1358 if (parse->groupClause && !use_hashed_grouping &&
1359 !pathkeys_contained_in(root->group_pathkeys, current_pathkeys))
1361 need_sort_for_grouping = true;
1364 * Always override create_plan's tlist, so that we don't sort
1365 * useless data from a "physical" tlist.
1367 need_tlist_eval = true;
1371 * create_plan returns a plan with just a "flat" tlist of required
1372 * Vars. Usually we need to insert the sub_tlist as the tlist of
1373 * the top plan node. However, we can skip that if we determined
1374 * that whatever create_plan chose to return will be good enough.
1376 if (need_tlist_eval)
1379 * If the top-level plan node is one that cannot do expression
1380 * evaluation, we must insert a Result node to project the
1383 if (!is_projection_capable_plan(result_plan))
1385 result_plan = (Plan *) make_result(root,
1393 * Otherwise, just replace the subplan's flat tlist with
1394 * the desired tlist.
1396 result_plan->targetlist = sub_tlist;
1400 * Also, account for the cost of evaluation of the sub_tlist.
1401 * See comments for add_tlist_costs_to_plan() for more info.
1403 add_tlist_costs_to_plan(root, result_plan, sub_tlist);
1408 * Since we're using create_plan's tlist and not the one
1409 * make_subplanTargetList calculated, we have to refigure any
1410 * grouping-column indexes make_subplanTargetList computed.
1412 locate_grouping_columns(root, tlist, result_plan->targetlist,
1417 * Insert AGG or GROUP node if needed, plus an explicit sort step
1420 * HAVING clause, if any, becomes qual of the Agg or Group node.
1422 if (use_hashed_grouping)
1424 /* Hashed aggregate plan --- no sort needed */
1425 result_plan = (Plan *) make_agg(root,
1427 (List *) parse->havingQual,
1432 extract_grouping_ops(parse->groupClause),
1435 /* Hashed aggregation produces randomly-ordered results */
1436 current_pathkeys = NIL;
1438 else if (parse->hasAggs)
1440 /* Plain aggregate plan --- sort if needed */
1441 AggStrategy aggstrategy;
1443 if (parse->groupClause)
1445 if (need_sort_for_grouping)
1447 result_plan = (Plan *)
1448 make_sort_from_groupcols(root,
1452 current_pathkeys = root->group_pathkeys;
1454 aggstrategy = AGG_SORTED;
1457 * The AGG node will not change the sort ordering of its
1458 * groups, so current_pathkeys describes the result too.
1463 aggstrategy = AGG_PLAIN;
1464 /* Result will be only one row anyway; no sort order */
1465 current_pathkeys = NIL;
1468 result_plan = (Plan *) make_agg(root,
1470 (List *) parse->havingQual,
1475 extract_grouping_ops(parse->groupClause),
1479 else if (parse->groupClause)
1482 * GROUP BY without aggregation, so insert a group node (plus
1483 * the appropriate sort node, if necessary).
1485 * Add an explicit sort if we couldn't make the path come out
1486 * the way the GROUP node needs it.
1488 if (need_sort_for_grouping)
1490 result_plan = (Plan *)
1491 make_sort_from_groupcols(root,
1495 current_pathkeys = root->group_pathkeys;
1498 result_plan = (Plan *) make_group(root,
1500 (List *) parse->havingQual,
1503 extract_grouping_ops(parse->groupClause),
1506 /* The Group node won't change sort ordering */
1508 else if (root->hasHavingQual)
1511 * No aggregates, and no GROUP BY, but we have a HAVING qual.
1512 * This is a degenerate case in which we are supposed to emit
1513 * either 0 or 1 row depending on whether HAVING succeeds.
1514 * Furthermore, there cannot be any variables in either HAVING
1515 * or the targetlist, so we actually do not need the FROM
1516 * table at all! We can just throw away the plan-so-far and
1517 * generate a Result node. This is a sufficiently unusual
1518 * corner case that it's not worth contorting the structure of
1519 * this routine to avoid having to generate the plan in the
1522 result_plan = (Plan *) make_result(root,
1527 } /* end of non-minmax-aggregate case */
1530 * Since each window function could require a different sort order, we
1531 * stack up a WindowAgg node for each window, with sort steps between
1540 * If the top-level plan node is one that cannot do expression
1541 * evaluation, we must insert a Result node to project the desired
1542 * tlist. (In some cases this might not really be required, but
1543 * it's not worth trying to avoid it.) Note that on second and
1544 * subsequent passes through the following loop, the top-level
1545 * node will be a WindowAgg which we know can project; so we only
1546 * need to check once.
1548 if (!is_projection_capable_plan(result_plan))
1550 result_plan = (Plan *) make_result(root,
1557 * The "base" targetlist for all steps of the windowing process is
1558 * a flat tlist of all Vars and Aggs needed in the result. (In
1559 * some cases we wouldn't need to propagate all of these all the
1560 * way to the top, since they might only be needed as inputs to
1561 * WindowFuncs. It's probably not worth trying to optimize that
1562 * though.) We also need any volatile sort expressions, because
1563 * make_sort_from_pathkeys won't add those on its own, and anyway
1564 * we want them evaluated only once at the bottom of the stack. As
1565 * we climb up the stack, we add outputs for the WindowFuncs
1566 * computed at each level. Also, each input tlist has to present
1567 * all the columns needed to sort the data for the next WindowAgg
1568 * step. That's handled internally by make_sort_from_pathkeys,
1569 * but we need the copyObject steps here to ensure that each plan
1570 * node has a separately modifiable tlist.
1572 * Note: it's essential here to use PVC_INCLUDE_AGGREGATES so that
1573 * Vars mentioned only in aggregate expressions aren't pulled out
1574 * as separate targetlist entries. Otherwise we could be putting
1575 * ungrouped Vars directly into an Agg node's tlist, resulting in
1576 * undefined behavior.
1578 window_tlist = flatten_tlist(tlist,
1579 PVC_INCLUDE_AGGREGATES,
1580 PVC_INCLUDE_PLACEHOLDERS);
1581 window_tlist = add_volatile_sort_exprs(window_tlist, tlist,
1583 result_plan->targetlist = (List *) copyObject(window_tlist);
1585 foreach(l, activeWindows)
1587 WindowClause *wc = (WindowClause *) lfirst(l);
1588 List *window_pathkeys;
1590 AttrNumber *partColIdx;
1593 AttrNumber *ordColIdx;
1596 window_pathkeys = make_pathkeys_for_window(root,
1602 * This is a bit tricky: we build a sort node even if we don't
1603 * really have to sort. Even when no explicit sort is needed,
1604 * we need to have suitable resjunk items added to the input
1605 * plan's tlist for any partitioning or ordering columns that
1606 * aren't plain Vars. Furthermore, this way we can use
1607 * existing infrastructure to identify which input columns are
1608 * the interesting ones.
1610 if (window_pathkeys)
1614 sort_plan = make_sort_from_pathkeys(root,
1618 if (!pathkeys_contained_in(window_pathkeys,
1621 /* we do indeed need to sort */
1622 result_plan = (Plan *) sort_plan;
1623 current_pathkeys = window_pathkeys;
1625 /* In either case, extract the per-column information */
1626 get_column_info_for_window(root, wc, tlist,
1628 sort_plan->sortColIdx,
1638 /* empty window specification, nothing to sort */
1641 partOperators = NULL;
1644 ordOperators = NULL;
1649 /* Add the current WindowFuncs to the running tlist */
1650 window_tlist = add_to_flat_tlist(window_tlist,
1651 wflists->windowFuncs[wc->winref]);
1655 /* Install the original tlist in the topmost WindowAgg */
1656 window_tlist = tlist;
1659 /* ... and make the WindowAgg plan node */
1660 result_plan = (Plan *)
1661 make_windowagg(root,
1662 (List *) copyObject(window_tlist),
1663 wflists->windowFuncs[wc->winref],
1677 } /* end of if (setOperations) */
1680 * If there is a DISTINCT clause, add the necessary node(s).
1682 if (parse->distinctClause)
1684 double dNumDistinctRows;
1685 long numDistinctRows;
1688 * If there was grouping or aggregation, use the current number of
1689 * rows as the estimated number of DISTINCT rows (ie, assume the
1690 * result was already mostly unique). If not, use the number of
1691 * distinct-groups calculated by query_planner.
1693 if (parse->groupClause || root->hasHavingQual || parse->hasAggs)
1694 dNumDistinctRows = result_plan->plan_rows;
1696 dNumDistinctRows = dNumGroups;
1698 /* Also convert to long int --- but 'ware overflow! */
1699 numDistinctRows = (long) Min(dNumDistinctRows, (double) LONG_MAX);
1701 /* Choose implementation method if we didn't already */
1702 if (!tested_hashed_distinct)
1705 * At this point, either hashed or sorted grouping will have to
1706 * work from result_plan, so we pass that as both "cheapest" and
1709 use_hashed_distinct =
1710 choose_hashed_distinct(root,
1711 tuple_fraction, limit_tuples,
1712 result_plan->plan_rows,
1713 result_plan->plan_width,
1714 result_plan->startup_cost,
1715 result_plan->total_cost,
1716 result_plan->startup_cost,
1717 result_plan->total_cost,
1722 if (use_hashed_distinct)
1724 /* Hashed aggregate plan --- no sort needed */
1725 result_plan = (Plan *) make_agg(root,
1726 result_plan->targetlist,
1730 list_length(parse->distinctClause),
1731 extract_grouping_cols(parse->distinctClause,
1732 result_plan->targetlist),
1733 extract_grouping_ops(parse->distinctClause),
1736 /* Hashed aggregation produces randomly-ordered results */
1737 current_pathkeys = NIL;
1742 * Use a Unique node to implement DISTINCT. Add an explicit sort
1743 * if we couldn't make the path come out the way the Unique node
1744 * needs it. If we do have to sort, always sort by the more
1745 * rigorous of DISTINCT and ORDER BY, to avoid a second sort
1746 * below. However, for regular DISTINCT, don't sort now if we
1747 * don't have to --- sorting afterwards will likely be cheaper,
1748 * and also has the possibility of optimizing via LIMIT. But for
1749 * DISTINCT ON, we *must* force the final sort now, else it won't
1750 * have the desired behavior.
1752 List *needed_pathkeys;
1754 if (parse->hasDistinctOn &&
1755 list_length(root->distinct_pathkeys) <
1756 list_length(root->sort_pathkeys))
1757 needed_pathkeys = root->sort_pathkeys;
1759 needed_pathkeys = root->distinct_pathkeys;
1761 if (!pathkeys_contained_in(needed_pathkeys, current_pathkeys))
1763 if (list_length(root->distinct_pathkeys) >=
1764 list_length(root->sort_pathkeys))
1765 current_pathkeys = root->distinct_pathkeys;
1768 current_pathkeys = root->sort_pathkeys;
1769 /* Assert checks that parser didn't mess up... */
1770 Assert(pathkeys_contained_in(root->distinct_pathkeys,
1774 result_plan = (Plan *) make_sort_from_pathkeys(root,
1780 result_plan = (Plan *) make_unique(result_plan,
1781 parse->distinctClause);
1782 result_plan->plan_rows = dNumDistinctRows;
1783 /* The Unique node won't change sort ordering */
1788 * If ORDER BY was given and we were not able to make the plan come out in
1789 * the right order, add an explicit sort step.
1791 if (parse->sortClause)
1793 if (!pathkeys_contained_in(root->sort_pathkeys, current_pathkeys))
1795 result_plan = (Plan *) make_sort_from_pathkeys(root,
1797 root->sort_pathkeys,
1799 current_pathkeys = root->sort_pathkeys;
1804 * If there is a FOR UPDATE/SHARE clause, add the LockRows node. (Note: we
1805 * intentionally test parse->rowMarks not root->rowMarks here. If there
1806 * are only non-locking rowmarks, they should be handled by the
1807 * ModifyTable node instead.)
1809 if (parse->rowMarks)
1811 result_plan = (Plan *) make_lockrows(result_plan,
1813 SS_assign_special_param(root));
1816 * The result can no longer be assumed sorted, since locking might
1817 * cause the sort key columns to be replaced with new values.
1819 current_pathkeys = NIL;
1823 * Finally, if there is a LIMIT/OFFSET clause, add the LIMIT node.
1825 if (parse->limitCount || parse->limitOffset)
1827 result_plan = (Plan *) make_limit(result_plan,
1835 * Return the actual output ordering in query_pathkeys for possible use by
1836 * an outer query level.
1838 root->query_pathkeys = current_pathkeys;
1844 * add_tlist_costs_to_plan
1846 * Estimate the execution costs associated with evaluating the targetlist
1847 * expressions, and add them to the cost estimates for the Plan node.
1849 * If the tlist contains set-returning functions, also inflate the Plan's cost
1850 * and plan_rows estimates accordingly. (Hence, this must be called *after*
1851 * any logic that uses plan_rows to, eg, estimate qual evaluation costs.)
1853 * Note: during initial stages of planning, we mostly consider plan nodes with
1854 * "flat" tlists, containing just Vars. So their evaluation cost is zero
1855 * according to the model used by cost_qual_eval() (or if you prefer, the cost
1856 * is factored into cpu_tuple_cost). Thus we can avoid accounting for tlist
1857 * cost throughout query_planner() and subroutines. But once we apply a
1858 * tlist that might contain actual operators, sub-selects, etc, we'd better
1859 * account for its cost. Any set-returning functions in the tlist must also
1860 * affect the estimated rowcount.
1862 * Once grouping_planner() has applied a general tlist to the topmost
1863 * scan/join plan node, any tlist eval cost for added-on nodes should be
1864 * accounted for as we create those nodes. Presently, of the node types we
1865 * can add on later, only Agg, WindowAgg, and Group project new tlists (the
1866 * rest just copy their input tuples) --- so make_agg(), make_windowagg() and
1867 * make_group() are responsible for calling this function to account for their
1871 add_tlist_costs_to_plan(PlannerInfo *root, Plan *plan, List *tlist)
1873 QualCost tlist_cost;
1876 cost_qual_eval(&tlist_cost, tlist, root);
1877 plan->startup_cost += tlist_cost.startup;
1878 plan->total_cost += tlist_cost.startup +
1879 tlist_cost.per_tuple * plan->plan_rows;
1881 tlist_rows = tlist_returns_set_rows(tlist);
1885 * We assume that execution costs of the tlist proper were all
1886 * accounted for by cost_qual_eval. However, it still seems
1887 * appropriate to charge something more for the executor's general
1888 * costs of processing the added tuples. The cost is probably less
1889 * than cpu_tuple_cost, though, so we arbitrarily use half of that.
1891 plan->total_cost += plan->plan_rows * (tlist_rows - 1) *
1894 plan->plan_rows *= tlist_rows;
1899 * Detect whether a plan node is a "dummy" plan created when a relation
1900 * is deemed not to need scanning due to constraint exclusion.
1902 * Currently, such dummy plans are Result nodes with constant FALSE
1903 * filter quals (see set_dummy_rel_pathlist and create_append_plan).
1905 * XXX this probably ought to be somewhere else, but not clear where.
1908 is_dummy_plan(Plan *plan)
1910 if (IsA(plan, Result))
1912 List *rcqual = (List *) ((Result *) plan)->resconstantqual;
1914 if (list_length(rcqual) == 1)
1916 Const *constqual = (Const *) linitial(rcqual);
1918 if (constqual && IsA(constqual, Const))
1920 if (!constqual->constisnull &&
1921 !DatumGetBool(constqual->constvalue))
1930 * Create a bitmapset of the RT indexes of live base relations
1932 * Helper for preprocess_rowmarks ... at this point in the proceedings,
1933 * the only good way to distinguish baserels from appendrel children
1934 * is to see what is in the join tree.
1937 get_base_rel_indexes(Node *jtnode)
1943 if (IsA(jtnode, RangeTblRef))
1945 int varno = ((RangeTblRef *) jtnode)->rtindex;
1947 result = bms_make_singleton(varno);
1949 else if (IsA(jtnode, FromExpr))
1951 FromExpr *f = (FromExpr *) jtnode;
1955 foreach(l, f->fromlist)
1956 result = bms_join(result,
1957 get_base_rel_indexes(lfirst(l)));
1959 else if (IsA(jtnode, JoinExpr))
1961 JoinExpr *j = (JoinExpr *) jtnode;
1963 result = bms_join(get_base_rel_indexes(j->larg),
1964 get_base_rel_indexes(j->rarg));
1968 elog(ERROR, "unrecognized node type: %d",
1969 (int) nodeTag(jtnode));
1970 result = NULL; /* keep compiler quiet */
1976 * preprocess_rowmarks - set up PlanRowMarks if needed
1979 preprocess_rowmarks(PlannerInfo *root)
1981 Query *parse = root->parse;
1987 if (parse->rowMarks)
1990 * We've got trouble if FOR UPDATE/SHARE appears inside grouping,
1991 * since grouping renders a reference to individual tuple CTIDs
1992 * invalid. This is also checked at parse time, but that's
1993 * insufficient because of rule substitution, query pullup, etc.
1995 CheckSelectLocking(parse);
2000 * We only need rowmarks for UPDATE, DELETE, or FOR UPDATE/SHARE.
2002 if (parse->commandType != CMD_UPDATE &&
2003 parse->commandType != CMD_DELETE)
2008 * We need to have rowmarks for all base relations except the target. We
2009 * make a bitmapset of all base rels and then remove the items we don't
2010 * need or have FOR UPDATE/SHARE marks for.
2012 rels = get_base_rel_indexes((Node *) parse->jointree);
2013 if (parse->resultRelation)
2014 rels = bms_del_member(rels, parse->resultRelation);
2017 * Convert RowMarkClauses to PlanRowMark representation.
2020 foreach(l, parse->rowMarks)
2022 RowMarkClause *rc = (RowMarkClause *) lfirst(l);
2023 RangeTblEntry *rte = rt_fetch(rc->rti, parse->rtable);
2027 * Currently, it is syntactically impossible to have FOR UPDATE
2028 * applied to an update/delete target rel. If that ever becomes
2029 * possible, we should drop the target from the PlanRowMark list.
2031 Assert(rc->rti != parse->resultRelation);
2034 * Ignore RowMarkClauses for subqueries; they aren't real tables and
2035 * can't support true locking. Subqueries that got flattened into the
2036 * main query should be ignored completely. Any that didn't will get
2037 * ROW_MARK_COPY items in the next loop.
2039 if (rte->rtekind != RTE_RELATION)
2042 rels = bms_del_member(rels, rc->rti);
2044 newrc = makeNode(PlanRowMark);
2045 newrc->rti = newrc->prti = rc->rti;
2046 newrc->rowmarkId = ++(root->glob->lastRowMarkId);
2048 newrc->markType = ROW_MARK_EXCLUSIVE;
2050 newrc->markType = ROW_MARK_SHARE;
2051 newrc->noWait = rc->noWait;
2052 newrc->isParent = false;
2054 prowmarks = lappend(prowmarks, newrc);
2058 * Now, add rowmarks for any non-target, non-locked base relations.
2061 foreach(l, parse->rtable)
2063 RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
2067 if (!bms_is_member(i, rels))
2070 newrc = makeNode(PlanRowMark);
2071 newrc->rti = newrc->prti = i;
2072 newrc->rowmarkId = ++(root->glob->lastRowMarkId);
2073 /* real tables support REFERENCE, anything else needs COPY */
2074 if (rte->rtekind == RTE_RELATION &&
2075 rte->relkind != RELKIND_FOREIGN_TABLE)
2076 newrc->markType = ROW_MARK_REFERENCE;
2078 newrc->markType = ROW_MARK_COPY;
2079 newrc->noWait = false; /* doesn't matter */
2080 newrc->isParent = false;
2082 prowmarks = lappend(prowmarks, newrc);
2085 root->rowMarks = prowmarks;
2089 * preprocess_limit - do pre-estimation for LIMIT and/or OFFSET clauses
2091 * We try to estimate the values of the LIMIT/OFFSET clauses, and pass the
2092 * results back in *count_est and *offset_est. These variables are set to
2093 * 0 if the corresponding clause is not present, and -1 if it's present
2094 * but we couldn't estimate the value for it. (The "0" convention is OK
2095 * for OFFSET but a little bit bogus for LIMIT: effectively we estimate
2096 * LIMIT 0 as though it were LIMIT 1. But this is in line with the planner's
2097 * usual practice of never estimating less than one row.) These values will
2098 * be passed to make_limit, which see if you change this code.
2100 * The return value is the suitably adjusted tuple_fraction to use for
2101 * planning the query. This adjustment is not overridable, since it reflects
2102 * plan actions that grouping_planner() will certainly take, not assumptions
2106 preprocess_limit(PlannerInfo *root, double tuple_fraction,
2107 int64 *offset_est, int64 *count_est)
2109 Query *parse = root->parse;
2111 double limit_fraction;
2113 /* Should not be called unless LIMIT or OFFSET */
2114 Assert(parse->limitCount || parse->limitOffset);
2117 * Try to obtain the clause values. We use estimate_expression_value
2118 * primarily because it can sometimes do something useful with Params.
2120 if (parse->limitCount)
2122 est = estimate_expression_value(root, parse->limitCount);
2123 if (est && IsA(est, Const))
2125 if (((Const *) est)->constisnull)
2127 /* NULL indicates LIMIT ALL, ie, no limit */
2128 *count_est = 0; /* treat as not present */
2132 *count_est = DatumGetInt64(((Const *) est)->constvalue);
2133 if (*count_est <= 0)
2134 *count_est = 1; /* force to at least 1 */
2138 *count_est = -1; /* can't estimate */
2141 *count_est = 0; /* not present */
2143 if (parse->limitOffset)
2145 est = estimate_expression_value(root, parse->limitOffset);
2146 if (est && IsA(est, Const))
2148 if (((Const *) est)->constisnull)
2150 /* Treat NULL as no offset; the executor will too */
2151 *offset_est = 0; /* treat as not present */
2155 *offset_est = DatumGetInt64(((Const *) est)->constvalue);
2156 if (*offset_est < 0)
2157 *offset_est = 0; /* less than 0 is same as 0 */
2161 *offset_est = -1; /* can't estimate */
2164 *offset_est = 0; /* not present */
2166 if (*count_est != 0)
2169 * A LIMIT clause limits the absolute number of tuples returned.
2170 * However, if it's not a constant LIMIT then we have to guess; for
2171 * lack of a better idea, assume 10% of the plan's result is wanted.
2173 if (*count_est < 0 || *offset_est < 0)
2175 /* LIMIT or OFFSET is an expression ... punt ... */
2176 limit_fraction = 0.10;
2180 /* LIMIT (plus OFFSET, if any) is max number of tuples needed */
2181 limit_fraction = (double) *count_est + (double) *offset_est;
2185 * If we have absolute limits from both caller and LIMIT, use the
2186 * smaller value; likewise if they are both fractional. If one is
2187 * fractional and the other absolute, we can't easily determine which
2188 * is smaller, but we use the heuristic that the absolute will usually
2191 if (tuple_fraction >= 1.0)
2193 if (limit_fraction >= 1.0)
2196 tuple_fraction = Min(tuple_fraction, limit_fraction);
2200 /* caller absolute, limit fractional; use caller's value */
2203 else if (tuple_fraction > 0.0)
2205 if (limit_fraction >= 1.0)
2207 /* caller fractional, limit absolute; use limit */
2208 tuple_fraction = limit_fraction;
2212 /* both fractional */
2213 tuple_fraction = Min(tuple_fraction, limit_fraction);
2218 /* no info from caller, just use limit */
2219 tuple_fraction = limit_fraction;
2222 else if (*offset_est != 0 && tuple_fraction > 0.0)
2225 * We have an OFFSET but no LIMIT. This acts entirely differently
2226 * from the LIMIT case: here, we need to increase rather than decrease
2227 * the caller's tuple_fraction, because the OFFSET acts to cause more
2228 * tuples to be fetched instead of fewer. This only matters if we got
2229 * a tuple_fraction > 0, however.
2231 * As above, use 10% if OFFSET is present but unestimatable.
2233 if (*offset_est < 0)
2234 limit_fraction = 0.10;
2236 limit_fraction = (double) *offset_est;
2239 * If we have absolute counts from both caller and OFFSET, add them
2240 * together; likewise if they are both fractional. If one is
2241 * fractional and the other absolute, we want to take the larger, and
2242 * we heuristically assume that's the fractional one.
2244 if (tuple_fraction >= 1.0)
2246 if (limit_fraction >= 1.0)
2248 /* both absolute, so add them together */
2249 tuple_fraction += limit_fraction;
2253 /* caller absolute, limit fractional; use limit */
2254 tuple_fraction = limit_fraction;
2259 if (limit_fraction >= 1.0)
2261 /* caller fractional, limit absolute; use caller's value */
2265 /* both fractional, so add them together */
2266 tuple_fraction += limit_fraction;
2267 if (tuple_fraction >= 1.0)
2268 tuple_fraction = 0.0; /* assume fetch all */
2273 return tuple_fraction;
2278 * preprocess_groupclause - do preparatory work on GROUP BY clause
2280 * The idea here is to adjust the ordering of the GROUP BY elements
2281 * (which in itself is semantically insignificant) to match ORDER BY,
2282 * thereby allowing a single sort operation to both implement the ORDER BY
2283 * requirement and set up for a Unique step that implements GROUP BY.
2285 * In principle it might be interesting to consider other orderings of the
2286 * GROUP BY elements, which could match the sort ordering of other
2287 * possible plans (eg an indexscan) and thereby reduce cost. We don't
2288 * bother with that, though. Hashed grouping will frequently win anyway.
2290 * Note: we need no comparable processing of the distinctClause because
2291 * the parser already enforced that that matches ORDER BY.
2294 preprocess_groupclause(PlannerInfo *root)
2296 Query *parse = root->parse;
2297 List *new_groupclause;
2302 /* If no ORDER BY, nothing useful to do here */
2303 if (parse->sortClause == NIL)
2307 * Scan the ORDER BY clause and construct a list of matching GROUP BY
2308 * items, but only as far as we can make a matching prefix.
2310 * This code assumes that the sortClause contains no duplicate items.
2312 new_groupclause = NIL;
2313 foreach(sl, parse->sortClause)
2315 SortGroupClause *sc = (SortGroupClause *) lfirst(sl);
2317 foreach(gl, parse->groupClause)
2319 SortGroupClause *gc = (SortGroupClause *) lfirst(gl);
2323 new_groupclause = lappend(new_groupclause, gc);
2328 break; /* no match, so stop scanning */
2331 /* Did we match all of the ORDER BY list, or just some of it? */
2332 partial_match = (sl != NULL);
2334 /* If no match at all, no point in reordering GROUP BY */
2335 if (new_groupclause == NIL)
2339 * Add any remaining GROUP BY items to the new list, but only if we were
2340 * able to make a complete match. In other words, we only rearrange the
2341 * GROUP BY list if the result is that one list is a prefix of the other
2342 * --- otherwise there's no possibility of a common sort. Also, give up
2343 * if there are any non-sortable GROUP BY items, since then there's no
2346 foreach(gl, parse->groupClause)
2348 SortGroupClause *gc = (SortGroupClause *) lfirst(gl);
2350 if (list_member_ptr(new_groupclause, gc))
2351 continue; /* it matched an ORDER BY item */
2353 return; /* give up, no common sort possible */
2354 if (!OidIsValid(gc->sortop))
2355 return; /* give up, GROUP BY can't be sorted */
2356 new_groupclause = lappend(new_groupclause, gc);
2359 /* Success --- install the rearranged GROUP BY list */
2360 Assert(list_length(parse->groupClause) == list_length(new_groupclause));
2361 parse->groupClause = new_groupclause;
2365 * choose_hashed_grouping - should we use hashed grouping?
2367 * Returns TRUE to select hashing, FALSE to select sorting.
2370 choose_hashed_grouping(PlannerInfo *root,
2371 double tuple_fraction, double limit_tuples,
2372 double path_rows, int path_width,
2373 Path *cheapest_path, Path *sorted_path,
2374 double dNumGroups, AggClauseCosts *agg_costs)
2376 Query *parse = root->parse;
2377 int numGroupCols = list_length(parse->groupClause);
2381 List *target_pathkeys;
2382 List *current_pathkeys;
2387 * Executor doesn't support hashed aggregation with DISTINCT or ORDER BY
2388 * aggregates. (Doing so would imply storing *all* the input values in
2389 * the hash table, and/or running many sorts in parallel, either of which
2390 * seems like a certain loser.)
2392 can_hash = (agg_costs->numOrderedAggs == 0 &&
2393 grouping_is_hashable(parse->groupClause));
2394 can_sort = grouping_is_sortable(parse->groupClause);
2396 /* Quick out if only one choice is workable */
2397 if (!(can_hash && can_sort))
2405 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
2406 errmsg("could not implement GROUP BY"),
2407 errdetail("Some of the datatypes only support hashing, while others only support sorting.")));
2410 /* Prefer sorting when enable_hashagg is off */
2411 if (!enable_hashagg)
2415 * Don't do it if it doesn't look like the hashtable will fit into
2419 /* Estimate per-hash-entry space at tuple width... */
2420 hashentrysize = MAXALIGN(path_width) + MAXALIGN(sizeof(MinimalTupleData));
2421 /* plus space for pass-by-ref transition values... */
2422 hashentrysize += agg_costs->transitionSpace;
2423 /* plus the per-hash-entry overhead */
2424 hashentrysize += hash_agg_entry_size(agg_costs->numAggs);
2426 if (hashentrysize * dNumGroups > work_mem * 1024L)
2430 * When we have both GROUP BY and DISTINCT, use the more-rigorous of
2431 * DISTINCT and ORDER BY as the assumed required output sort order. This
2432 * is an oversimplification because the DISTINCT might get implemented via
2433 * hashing, but it's not clear that the case is common enough (or that our
2434 * estimates are good enough) to justify trying to solve it exactly.
2436 if (list_length(root->distinct_pathkeys) >
2437 list_length(root->sort_pathkeys))
2438 target_pathkeys = root->distinct_pathkeys;
2440 target_pathkeys = root->sort_pathkeys;
2443 * See if the estimated cost is no more than doing it the other way. While
2444 * avoiding the need for sorted input is usually a win, the fact that the
2445 * output won't be sorted may be a loss; so we need to do an actual cost
2448 * We need to consider cheapest_path + hashagg [+ final sort] versus
2449 * either cheapest_path [+ sort] + group or agg [+ final sort] or
2450 * presorted_path + group or agg [+ final sort] where brackets indicate a
2451 * step that may not be needed. We assume query_planner() will have
2452 * returned a presorted path only if it's a winner compared to
2453 * cheapest_path for this purpose.
2455 * These path variables are dummies that just hold cost fields; we don't
2456 * make actual Paths for these steps.
2458 cost_agg(&hashed_p, root, AGG_HASHED, agg_costs,
2459 numGroupCols, dNumGroups,
2460 cheapest_path->startup_cost, cheapest_path->total_cost,
2462 /* Result of hashed agg is always unsorted */
2463 if (target_pathkeys)
2464 cost_sort(&hashed_p, root, target_pathkeys, hashed_p.total_cost,
2465 dNumGroups, path_width,
2466 0.0, work_mem, limit_tuples);
2470 sorted_p.startup_cost = sorted_path->startup_cost;
2471 sorted_p.total_cost = sorted_path->total_cost;
2472 current_pathkeys = sorted_path->pathkeys;
2476 sorted_p.startup_cost = cheapest_path->startup_cost;
2477 sorted_p.total_cost = cheapest_path->total_cost;
2478 current_pathkeys = cheapest_path->pathkeys;
2480 if (!pathkeys_contained_in(root->group_pathkeys, current_pathkeys))
2482 cost_sort(&sorted_p, root, root->group_pathkeys, sorted_p.total_cost,
2483 path_rows, path_width,
2484 0.0, work_mem, -1.0);
2485 current_pathkeys = root->group_pathkeys;
2489 cost_agg(&sorted_p, root, AGG_SORTED, agg_costs,
2490 numGroupCols, dNumGroups,
2491 sorted_p.startup_cost, sorted_p.total_cost,
2494 cost_group(&sorted_p, root, numGroupCols, dNumGroups,
2495 sorted_p.startup_cost, sorted_p.total_cost,
2497 /* The Agg or Group node will preserve ordering */
2498 if (target_pathkeys &&
2499 !pathkeys_contained_in(target_pathkeys, current_pathkeys))
2500 cost_sort(&sorted_p, root, target_pathkeys, sorted_p.total_cost,
2501 dNumGroups, path_width,
2502 0.0, work_mem, limit_tuples);
2505 * Now make the decision using the top-level tuple fraction. First we
2506 * have to convert an absolute count (LIMIT) into fractional form.
2508 if (tuple_fraction >= 1.0)
2509 tuple_fraction /= dNumGroups;
2511 if (compare_fractional_path_costs(&hashed_p, &sorted_p,
2512 tuple_fraction) < 0)
2514 /* Hashed is cheaper, so use it */
2521 * choose_hashed_distinct - should we use hashing for DISTINCT?
2523 * This is fairly similar to choose_hashed_grouping, but there are enough
2524 * differences that it doesn't seem worth trying to unify the two functions.
2525 * (One difference is that we sometimes apply this after forming a Plan,
2526 * so the input alternatives can't be represented as Paths --- instead we
2527 * pass in the costs as individual variables.)
2529 * But note that making the two choices independently is a bit bogus in
2530 * itself. If the two could be combined into a single choice operation
2531 * it'd probably be better, but that seems far too unwieldy to be practical,
2532 * especially considering that the combination of GROUP BY and DISTINCT
2533 * isn't very common in real queries. By separating them, we are giving
2534 * extra preference to using a sorting implementation when a common sort key
2535 * is available ... and that's not necessarily wrong anyway.
2537 * Returns TRUE to select hashing, FALSE to select sorting.
2540 choose_hashed_distinct(PlannerInfo *root,
2541 double tuple_fraction, double limit_tuples,
2542 double path_rows, int path_width,
2543 Cost cheapest_startup_cost, Cost cheapest_total_cost,
2544 Cost sorted_startup_cost, Cost sorted_total_cost,
2545 List *sorted_pathkeys,
2546 double dNumDistinctRows)
2548 Query *parse = root->parse;
2549 int numDistinctCols = list_length(parse->distinctClause);
2553 List *current_pathkeys;
2554 List *needed_pathkeys;
2559 * If we have a sortable DISTINCT ON clause, we always use sorting. This
2560 * enforces the expected behavior of DISTINCT ON.
2562 can_sort = grouping_is_sortable(parse->distinctClause);
2563 if (can_sort && parse->hasDistinctOn)
2566 can_hash = grouping_is_hashable(parse->distinctClause);
2568 /* Quick out if only one choice is workable */
2569 if (!(can_hash && can_sort))
2577 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
2578 errmsg("could not implement DISTINCT"),
2579 errdetail("Some of the datatypes only support hashing, while others only support sorting.")));
2582 /* Prefer sorting when enable_hashagg is off */
2583 if (!enable_hashagg)
2587 * Don't do it if it doesn't look like the hashtable will fit into
2590 hashentrysize = MAXALIGN(path_width) + MAXALIGN(sizeof(MinimalTupleData));
2592 if (hashentrysize * dNumDistinctRows > work_mem * 1024L)
2596 * See if the estimated cost is no more than doing it the other way. While
2597 * avoiding the need for sorted input is usually a win, the fact that the
2598 * output won't be sorted may be a loss; so we need to do an actual cost
2601 * We need to consider cheapest_path + hashagg [+ final sort] versus
2602 * sorted_path [+ sort] + group [+ final sort] where brackets indicate a
2603 * step that may not be needed.
2605 * These path variables are dummies that just hold cost fields; we don't
2606 * make actual Paths for these steps.
2608 cost_agg(&hashed_p, root, AGG_HASHED, NULL,
2609 numDistinctCols, dNumDistinctRows,
2610 cheapest_startup_cost, cheapest_total_cost,
2614 * Result of hashed agg is always unsorted, so if ORDER BY is present we
2615 * need to charge for the final sort.
2617 if (parse->sortClause)
2618 cost_sort(&hashed_p, root, root->sort_pathkeys, hashed_p.total_cost,
2619 dNumDistinctRows, path_width,
2620 0.0, work_mem, limit_tuples);
2623 * Now for the GROUP case. See comments in grouping_planner about the
2624 * sorting choices here --- this code should match that code.
2626 sorted_p.startup_cost = sorted_startup_cost;
2627 sorted_p.total_cost = sorted_total_cost;
2628 current_pathkeys = sorted_pathkeys;
2629 if (parse->hasDistinctOn &&
2630 list_length(root->distinct_pathkeys) <
2631 list_length(root->sort_pathkeys))
2632 needed_pathkeys = root->sort_pathkeys;
2634 needed_pathkeys = root->distinct_pathkeys;
2635 if (!pathkeys_contained_in(needed_pathkeys, current_pathkeys))
2637 if (list_length(root->distinct_pathkeys) >=
2638 list_length(root->sort_pathkeys))
2639 current_pathkeys = root->distinct_pathkeys;
2641 current_pathkeys = root->sort_pathkeys;
2642 cost_sort(&sorted_p, root, current_pathkeys, sorted_p.total_cost,
2643 path_rows, path_width,
2644 0.0, work_mem, -1.0);
2646 cost_group(&sorted_p, root, numDistinctCols, dNumDistinctRows,
2647 sorted_p.startup_cost, sorted_p.total_cost,
2649 if (parse->sortClause &&
2650 !pathkeys_contained_in(root->sort_pathkeys, current_pathkeys))
2651 cost_sort(&sorted_p, root, root->sort_pathkeys, sorted_p.total_cost,
2652 dNumDistinctRows, path_width,
2653 0.0, work_mem, limit_tuples);
2656 * Now make the decision using the top-level tuple fraction. First we
2657 * have to convert an absolute count (LIMIT) into fractional form.
2659 if (tuple_fraction >= 1.0)
2660 tuple_fraction /= dNumDistinctRows;
2662 if (compare_fractional_path_costs(&hashed_p, &sorted_p,
2663 tuple_fraction) < 0)
2665 /* Hashed is cheaper, so use it */
2672 * make_subplanTargetList
2673 * Generate appropriate target list when grouping is required.
2675 * When grouping_planner inserts grouping or aggregation plan nodes
2676 * above the scan/join plan constructed by query_planner+create_plan,
2677 * we typically want the scan/join plan to emit a different target list
2678 * than the outer plan nodes should have. This routine generates the
2679 * correct target list for the scan/join subplan.
2681 * The initial target list passed from the parser already contains entries
2682 * for all ORDER BY and GROUP BY expressions, but it will not have entries
2683 * for variables used only in HAVING clauses; so we need to add those
2684 * variables to the subplan target list. Also, we flatten all expressions
2685 * except GROUP BY items into their component variables; the other expressions
2686 * will be computed by the inserted nodes rather than by the subplan.
2687 * For example, given a query like
2688 * SELECT a+b,SUM(c+d) FROM table GROUP BY a+b;
2689 * we want to pass this targetlist to the subplan:
2691 * where the a+b target will be used by the Sort/Group steps, and the
2692 * other targets will be used for computing the final results.
2694 * If we are grouping or aggregating, *and* there are no non-Var grouping
2695 * expressions, then the returned tlist is effectively dummy; we do not
2696 * need to force it to be evaluated, because all the Vars it contains
2697 * should be present in the "flat" tlist generated by create_plan, though
2698 * possibly in a different order. In that case we'll use create_plan's tlist,
2699 * and the tlist made here is only needed as input to query_planner to tell
2700 * it which Vars are needed in the output of the scan/join plan.
2702 * 'tlist' is the query's target list.
2703 * 'groupColIdx' receives an array of column numbers for the GROUP BY
2704 * expressions (if there are any) in the returned target list.
2705 * 'need_tlist_eval' is set true if we really need to evaluate the
2706 * returned tlist as-is.
2708 * The result is the targetlist to be passed to query_planner.
2711 make_subplanTargetList(PlannerInfo *root,
2713 AttrNumber **groupColIdx,
2714 bool *need_tlist_eval)
2716 Query *parse = root->parse;
2718 List *non_group_cols;
2719 List *non_group_vars;
2722 *groupColIdx = NULL;
2725 * If we're not grouping or aggregating, there's nothing to do here;
2726 * query_planner should receive the unmodified target list.
2728 if (!parse->hasAggs && !parse->groupClause && !root->hasHavingQual &&
2729 !parse->hasWindowFuncs)
2731 *need_tlist_eval = true;
2736 * Otherwise, we must build a tlist containing all grouping columns, plus
2737 * any other Vars mentioned in the targetlist and HAVING qual.
2740 non_group_cols = NIL;
2741 *need_tlist_eval = false; /* only eval if not flat tlist */
2743 numCols = list_length(parse->groupClause);
2747 * If grouping, create sub_tlist entries for all GROUP BY columns, and
2748 * make an array showing where the group columns are in the sub_tlist.
2750 * Note: with this implementation, the array entries will always be
2751 * 1..N, but we don't want callers to assume that.
2753 AttrNumber *grpColIdx;
2756 grpColIdx = (AttrNumber *) palloc0(sizeof(AttrNumber) * numCols);
2757 *groupColIdx = grpColIdx;
2761 TargetEntry *tle = (TargetEntry *) lfirst(tl);
2764 colno = get_grouping_column_index(parse, tle);
2768 * It's a grouping column, so add it to the result tlist and
2769 * remember its resno in grpColIdx[].
2771 TargetEntry *newtle;
2773 newtle = makeTargetEntry(tle->expr,
2774 list_length(sub_tlist) + 1,
2777 sub_tlist = lappend(sub_tlist, newtle);
2779 Assert(grpColIdx[colno] == 0); /* no dups expected */
2780 grpColIdx[colno] = newtle->resno;
2782 if (!(newtle->expr && IsA(newtle->expr, Var)))
2783 *need_tlist_eval = true; /* tlist contains non Vars */
2788 * Non-grouping column, so just remember the expression for
2789 * later call to pull_var_clause. There's no need for
2790 * pull_var_clause to examine the TargetEntry node itself.
2792 non_group_cols = lappend(non_group_cols, tle->expr);
2799 * With no grouping columns, just pass whole tlist to pull_var_clause.
2800 * Need (shallow) copy to avoid damaging input tlist below.
2802 non_group_cols = list_copy(tlist);
2806 * If there's a HAVING clause, we'll need the Vars it uses, too.
2808 if (parse->havingQual)
2809 non_group_cols = lappend(non_group_cols, parse->havingQual);
2812 * Pull out all the Vars mentioned in non-group cols (plus HAVING), and
2813 * add them to the result tlist if not already present. (A Var used
2814 * directly as a GROUP BY item will be present already.) Note this
2815 * includes Vars used in resjunk items, so we are covering the needs of
2816 * ORDER BY and window specifications. Vars used within Aggrefs will be
2817 * pulled out here, too.
2819 non_group_vars = pull_var_clause((Node *) non_group_cols,
2820 PVC_RECURSE_AGGREGATES,
2821 PVC_INCLUDE_PLACEHOLDERS);
2822 sub_tlist = add_to_flat_tlist(sub_tlist, non_group_vars);
2824 /* clean up cruft */
2825 list_free(non_group_vars);
2826 list_free(non_group_cols);
2832 * get_grouping_column_index
2833 * Get the GROUP BY column position, if any, of a targetlist entry.
2835 * Returns the index (counting from 0) of the TLE in the GROUP BY list, or -1
2836 * if it's not a grouping column. Note: the result is unique because the
2837 * parser won't make multiple groupClause entries for the same TLE.
2840 get_grouping_column_index(Query *parse, TargetEntry *tle)
2843 Index ressortgroupref = tle->ressortgroupref;
2846 /* No need to search groupClause if TLE hasn't got a sortgroupref */
2847 if (ressortgroupref == 0)
2850 foreach(gl, parse->groupClause)
2852 SortGroupClause *grpcl = (SortGroupClause *) lfirst(gl);
2854 if (grpcl->tleSortGroupRef == ressortgroupref)
2863 * locate_grouping_columns
2864 * Locate grouping columns in the tlist chosen by create_plan.
2866 * This is only needed if we don't use the sub_tlist chosen by
2867 * make_subplanTargetList. We have to forget the column indexes found
2868 * by that routine and re-locate the grouping exprs in the real sub_tlist.
2871 locate_grouping_columns(PlannerInfo *root,
2874 AttrNumber *groupColIdx)
2880 * No work unless grouping.
2882 if (!root->parse->groupClause)
2884 Assert(groupColIdx == NULL);
2887 Assert(groupColIdx != NULL);
2889 foreach(gl, root->parse->groupClause)
2891 SortGroupClause *grpcl = (SortGroupClause *) lfirst(gl);
2892 Node *groupexpr = get_sortgroupclause_expr(grpcl, tlist);
2893 TargetEntry *te = tlist_member(groupexpr, sub_tlist);
2896 elog(ERROR, "failed to locate grouping columns");
2897 groupColIdx[keyno++] = te->resno;
2902 * postprocess_setop_tlist
2903 * Fix up targetlist returned by plan_set_operations().
2905 * We need to transpose sort key info from the orig_tlist into new_tlist.
2906 * NOTE: this would not be good enough if we supported resjunk sort keys
2907 * for results of set operations --- then, we'd need to project a whole
2908 * new tlist to evaluate the resjunk columns. For now, just ereport if we
2909 * find any resjunk columns in orig_tlist.
2912 postprocess_setop_tlist(List *new_tlist, List *orig_tlist)
2915 ListCell *orig_tlist_item = list_head(orig_tlist);
2917 foreach(l, new_tlist)
2919 TargetEntry *new_tle = (TargetEntry *) lfirst(l);
2920 TargetEntry *orig_tle;
2922 /* ignore resjunk columns in setop result */
2923 if (new_tle->resjunk)
2926 Assert(orig_tlist_item != NULL);
2927 orig_tle = (TargetEntry *) lfirst(orig_tlist_item);
2928 orig_tlist_item = lnext(orig_tlist_item);
2929 if (orig_tle->resjunk) /* should not happen */
2930 elog(ERROR, "resjunk output columns are not implemented");
2931 Assert(new_tle->resno == orig_tle->resno);
2932 new_tle->ressortgroupref = orig_tle->ressortgroupref;
2934 if (orig_tlist_item != NULL)
2935 elog(ERROR, "resjunk output columns are not implemented");
2940 * select_active_windows
2941 * Create a list of the "active" window clauses (ie, those referenced
2942 * by non-deleted WindowFuncs) in the order they are to be executed.
2945 select_active_windows(PlannerInfo *root, WindowFuncLists *wflists)
2951 /* First, make a list of the active windows */
2953 foreach(lc, root->parse->windowClause)
2955 WindowClause *wc = (WindowClause *) lfirst(lc);
2957 /* It's only active if wflists shows some related WindowFuncs */
2958 Assert(wc->winref <= wflists->maxWinRef);
2959 if (wflists->windowFuncs[wc->winref] != NIL)
2960 actives = lappend(actives, wc);
2964 * Now, ensure that windows with identical partitioning/ordering clauses
2965 * are adjacent in the list. This is required by the SQL standard, which
2966 * says that only one sort is to be used for such windows, even if they
2967 * are otherwise distinct (eg, different names or framing clauses).
2969 * There is room to be much smarter here, for example detecting whether
2970 * one window's sort keys are a prefix of another's (so that sorting for
2971 * the latter would do for the former), or putting windows first that
2972 * match a sort order available for the underlying query. For the moment
2973 * we are content with meeting the spec.
2976 while (actives != NIL)
2978 WindowClause *wc = (WindowClause *) linitial(actives);
2982 /* Move wc from actives to result */
2983 actives = list_delete_first(actives);
2984 result = lappend(result, wc);
2986 /* Now move any matching windows from actives to result */
2988 for (lc = list_head(actives); lc; lc = next)
2990 WindowClause *wc2 = (WindowClause *) lfirst(lc);
2993 /* framing options are NOT to be compared here! */
2994 if (equal(wc->partitionClause, wc2->partitionClause) &&
2995 equal(wc->orderClause, wc2->orderClause))
2997 actives = list_delete_cell(actives, lc, prev);
2998 result = lappend(result, wc2);
3009 * add_volatile_sort_exprs
3010 * Identify any volatile sort/group expressions used by the active
3011 * windows, and add them to window_tlist if not already present.
3012 * Return the modified window_tlist.
3015 add_volatile_sort_exprs(List *window_tlist, List *tlist, List *activeWindows)
3017 Bitmapset *sgrefs = NULL;
3020 /* First, collect the sortgrouprefs of the windows into a bitmapset */
3021 foreach(lc, activeWindows)
3023 WindowClause *wc = (WindowClause *) lfirst(lc);
3026 foreach(lc2, wc->partitionClause)
3028 SortGroupClause *sortcl = (SortGroupClause *) lfirst(lc2);
3030 sgrefs = bms_add_member(sgrefs, sortcl->tleSortGroupRef);
3032 foreach(lc2, wc->orderClause)
3034 SortGroupClause *sortcl = (SortGroupClause *) lfirst(lc2);
3036 sgrefs = bms_add_member(sgrefs, sortcl->tleSortGroupRef);
3041 * Now scan the original tlist to find the referenced expressions. Any
3042 * that are volatile must be added to window_tlist.
3044 * Note: we know that the input window_tlist contains no items marked with
3045 * ressortgrouprefs, so we don't have to worry about collisions of the
3046 * reference numbers.
3050 TargetEntry *tle = (TargetEntry *) lfirst(lc);
3052 if (tle->ressortgroupref != 0 &&
3053 bms_is_member(tle->ressortgroupref, sgrefs) &&
3054 contain_volatile_functions((Node *) tle->expr))
3056 TargetEntry *newtle;
3058 newtle = makeTargetEntry(tle->expr,
3059 list_length(window_tlist) + 1,
3062 newtle->ressortgroupref = tle->ressortgroupref;
3063 window_tlist = lappend(window_tlist, newtle);
3067 return window_tlist;
3071 * make_pathkeys_for_window
3072 * Create a pathkeys list describing the required input ordering
3073 * for the given WindowClause.
3075 * The required ordering is first the PARTITION keys, then the ORDER keys.
3076 * In the future we might try to implement windowing using hashing, in which
3077 * case the ordering could be relaxed, but for now we always sort.
3080 make_pathkeys_for_window(PlannerInfo *root, WindowClause *wc,
3081 List *tlist, bool canonicalize)
3083 List *window_pathkeys;
3084 List *window_sortclauses;
3086 /* Throw error if can't sort */
3087 if (!grouping_is_sortable(wc->partitionClause))
3089 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
3090 errmsg("could not implement window PARTITION BY"),
3091 errdetail("Window partitioning columns must be of sortable datatypes.")));
3092 if (!grouping_is_sortable(wc->orderClause))
3094 (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
3095 errmsg("could not implement window ORDER BY"),
3096 errdetail("Window ordering columns must be of sortable datatypes.")));
3098 /* Okay, make the combined pathkeys */
3099 window_sortclauses = list_concat(list_copy(wc->partitionClause),
3100 list_copy(wc->orderClause));
3101 window_pathkeys = make_pathkeys_for_sortclauses(root,
3105 list_free(window_sortclauses);
3106 return window_pathkeys;
3110 * get_column_info_for_window
3111 * Get the partitioning/ordering column numbers and equality operators
3112 * for a WindowAgg node.
3114 * This depends on the behavior of make_pathkeys_for_window()!
3116 * We are given the target WindowClause and an array of the input column
3117 * numbers associated with the resulting pathkeys. In the easy case, there
3118 * are the same number of pathkey columns as partitioning + ordering columns
3119 * and we just have to copy some data around. However, it's possible that
3120 * some of the original partitioning + ordering columns were eliminated as
3121 * redundant during the transformation to pathkeys. (This can happen even
3122 * though the parser gets rid of obvious duplicates. A typical scenario is a
3123 * window specification "PARTITION BY x ORDER BY y" coupled with a clause
3124 * "WHERE x = y" that causes the two sort columns to be recognized as
3125 * redundant.) In that unusual case, we have to work a lot harder to
3126 * determine which keys are significant.
3128 * The method used here is a bit brute-force: add the sort columns to a list
3129 * one at a time and note when the resulting pathkey list gets longer. But
3130 * it's a sufficiently uncommon case that a faster way doesn't seem worth
3131 * the amount of code refactoring that'd be needed.
3135 get_column_info_for_window(PlannerInfo *root, WindowClause *wc, List *tlist,
3136 int numSortCols, AttrNumber *sortColIdx,
3138 AttrNumber **partColIdx,
3139 Oid **partOperators,
3141 AttrNumber **ordColIdx,
3144 int numPart = list_length(wc->partitionClause);
3145 int numOrder = list_length(wc->orderClause);
3147 if (numSortCols == numPart + numOrder)
3150 *partNumCols = numPart;
3151 *partColIdx = sortColIdx;
3152 *partOperators = extract_grouping_ops(wc->partitionClause);
3153 *ordNumCols = numOrder;
3154 *ordColIdx = sortColIdx + numPart;
3155 *ordOperators = extract_grouping_ops(wc->orderClause);
3164 /* first, allocate what's certainly enough space for the arrays */
3166 *partColIdx = (AttrNumber *) palloc(numPart * sizeof(AttrNumber));
3167 *partOperators = (Oid *) palloc(numPart * sizeof(Oid));
3169 *ordColIdx = (AttrNumber *) palloc(numOrder * sizeof(AttrNumber));
3170 *ordOperators = (Oid *) palloc(numOrder * sizeof(Oid));
3174 foreach(lc, wc->partitionClause)
3176 SortGroupClause *sgc = (SortGroupClause *) lfirst(lc);
3179 sortclauses = lappend(sortclauses, sgc);
3180 new_pathkeys = make_pathkeys_for_sortclauses(root,
3184 if (list_length(new_pathkeys) > list_length(pathkeys))
3186 /* this sort clause is actually significant */
3187 (*partColIdx)[*partNumCols] = sortColIdx[scidx++];
3188 (*partOperators)[*partNumCols] = sgc->eqop;
3190 pathkeys = new_pathkeys;
3193 foreach(lc, wc->orderClause)
3195 SortGroupClause *sgc = (SortGroupClause *) lfirst(lc);
3198 sortclauses = lappend(sortclauses, sgc);
3199 new_pathkeys = make_pathkeys_for_sortclauses(root,
3203 if (list_length(new_pathkeys) > list_length(pathkeys))
3205 /* this sort clause is actually significant */
3206 (*ordColIdx)[*ordNumCols] = sortColIdx[scidx++];
3207 (*ordOperators)[*ordNumCols] = sgc->eqop;
3209 pathkeys = new_pathkeys;
3212 /* complain if we didn't eat exactly the right number of sort cols */
3213 if (scidx != numSortCols)
3214 elog(ERROR, "failed to deconstruct sort operators into partitioning/ordering operators");
3220 * expression_planner
3221 * Perform planner's transformations on a standalone expression.
3223 * Various utility commands need to evaluate expressions that are not part
3224 * of a plannable query. They can do so using the executor's regular
3225 * expression-execution machinery, but first the expression has to be fed
3226 * through here to transform it from parser output to something executable.
3228 * Currently, we disallow sublinks in standalone expressions, so there's no
3229 * real "planning" involved here. (That might not always be true though.)
3230 * What we must do is run eval_const_expressions to ensure that any function
3231 * calls are converted to positional notation and function default arguments
3232 * get inserted. The fact that constant subexpressions get simplified is a
3233 * side-effect that is useful when the expression will get evaluated more than
3234 * once. Also, we must fix operator function IDs.
3236 * Note: this must not make any damaging changes to the passed-in expression
3237 * tree. (It would actually be okay to apply fix_opfuncids to it, but since
3238 * we first do an expression_tree_mutator-based walk, what is returned will
3239 * be a new node tree.)
3242 expression_planner(Expr *expr)
3247 * Convert named-argument function calls, insert default arguments and
3248 * simplify constant subexprs
3250 result = eval_const_expressions(NULL, (Node *) expr);
3252 /* Fill in opfuncid values if missing */
3253 fix_opfuncids(result);
3255 return (Expr *) result;
3260 * plan_cluster_use_sort
3261 * Use the planner to decide how CLUSTER should implement sorting
3263 * tableOid is the OID of a table to be clustered on its index indexOid
3264 * (which is already known to be a btree index). Decide whether it's
3265 * cheaper to do an indexscan or a seqscan-plus-sort to execute the CLUSTER.
3266 * Return TRUE to use sorting, FALSE to use an indexscan.
3268 * Note: caller had better already hold some type of lock on the table.
3271 plan_cluster_use_sort(Oid tableOid, Oid indexOid)
3275 PlannerGlobal *glob;
3278 IndexOptInfo *indexInfo;
3279 QualCost indexExprCost;
3280 Cost comparisonCost;
3282 Path seqScanAndSortPath;
3283 IndexPath *indexScanPath;
3286 /* Set up mostly-dummy planner state */
3287 query = makeNode(Query);
3288 query->commandType = CMD_SELECT;
3290 glob = makeNode(PlannerGlobal);
3292 root = makeNode(PlannerInfo);
3293 root->parse = query;
3295 root->query_level = 1;
3296 root->planner_cxt = CurrentMemoryContext;
3297 root->wt_param_id = -1;
3299 /* Build a minimal RTE for the rel */
3300 rte = makeNode(RangeTblEntry);
3301 rte->rtekind = RTE_RELATION;
3302 rte->relid = tableOid;
3303 rte->relkind = RELKIND_RELATION;
3304 rte->lateral = false;
3306 rte->inFromCl = true;
3307 query->rtable = list_make1(rte);
3309 /* Set up RTE/RelOptInfo arrays */
3310 setup_simple_rel_arrays(root);
3312 /* Build RelOptInfo */
3313 rel = build_simple_rel(root, 1, RELOPT_BASEREL);
3315 /* Locate IndexOptInfo for the target index */
3317 foreach(lc, rel->indexlist)
3319 indexInfo = (IndexOptInfo *) lfirst(lc);
3320 if (indexInfo->indexoid == indexOid)
3325 * It's possible that get_relation_info did not generate an IndexOptInfo
3326 * for the desired index; this could happen if it's not yet reached its
3327 * indcheckxmin usability horizon, or if it's a system index and we're
3328 * ignoring system indexes. In such cases we should tell CLUSTER to not
3329 * trust the index contents but use seqscan-and-sort.
3331 if (lc == NULL) /* not in the list? */
3332 return true; /* use sort */
3335 * Rather than doing all the pushups that would be needed to use
3336 * set_baserel_size_estimates, just do a quick hack for rows and width.
3338 rel->rows = rel->tuples;
3339 rel->width = get_relation_data_width(tableOid, NULL);
3341 root->total_table_pages = rel->pages;
3344 * Determine eval cost of the index expressions, if any. We need to
3345 * charge twice that amount for each tuple comparison that happens during
3346 * the sort, since tuplesort.c will have to re-evaluate the index
3347 * expressions each time. (XXX that's pretty inefficient...)
3349 cost_qual_eval(&indexExprCost, indexInfo->indexprs, root);
3350 comparisonCost = 2.0 * (indexExprCost.startup + indexExprCost.per_tuple);
3352 /* Estimate the cost of seq scan + sort */
3353 seqScanPath = create_seqscan_path(root, rel, NULL);
3354 cost_sort(&seqScanAndSortPath, root, NIL,
3355 seqScanPath->total_cost, rel->tuples, rel->width,
3356 comparisonCost, maintenance_work_mem, -1.0);
3358 /* Estimate the cost of index scan */
3359 indexScanPath = create_index_path(root, indexInfo,
3360 NIL, NIL, NIL, NIL, NIL,
3361 ForwardScanDirection, false,
3364 return (seqScanAndSortPath.total_cost < indexScanPath->path.total_cost);
projects / postgresql / blob