planner.c

/*-------------------------------------------------------------------------
 *
 * planner.c
 *	  The query optimizer external interface.
 *
 * Portions Copyright (c) 1996-2015, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/optimizer/plan/planner.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include <limits.h>
#include <math.h>

#include "access/htup_details.h"
#include "executor/executor.h"
#include "executor/nodeAgg.h"
#include "foreign/fdwapi.h"
#include "miscadmin.h"
#include "lib/bipartite_match.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#ifdef OPTIMIZER_DEBUG
#include "nodes/print.h"
#endif
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
#include "optimizer/plancat.h"
#include "optimizer/planmain.h"
#include "optimizer/planner.h"
#include "optimizer/prep.h"
#include "optimizer/subselect.h"
#include "optimizer/tlist.h"
#include "parser/analyze.h"
#include "parser/parsetree.h"
#include "parser/parse_agg.h"
#include "rewrite/rewriteManip.h"
#include "utils/rel.h"
#include "utils/selfuncs.h"


/* GUC parameter */
double		cursor_tuple_fraction = DEFAULT_CURSOR_TUPLE_FRACTION;

/* Hook for plugins to get control in planner() */
planner_hook_type planner_hook = NULL;


/* Expression kind codes for preprocess_expression */
#define EXPRKIND_QUAL			0
#define EXPRKIND_TARGET			1
#define EXPRKIND_RTFUNC			2
#define EXPRKIND_RTFUNC_LATERAL 3
#define EXPRKIND_VALUES			4
#define EXPRKIND_VALUES_LATERAL 5
#define EXPRKIND_LIMIT			6
#define EXPRKIND_APPINFO		7
#define EXPRKIND_PHV			8
#define EXPRKIND_TABLESAMPLE	9

/* Passthrough data for standard_qp_callback */
typedef struct
{
	List	   *tlist;			/* preprocessed query targetlist */
	List	   *activeWindows;	/* active windows, if any */
	List	   *groupClause;	/* overrides parse->groupClause */
} standard_qp_extra;

/* Local functions */
static Node *preprocess_expression(PlannerInfo *root, Node *expr, int kind);
static void preprocess_qual_conditions(PlannerInfo *root, Node *jtnode);
static Plan *inheritance_planner(PlannerInfo *root);
static Plan *grouping_planner(PlannerInfo *root, double tuple_fraction);
static void preprocess_rowmarks(PlannerInfo *root);
static double preprocess_limit(PlannerInfo *root,
				 double tuple_fraction,
				 int64 *offset_est, int64 *count_est);
static bool limit_needed(Query *parse);
static List *preprocess_groupclause(PlannerInfo *root, List *force);
static List *extract_rollup_sets(List *groupingSets);
static List *reorder_grouping_sets(List *groupingSets, List *sortclause);
static void standard_qp_callback(PlannerInfo *root, void *extra);
static bool choose_hashed_grouping(PlannerInfo *root,
					   double tuple_fraction, double limit_tuples,
					   double path_rows, int path_width,
					   Path *cheapest_path, Path *sorted_path,
					   double dNumGroups, AggClauseCosts *agg_costs);
static bool choose_hashed_distinct(PlannerInfo *root,
					   double tuple_fraction, double limit_tuples,
					   double path_rows, int path_width,
					   Cost cheapest_startup_cost, Cost cheapest_total_cost,
					   Cost sorted_startup_cost, Cost sorted_total_cost,
					   List *sorted_pathkeys,
					   double dNumDistinctRows);
static List *make_subplanTargetList(PlannerInfo *root, List *tlist,
					   AttrNumber **groupColIdx, bool *need_tlist_eval);
static int	get_grouping_column_index(Query *parse, TargetEntry *tle);
static void locate_grouping_columns(PlannerInfo *root,
						List *tlist,
						List *sub_tlist,
						AttrNumber *groupColIdx);
static List *postprocess_setop_tlist(List *new_tlist, List *orig_tlist);
static List *select_active_windows(PlannerInfo *root, WindowFuncLists *wflists);
static List *make_windowInputTargetList(PlannerInfo *root,
						   List *tlist, List *activeWindows);
static List *make_pathkeys_for_window(PlannerInfo *root, WindowClause *wc,
						 List *tlist);
static void get_column_info_for_window(PlannerInfo *root, WindowClause *wc,
						   List *tlist,
						   int numSortCols, AttrNumber *sortColIdx,
						   int *partNumCols,
						   AttrNumber **partColIdx,
						   Oid **partOperators,
						   int *ordNumCols,
						   AttrNumber **ordColIdx,
						   Oid **ordOperators);
static Plan *build_grouping_chain(PlannerInfo *root,
					 Query *parse,
					 List *tlist,
					 bool need_sort_for_grouping,
					 List *rollup_groupclauses,
					 List *rollup_lists,
					 AttrNumber *groupColIdx,
					 AggClauseCosts *agg_costs,
					 long numGroups,
					 Plan *result_plan);

/*****************************************************************************
 *
 *	   Query optimizer entry point
 *
 * To support loadable plugins that monitor or modify planner behavior,
 * we provide a hook variable that lets a plugin get control before and
 * after the standard planning process.  The plugin would normally call
 * standard_planner().
 *
 * Note to plugin authors: standard_planner() scribbles on its Query input,
 * so you'd better copy that data structure if you want to plan more than once.
 *
 *****************************************************************************/
PlannedStmt *
planner(Query *parse, int cursorOptions, ParamListInfo boundParams)
{
	PlannedStmt *result;

	if (planner_hook)
		result = (*planner_hook) (parse, cursorOptions, boundParams);
	else
		result = standard_planner(parse, cursorOptions, boundParams);
	return result;
}

PlannedStmt *
standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams)
{
	PlannedStmt *result;
	PlannerGlobal *glob;
	double		tuple_fraction;
	PlannerInfo *root;
	Plan	   *top_plan;
	ListCell   *lp,
			   *lr;

	/* Cursor options may come from caller or from DECLARE CURSOR stmt */
	if (parse->utilityStmt &&
		IsA(parse->utilityStmt, DeclareCursorStmt))
		cursorOptions |= ((DeclareCursorStmt *) parse->utilityStmt)->options;

	/*
	 * Set up global state for this planner invocation.  This data is needed
	 * across all levels of sub-Query that might exist in the given command,
	 * so we keep it in a separate struct that's linked to by each per-Query
	 * PlannerInfo.
	 */
	glob = makeNode(PlannerGlobal);

	glob->boundParams = boundParams;
	glob->subplans = NIL;
	glob->subroots = NIL;
	glob->rewindPlanIDs = NULL;
	glob->finalrtable = NIL;
	glob->finalrowmarks = NIL;
	glob->resultRelations = NIL;
	glob->relationOids = NIL;
	glob->invalItems = NIL;
	glob->nParamExec = 0;
	glob->lastPHId = 0;
	glob->lastRowMarkId = 0;
	glob->transientPlan = false;
	glob->hasRowSecurity = false;

	/* Determine what fraction of the plan is likely to be scanned */
	if (cursorOptions & CURSOR_OPT_FAST_PLAN)
	{
		/*
		 * We have no real idea how many tuples the user will ultimately FETCH
		 * from a cursor, but it is often the case that he doesn't want 'em
		 * all, or would prefer a fast-start plan anyway so that he can
		 * process some of the tuples sooner.  Use a GUC parameter to decide
		 * what fraction to optimize for.
		 */
		tuple_fraction = cursor_tuple_fraction;

		/*
		 * We document cursor_tuple_fraction as simply being a fraction, which
		 * means the edge cases 0 and 1 have to be treated specially here.  We
		 * convert 1 to 0 ("all the tuples") and 0 to a very small fraction.
		 */
		if (tuple_fraction >= 1.0)
			tuple_fraction = 0.0;
		else if (tuple_fraction <= 0.0)
			tuple_fraction = 1e-10;
	}
	else
	{
		/* Default assumption is we need all the tuples */
		tuple_fraction = 0.0;
	}

	/* primary planning entry point (may recurse for subqueries) */
	top_plan = subquery_planner(glob, parse, NULL,
								false, tuple_fraction, &root);

	/*
	 * If creating a plan for a scrollable cursor, make sure it can run
	 * backwards on demand.  Add a Material node at the top at need.
	 */
	if (cursorOptions & CURSOR_OPT_SCROLL)
	{
		if (!ExecSupportsBackwardScan(top_plan))
			top_plan = materialize_finished_plan(top_plan);
	}

	/* final cleanup of the plan */
	Assert(glob->finalrtable == NIL);
	Assert(glob->finalrowmarks == NIL);
	Assert(glob->resultRelations == NIL);
	top_plan = set_plan_references(root, top_plan);
	/* ... and the subplans (both regular subplans and initplans) */
	Assert(list_length(glob->subplans) == list_length(glob->subroots));
	forboth(lp, glob->subplans, lr, glob->subroots)
	{
		Plan	   *subplan = (Plan *) lfirst(lp);
		PlannerInfo *subroot = (PlannerInfo *) lfirst(lr);

		lfirst(lp) = set_plan_references(subroot, subplan);
	}

	/* build the PlannedStmt result */
	result = makeNode(PlannedStmt);

	result->commandType = parse->commandType;
	result->queryId = parse->queryId;
	result->hasReturning = (parse->returningList != NIL);
	result->hasModifyingCTE = parse->hasModifyingCTE;
	result->canSetTag = parse->canSetTag;
	result->transientPlan = glob->transientPlan;
	result->planTree = top_plan;
	result->rtable = glob->finalrtable;
	result->resultRelations = glob->resultRelations;
	result->utilityStmt = parse->utilityStmt;
	result->subplans = glob->subplans;
	result->rewindPlanIDs = glob->rewindPlanIDs;
	result->rowMarks = glob->finalrowmarks;
	result->relationOids = glob->relationOids;
	result->invalItems = glob->invalItems;
	result->nParamExec = glob->nParamExec;
	result->hasRowSecurity = glob->hasRowSecurity;

	return result;
}


/*--------------------
 * subquery_planner
 *	  Invokes the planner on a subquery.  We recurse to here for each
 *	  sub-SELECT found in the query tree.
 *
 * glob is the global state for the current planner run.
 * parse is the querytree produced by the parser & rewriter.
 * parent_root is the immediate parent Query's info (NULL at the top level).
 * hasRecursion is true if this is a recursive WITH query.
 * tuple_fraction is the fraction of tuples we expect will be retrieved.
 * tuple_fraction is interpreted as explained for grouping_planner, below.
 *
 * If subroot isn't NULL, we pass back the query's final PlannerInfo struct;
 * among other things this tells the output sort ordering of the plan.
 *
 * Basically, this routine does the stuff that should only be done once
 * per Query object.  It then calls grouping_planner.  At one time,
 * grouping_planner could be invoked recursively on the same Query object;
 * that's not currently true, but we keep the separation between the two
 * routines anyway, in case we need it again someday.
 *
 * subquery_planner will be called recursively to handle sub-Query nodes
 * found within the query's expressions and rangetable.
 *
 * Returns a query plan.
 *--------------------
 */
Plan *
subquery_planner(PlannerGlobal *glob, Query *parse,
				 PlannerInfo *parent_root,
				 bool hasRecursion, double tuple_fraction,
				 PlannerInfo **subroot)
{
	int			num_old_subplans = list_length(glob->subplans);
	PlannerInfo *root;
	Plan	   *plan;
	List	   *newWithCheckOptions;
	List	   *newHaving;
	bool		hasOuterJoins;
	ListCell   *l;

	/* Create a PlannerInfo data structure for this subquery */
	root = makeNode(PlannerInfo);
	root->parse = parse;
	root->glob = glob;
	root->query_level = parent_root ? parent_root->query_level + 1 : 1;
	root->parent_root = parent_root;
	root->plan_params = NIL;
	root->planner_cxt = CurrentMemoryContext;
	root->init_plans = NIL;
	root->cte_plan_ids = NIL;
	root->multiexpr_params = NIL;
	root->eq_classes = NIL;
	root->append_rel_list = NIL;
	root->rowMarks = NIL;
	root->hasInheritedTarget = false;
	root->grouping_map = NULL;

	root->hasRecursion = hasRecursion;
	if (hasRecursion)
		root->wt_param_id = SS_assign_special_param(root);
	else
		root->wt_param_id = -1;
	root->non_recursive_plan = NULL;

	/*
	 * If there is a WITH list, process each WITH query and build an initplan
	 * SubPlan structure for it.
	 */
	if (parse->cteList)
		SS_process_ctes(root);

	/*
	 * Look for ANY and EXISTS SubLinks in WHERE and JOIN/ON clauses, and try
	 * to transform them into joins.  Note that this step does not descend
	 * into subqueries; if we pull up any subqueries below, their SubLinks are
	 * processed just before pulling them up.
	 */
	if (parse->hasSubLinks)
		pull_up_sublinks(root);

	/*
	 * Scan the rangetable for set-returning functions, and inline them if
	 * possible (producing subqueries that might get pulled up next).
	 * Recursion issues here are handled in the same way as for SubLinks.
	 */
	inline_set_returning_functions(root);

	/*
	 * Check to see if any subqueries in the jointree can be merged into this
	 * query.
	 */
	pull_up_subqueries(root);

	/*
	 * If this is a simple UNION ALL query, flatten it into an appendrel. We
	 * do this now because it requires applying pull_up_subqueries to the leaf
	 * queries of the UNION ALL, which weren't touched above because they
	 * weren't referenced by the jointree (they will be after we do this).
	 */
	if (parse->setOperations)
		flatten_simple_union_all(root);

	/*
	 * Detect whether any rangetable entries are RTE_JOIN kind; if not, we can
	 * avoid the expense of doing flatten_join_alias_vars().  Also check for
	 * outer joins --- if none, we can skip reduce_outer_joins().  And check
	 * for LATERAL RTEs, too.  This must be done after we have done
	 * pull_up_subqueries(), of course.
	 */
	root->hasJoinRTEs = false;
	root->hasLateralRTEs = false;
	hasOuterJoins = false;
	foreach(l, parse->rtable)
	{
		RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);

		if (rte->rtekind == RTE_JOIN)
		{
			root->hasJoinRTEs = true;
			if (IS_OUTER_JOIN(rte->jointype))
				hasOuterJoins = true;
		}
		if (rte->lateral)
			root->hasLateralRTEs = true;
	}

	/*
	 * Preprocess RowMark information.  We need to do this after subquery
	 * pullup (so that all non-inherited RTEs are present) and before
	 * inheritance expansion (so that the info is available for
	 * expand_inherited_tables to examine and modify).
	 */
	preprocess_rowmarks(root);

	/*
	 * Expand any rangetable entries that are inheritance sets into "append
	 * relations".  This can add entries to the rangetable, but they must be
	 * plain base relations not joins, so it's OK (and marginally more
	 * efficient) to do it after checking for join RTEs.  We must do it after
	 * pulling up subqueries, else we'd fail to handle inherited tables in
	 * subqueries.
	 */
	expand_inherited_tables(root);

	/*
	 * Set hasHavingQual to remember if HAVING clause is present.  Needed
	 * because preprocess_expression will reduce a constant-true condition to
	 * an empty qual list ... but "HAVING TRUE" is not a semantic no-op.
	 */
	root->hasHavingQual = (parse->havingQual != NULL);

	/* Clear this flag; might get set in distribute_qual_to_rels */
	root->hasPseudoConstantQuals = false;

	/*
	 * Do expression preprocessing on targetlist and quals, as well as other
	 * random expressions in the querytree.  Note that we do not need to
	 * handle sort/group expressions explicitly, because they are actually
	 * part of the targetlist.
	 */
	parse->targetList = (List *)
		preprocess_expression(root, (Node *) parse->targetList,
							  EXPRKIND_TARGET);

	newWithCheckOptions = NIL;
	foreach(l, parse->withCheckOptions)
	{
		WithCheckOption *wco = (WithCheckOption *) lfirst(l);

		wco->qual = preprocess_expression(root, wco->qual,
										  EXPRKIND_QUAL);
		if (wco->qual != NULL)
			newWithCheckOptions = lappend(newWithCheckOptions, wco);
	}
	parse->withCheckOptions = newWithCheckOptions;

	parse->returningList = (List *)
		preprocess_expression(root, (Node *) parse->returningList,
							  EXPRKIND_TARGET);

	preprocess_qual_conditions(root, (Node *) parse->jointree);

	parse->havingQual = preprocess_expression(root, parse->havingQual,
											  EXPRKIND_QUAL);

	foreach(l, parse->windowClause)
	{
		WindowClause *wc = (WindowClause *) lfirst(l);

		/* partitionClause/orderClause are sort/group expressions */
		wc->startOffset = preprocess_expression(root, wc->startOffset,
												EXPRKIND_LIMIT);
		wc->endOffset = preprocess_expression(root, wc->endOffset,
											  EXPRKIND_LIMIT);
	}

	parse->limitOffset = preprocess_expression(root, parse->limitOffset,
											   EXPRKIND_LIMIT);
	parse->limitCount = preprocess_expression(root, parse->limitCount,
											  EXPRKIND_LIMIT);

	if (parse->onConflict)
	{
		parse->onConflict->onConflictSet = (List *)
			preprocess_expression(root, (Node *) parse->onConflict->onConflictSet,
								  EXPRKIND_TARGET);

		parse->onConflict->onConflictWhere =
			preprocess_expression(root, (Node *) parse->onConflict->onConflictWhere,
								  EXPRKIND_QUAL);
	}

	root->append_rel_list = (List *)
		preprocess_expression(root, (Node *) root->append_rel_list,
							  EXPRKIND_APPINFO);

	/* Also need to preprocess expressions within RTEs */
	foreach(l, parse->rtable)
	{
		RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
		int			kind;

		if (rte->rtekind == RTE_RELATION)
		{
			if (rte->tablesample)
			{
				rte->tablesample->args = (List *)
					preprocess_expression(root, (Node *) rte->tablesample->args,
										  EXPRKIND_TABLESAMPLE);
				rte->tablesample->repeatable = (Node *)
					preprocess_expression(root, rte->tablesample->repeatable,
										  EXPRKIND_TABLESAMPLE);
			}
		}
		else if (rte->rtekind == RTE_SUBQUERY)
		{
			/*
			 * We don't want to do all preprocessing yet on the subquery's
			 * expressions, since that will happen when we plan it.  But if it
			 * contains any join aliases of our level, those have to get
			 * expanded now, because planning of the subquery won't do it.
			 * That's only possible if the subquery is LATERAL.
			 */
			if (rte->lateral && root->hasJoinRTEs)
				rte->subquery = (Query *)
					flatten_join_alias_vars(root, (Node *) rte->subquery);
		}
		else if (rte->rtekind == RTE_FUNCTION)
		{
			/* Preprocess the function expression(s) fully */
			kind = rte->lateral ? EXPRKIND_RTFUNC_LATERAL : EXPRKIND_RTFUNC;
			rte->functions = (List *) preprocess_expression(root, (Node *) rte->functions, kind);
		}
		else if (rte->rtekind == RTE_VALUES)
		{
			/* Preprocess the values lists fully */
			kind = rte->lateral ? EXPRKIND_VALUES_LATERAL : EXPRKIND_VALUES;
			rte->values_lists = (List *)
				preprocess_expression(root, (Node *) rte->values_lists, kind);
		}
	}

	/*
	 * In some cases we may want to transfer a HAVING clause into WHERE. We
	 * cannot do so if the HAVING clause contains aggregates (obviously) or
	 * volatile functions (since a HAVING clause is supposed to be executed
	 * only once per group).  Also, it may be that the clause is so expensive
	 * to execute that we're better off doing it only once per group, despite
	 * the loss of selectivity.  This is hard to estimate short of doing the
	 * entire planning process twice, so we use a heuristic: clauses
	 * containing subplans are left in HAVING.  Otherwise, we move or copy the
	 * HAVING clause into WHERE, in hopes of eliminating tuples before
	 * aggregation instead of after.
	 *
	 * If the query has explicit grouping then we can simply move such a
	 * clause into WHERE; any group that fails the clause will not be in the
	 * output because none of its tuples will reach the grouping or
	 * aggregation stage.  Otherwise we must have a degenerate (variable-free)
	 * HAVING clause, which we put in WHERE so that query_planner() can use it
	 * in a gating Result node, but also keep in HAVING to ensure that we
	 * don't emit a bogus aggregated row. (This could be done better, but it
	 * seems not worth optimizing.)
	 *
	 * Note that both havingQual and parse->jointree->quals are in
	 * implicitly-ANDed-list form at this point, even though they are declared
	 * as Node *.
	 */
	newHaving = NIL;
	foreach(l, (List *) parse->havingQual)
	{
		Node	   *havingclause = (Node *) lfirst(l);

		if (contain_agg_clause(havingclause) ||
			contain_volatile_functions(havingclause) ||
			contain_subplans(havingclause) ||
			parse->groupingSets)
		{
			/* keep it in HAVING */
			newHaving = lappend(newHaving, havingclause);
		}
		else if (parse->groupClause)
		{
			/* move it to WHERE */
			parse->jointree->quals = (Node *)
				lappend((List *) parse->jointree->quals, havingclause);
		}
		else
		{
			/* put a copy in WHERE, keep it in HAVING */
			parse->jointree->quals = (Node *)
				lappend((List *) parse->jointree->quals,
						copyObject(havingclause));
			newHaving = lappend(newHaving, havingclause);
		}
	}
	parse->havingQual = (Node *) newHaving;

	/*
	 * If we have any outer joins, try to reduce them to plain inner joins.
	 * This step is most easily done after we've done expression
	 * preprocessing.
	 */
	if (hasOuterJoins)
		reduce_outer_joins(root);

	/*
	 * Do the main planning.  If we have an inherited target relation, that
	 * needs special processing, else go straight to grouping_planner.
	 */
	if (parse->resultRelation &&
		rt_fetch(parse->resultRelation, parse->rtable)->inh)
		plan = inheritance_planner(root);
	else
	{
		plan = grouping_planner(root, tuple_fraction);
		/* If it's not SELECT, we need a ModifyTable node */
		if (parse->commandType != CMD_SELECT)
		{
			List	   *withCheckOptionLists;
			List	   *returningLists;
			List	   *rowMarks;

			/*
			 * Set up the WITH CHECK OPTION and RETURNING lists-of-lists, if
			 * needed.
			 */
			if (parse->withCheckOptions)
				withCheckOptionLists = list_make1(parse->withCheckOptions);
			else
				withCheckOptionLists = NIL;

			if (parse->returningList)
				returningLists = list_make1(parse->returningList);
			else
				returningLists = NIL;

			/*
			 * If there was a FOR [KEY] UPDATE/SHARE clause, the LockRows node
			 * will have dealt with fetching non-locked marked rows, else we
			 * need to have ModifyTable do that.
			 */
			if (parse->rowMarks)
				rowMarks = NIL;
			else
				rowMarks = root->rowMarks;

			plan = (Plan *) make_modifytable(root,
											 parse->commandType,
											 parse->canSetTag,
											 parse->resultRelation,
									   list_make1_int(parse->resultRelation),
											 list_make1(plan),
											 withCheckOptionLists,
											 returningLists,
											 rowMarks,
											 parse->onConflict,
											 SS_assign_special_param(root));
		}
	}

	/*
	 * If any subplans were generated, or if there are any parameters to worry
	 * about, build initPlan list and extParam/allParam sets for plan nodes,
	 * and attach the initPlans to the top plan node.
	 */
	if (list_length(glob->subplans) != num_old_subplans ||
		root->glob->nParamExec > 0)
		SS_finalize_plan(root, plan, true);

	/* Return internal info if caller wants it */
	if (subroot)
		*subroot = root;

	return plan;
}

/*
 * preprocess_expression
 *		Do subquery_planner's preprocessing work for an expression,
 *		which can be a targetlist, a WHERE clause (including JOIN/ON
 *		conditions), a HAVING clause, or a few other things.
 */
static Node *
preprocess_expression(PlannerInfo *root, Node *expr, int kind)
{
	/*
	 * Fall out quickly if expression is empty.  This occurs often enough to
	 * be worth checking.  Note that null->null is the correct conversion for
	 * implicit-AND result format, too.
	 */
	if (expr == NULL)
		return NULL;

	/*
	 * If the query has any join RTEs, replace join alias variables with
	 * base-relation variables.  We must do this before sublink processing,
	 * else sublinks expanded out from join aliases would not get processed.
	 * We can skip it in non-lateral RTE functions and VALUES lists, however,
	 * since they can't contain any Vars of the current query level.
	 */
	if (root->hasJoinRTEs &&
		!(kind == EXPRKIND_RTFUNC || kind == EXPRKIND_VALUES))
		expr = flatten_join_alias_vars(root, expr);

	/*
	 * Simplify constant expressions.
	 *
	 * Note: an essential effect of this is to convert named-argument function
	 * calls to positional notation and insert the current actual values of
	 * any default arguments for functions.  To ensure that happens, we *must*
	 * process all expressions here.  Previous PG versions sometimes skipped
	 * const-simplification if it didn't seem worth the trouble, but we can't
	 * do that anymore.
	 *
	 * Note: this also flattens nested AND and OR expressions into N-argument
	 * form.  All processing of a qual expression after this point must be
	 * careful to maintain AND/OR flatness --- that is, do not generate a tree
	 * with AND directly under AND, nor OR directly under OR.
	 */
	expr = eval_const_expressions(root, expr);

	/*
	 * If it's a qual or havingQual, canonicalize it.
	 */
	if (kind == EXPRKIND_QUAL)
	{
		expr = (Node *) canonicalize_qual((Expr *) expr);

#ifdef OPTIMIZER_DEBUG
		printf("After canonicalize_qual()\n");
		pprint(expr);
#endif
	}

	/* Expand SubLinks to SubPlans */
	if (root->parse->hasSubLinks)
		expr = SS_process_sublinks(root, expr, (kind == EXPRKIND_QUAL));

	/*
	 * XXX do not insert anything here unless you have grokked the comments in
	 * SS_replace_correlation_vars ...
	 */

	/* Replace uplevel vars with Param nodes (this IS possible in VALUES) */
	if (root->query_level > 1)
		expr = SS_replace_correlation_vars(root, expr);

	/*
	 * If it's a qual or havingQual, convert it to implicit-AND format. (We
	 * don't want to do this before eval_const_expressions, since the latter
	 * would be unable to simplify a top-level AND correctly. Also,
	 * SS_process_sublinks expects explicit-AND format.)
	 */
	if (kind == EXPRKIND_QUAL)
		expr = (Node *) make_ands_implicit((Expr *) expr);

	return expr;
}

/*
 * preprocess_qual_conditions
 *		Recursively scan the query's jointree and do subquery_planner's
 *		preprocessing work on each qual condition found therein.
 */
static void
preprocess_qual_conditions(PlannerInfo *root, Node *jtnode)
{
	if (jtnode == NULL)
		return;
	if (IsA(jtnode, RangeTblRef))
	{
		/* nothing to do here */
	}
	else if (IsA(jtnode, FromExpr))
	{
		FromExpr   *f = (FromExpr *) jtnode;
		ListCell   *l;

		foreach(l, f->fromlist)
			preprocess_qual_conditions(root, lfirst(l));

		f->quals = preprocess_expression(root, f->quals, EXPRKIND_QUAL);
	}
	else if (IsA(jtnode, JoinExpr))
	{
		JoinExpr   *j = (JoinExpr *) jtnode;

		preprocess_qual_conditions(root, j->larg);
		preprocess_qual_conditions(root, j->rarg);

		j->quals = preprocess_expression(root, j->quals, EXPRKIND_QUAL);
	}
	else
		elog(ERROR, "unrecognized node type: %d",
			 (int) nodeTag(jtnode));
}

/*
 * preprocess_phv_expression
 *	  Do preprocessing on a PlaceHolderVar expression that's been pulled up.
 *
 * If a LATERAL subquery references an output of another subquery, and that
 * output must be wrapped in a PlaceHolderVar because of an intermediate outer
 * join, then we'll push the PlaceHolderVar expression down into the subquery
 * and later pull it back up during find_lateral_references, which runs after
 * subquery_planner has preprocessed all the expressions that were in the
 * current query level to start with.  So we need to preprocess it then.
 */
Expr *
preprocess_phv_expression(PlannerInfo *root, Expr *expr)
{
	return (Expr *) preprocess_expression(root, (Node *) expr, EXPRKIND_PHV);
}

/*
 * inheritance_planner
 *	  Generate a plan in the case where the result relation is an
 *	  inheritance set.
 *
 * We have to handle this case differently from cases where a source relation
 * is an inheritance set. Source inheritance is expanded at the bottom of the
 * plan tree (see allpaths.c), but target inheritance has to be expanded at
 * the top.  The reason is that for UPDATE, each target relation needs a
 * different targetlist matching its own column set.  Fortunately,
 * the UPDATE/DELETE target can never be the nullable side of an outer join,
 * so it's OK to generate the plan this way.
 *
 * Returns a query plan.
 */
static Plan *
inheritance_planner(PlannerInfo *root)
{
	Query	   *parse = root->parse;
	int			parentRTindex = parse->resultRelation;
	Bitmapset  *resultRTindexes = NULL;
	int			nominalRelation = -1;
	List	   *final_rtable = NIL;
	int			save_rel_array_size = 0;
	RelOptInfo **save_rel_array = NULL;
	List	   *subplans = NIL;
	List	   *resultRelations = NIL;
	List	   *withCheckOptionLists = NIL;
	List	   *returningLists = NIL;
	List	   *rowMarks;
	ListCell   *lc;

	Assert(parse->commandType != CMD_INSERT);

	/*
	 * We generate a modified instance of the original Query for each target
	 * relation, plan that, and put all the plans into a list that will be
	 * controlled by a single ModifyTable node.  All the instances share the
	 * same rangetable, but each instance must have its own set of subquery
	 * RTEs within the finished rangetable because (1) they are likely to get
	 * scribbled on during planning, and (2) it's not inconceivable that
	 * subqueries could get planned differently in different cases.  We need
	 * not create duplicate copies of other RTE kinds, in particular not the
	 * target relations, because they don't have either of those issues.  Not
	 * having to duplicate the target relations is important because doing so
	 * (1) would result in a rangetable of length O(N^2) for N targets, with
	 * at least O(N^3) work expended here; and (2) would greatly complicate
	 * management of the rowMarks list.
	 *
	 * Note that any RTEs with security barrier quals will be turned into
	 * subqueries during planning, and so we must create copies of them too,
	 * except where they are target relations, which will each only be used in
	 * a single plan.
	 */
	resultRTindexes = bms_add_member(resultRTindexes, parentRTindex);
	foreach(lc, root->append_rel_list)
	{
		AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);

		if (appinfo->parent_relid == parentRTindex)
			resultRTindexes = bms_add_member(resultRTindexes,
											 appinfo->child_relid);
	}

	foreach(lc, root->append_rel_list)
	{
		AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
		PlannerInfo subroot;
		Plan	   *subplan;
		Index		rti;

		/* append_rel_list contains all append rels; ignore others */
		if (appinfo->parent_relid != parentRTindex)
			continue;

		/*
		 * We need a working copy of the PlannerInfo so that we can control
		 * propagation of information back to the main copy.
		 */
		memcpy(&subroot, root, sizeof(PlannerInfo));

		/*
		 * Generate modified query with this rel as target.  We first apply
		 * adjust_appendrel_attrs, which copies the Query and changes
		 * references to the parent RTE to refer to the current child RTE,
		 * then fool around with subquery RTEs.
		 */
		subroot.parse = (Query *)
			adjust_appendrel_attrs(root,
								   (Node *) parse,
								   appinfo);

		/*
		 * The rowMarks list might contain references to subquery RTEs, so
		 * make a copy that we can apply ChangeVarNodes to.  (Fortunately, the
		 * executor doesn't need to see the modified copies --- we can just
		 * pass it the original rowMarks list.)
		 */
		subroot.rowMarks = (List *) copyObject(root->rowMarks);

		/*
		 * The append_rel_list likewise might contain references to subquery
		 * RTEs (if any subqueries were flattenable UNION ALLs).  So prepare
		 * to apply ChangeVarNodes to that, too.
		 */
		subroot.append_rel_list = (List *) copyObject(root->append_rel_list);

		/*
		 * Add placeholders to the child Query's rangetable list to fill the
		 * RT indexes already reserved for subqueries in previous children.
		 * These won't be referenced, so there's no need to make them very
		 * valid-looking.
		 */
		while (list_length(subroot.parse->rtable) < list_length(final_rtable))
			subroot.parse->rtable = lappend(subroot.parse->rtable,
											makeNode(RangeTblEntry));

		/*
		 * If this isn't the first child Query, generate duplicates of all
		 * subquery RTEs, and adjust Var numbering to reference the
		 * duplicates. To simplify the loop logic, we scan the original rtable
		 * not the copy just made by adjust_appendrel_attrs; that should be OK
		 * since subquery RTEs couldn't contain any references to the target
		 * rel.
		 */
		if (final_rtable != NIL)
		{
			ListCell   *lr;

			rti = 1;
			foreach(lr, parse->rtable)
			{
				RangeTblEntry *rte = (RangeTblEntry *) lfirst(lr);

				/*
				 * Copy subquery RTEs and RTEs with security barrier quals
				 * that will be turned into subqueries, except those that are
				 * target relations.
				 */
				if (rte->rtekind == RTE_SUBQUERY ||
					(rte->securityQuals != NIL &&
					 !bms_is_member(rti, resultRTindexes)))
				{
					Index		newrti;

					/*
					 * The RTE can't contain any references to its own RT
					 * index, except in the security barrier quals, so we can
					 * save a few cycles by applying ChangeVarNodes before we
					 * append the RTE to the rangetable.
					 */
					newrti = list_length(subroot.parse->rtable) + 1;
					ChangeVarNodes((Node *) subroot.parse, rti, newrti, 0);
					ChangeVarNodes((Node *) subroot.rowMarks, rti, newrti, 0);
					ChangeVarNodes((Node *) subroot.append_rel_list, rti, newrti, 0);
					rte = copyObject(rte);
					ChangeVarNodes((Node *) rte->securityQuals, rti, newrti, 0);
					subroot.parse->rtable = lappend(subroot.parse->rtable,
													rte);
				}
				rti++;
			}
		}

		/* There shouldn't be any OJ or LATERAL info to translate, as yet */
		Assert(subroot.join_info_list == NIL);
		Assert(subroot.lateral_info_list == NIL);
		/* and we haven't created PlaceHolderInfos, either */
		Assert(subroot.placeholder_list == NIL);
		/* hack to mark target relation as an inheritance partition */
		subroot.hasInheritedTarget = true;

		/* Generate plan */
		subplan = grouping_planner(&subroot, 0.0 /* retrieve all tuples */ );

		/*
		 * Planning may have modified the query result relation (if there were
		 * security barrier quals on the result RTE).
		 */
		appinfo->child_relid = subroot.parse->resultRelation;

		/*
		 * We'll use the first child relation (even if it's excluded) as the
		 * nominal target relation of the ModifyTable node.  Because of the
		 * way expand_inherited_rtentry works, this should always be the RTE
		 * representing the parent table in its role as a simple member of the
		 * inheritance set.  (It would be logically cleaner to use the
		 * inheritance parent RTE as the nominal target; but since that RTE
		 * will not be otherwise referenced in the plan, doing so would give
		 * rise to confusing use of multiple aliases in EXPLAIN output for
		 * what the user will think is the "same" table.)
		 */
		if (nominalRelation < 0)
			nominalRelation = appinfo->child_relid;

		/*
		 * If this child rel was excluded by constraint exclusion, exclude it
		 * from the result plan.
		 */
		if (is_dummy_plan(subplan))
			continue;

		subplans = lappend(subplans, subplan);

		/*
		 * If this is the first non-excluded child, its post-planning rtable
		 * becomes the initial contents of final_rtable; otherwise, append
		 * just its modified subquery RTEs to final_rtable.
		 */
		if (final_rtable == NIL)
			final_rtable = subroot.parse->rtable;
		else
		{
			List	   *tmp_rtable = NIL;
			ListCell   *cell1,
					   *cell2;

			/*
			 * Check to see if any of the original RTEs were turned into
			 * subqueries during planning.  Currently, this should only ever
			 * happen due to securityQuals being involved which push a
			 * relation down under a subquery, to ensure that the security
			 * barrier quals are evaluated first.
			 *
			 * When this happens, we want to use the new subqueries in the
			 * final rtable.
			 */
			forboth(cell1, final_rtable, cell2, subroot.parse->rtable)
			{
				RangeTblEntry *rte1 = (RangeTblEntry *) lfirst(cell1);
				RangeTblEntry *rte2 = (RangeTblEntry *) lfirst(cell2);

				if (rte1->rtekind == RTE_RELATION &&
					rte2->rtekind == RTE_SUBQUERY)
				{
					/* Should only be when there are securityQuals today */
					Assert(rte1->securityQuals != NIL);
					tmp_rtable = lappend(tmp_rtable, rte2);
				}
				else
					tmp_rtable = lappend(tmp_rtable, rte1);
			}

			final_rtable = list_concat(tmp_rtable,
									   list_copy_tail(subroot.parse->rtable,
												 list_length(final_rtable)));
		}

		/*
		 * We need to collect all the RelOptInfos from all child plans into
		 * the main PlannerInfo, since setrefs.c will need them.  We use the
		 * last child's simple_rel_array (previous ones are too short), so we
		 * have to propagate forward the RelOptInfos that were already built
		 * in previous children.
		 */
		Assert(subroot.simple_rel_array_size >= save_rel_array_size);
		for (rti = 1; rti < save_rel_array_size; rti++)
		{
			RelOptInfo *brel = save_rel_array[rti];

			if (brel)
				subroot.simple_rel_array[rti] = brel;
		}
		save_rel_array_size = subroot.simple_rel_array_size;
		save_rel_array = subroot.simple_rel_array;

		/* Make sure any initplans from this rel get into the outer list */
		root->init_plans = subroot.init_plans;

		/* Build list of target-relation RT indexes */
		resultRelations = lappend_int(resultRelations, appinfo->child_relid);

		/* Build lists of per-relation WCO and RETURNING targetlists */
		if (parse->withCheckOptions)
			withCheckOptionLists = lappend(withCheckOptionLists,
										   subroot.parse->withCheckOptions);
		if (parse->returningList)
			returningLists = lappend(returningLists,
									 subroot.parse->returningList);

		Assert(!parse->onConflict);
	}

	/* Mark result as unordered (probably unnecessary) */
	root->query_pathkeys = NIL;

	/*
	 * If we managed to exclude every child rel, return a dummy plan; it
	 * doesn't even need a ModifyTable node.
	 */
	if (subplans == NIL)
	{
		/* although dummy, it must have a valid tlist for executor */
		List	   *tlist;

		tlist = preprocess_targetlist(root, parse->targetList);
		return (Plan *) make_result(root,
									tlist,
									(Node *) list_make1(makeBoolConst(false,
																	  false)),
									NULL);
	}

	/*
	 * Put back the final adjusted rtable into the master copy of the Query.
	 */
	parse->rtable = final_rtable;
	root->simple_rel_array_size = save_rel_array_size;
	root->simple_rel_array = save_rel_array;

	/*
	 * If there was a FOR [KEY] UPDATE/SHARE clause, the LockRows node will
	 * have dealt with fetching non-locked marked rows, else we need to have
	 * ModifyTable do that.
	 */
	if (parse->rowMarks)
		rowMarks = NIL;
	else
		rowMarks = root->rowMarks;

	/* And last, tack on a ModifyTable node to do the UPDATE/DELETE work */
	return (Plan *) make_modifytable(root,
									 parse->commandType,
									 parse->canSetTag,
									 nominalRelation,
									 resultRelations,
									 subplans,
									 withCheckOptionLists,
									 returningLists,
									 rowMarks,
									 NULL,
									 SS_assign_special_param(root));
}

/*--------------------
 * grouping_planner
 *	  Perform planning steps related to grouping, aggregation, etc.
 *	  This primarily means adding top-level processing to the basic
 *	  query plan produced by query_planner.
 *
 * tuple_fraction is the fraction of tuples we expect will be retrieved
 *
 * tuple_fraction is interpreted as follows:
 *	  0: expect all tuples to be retrieved (normal case)
 *	  0 < tuple_fraction < 1: expect the given fraction of tuples available
 *		from the plan to be retrieved
 *	  tuple_fraction >= 1: tuple_fraction is the absolute number of tuples
 *		expected to be retrieved (ie, a LIMIT specification)
 *
 * Returns a query plan.  Also, root->query_pathkeys is returned as the
 * actual output ordering of the plan (in pathkey format).
 *--------------------
 */
static Plan *
grouping_planner(PlannerInfo *root, double tuple_fraction)
{
	Query	   *parse = root->parse;
	List	   *tlist = parse->targetList;
	int64		offset_est = 0;
	int64		count_est = 0;
	double		limit_tuples = -1.0;
	Plan	   *result_plan;
	List	   *current_pathkeys;
	double		dNumGroups = 0;
	bool		use_hashed_distinct = false;
	bool		tested_hashed_distinct = false;

	/* Tweak caller-supplied tuple_fraction if have LIMIT/OFFSET */
	if (parse->limitCount || parse->limitOffset)
	{
		tuple_fraction = preprocess_limit(root, tuple_fraction,
										  &offset_est, &count_est);

		/*
		 * If we have a known LIMIT, and don't have an unknown OFFSET, we can
		 * estimate the effects of using a bounded sort.
		 */
		if (count_est > 0 && offset_est >= 0)
			limit_tuples = (double) count_est + (double) offset_est;
	}

	if (parse->setOperations)
	{
		List	   *set_sortclauses;

		/*
		 * If there's a top-level ORDER BY, assume we have to fetch all the
		 * tuples.  This might be too simplistic given all the hackery below
		 * to possibly avoid the sort; but the odds of accurate estimates here
		 * are pretty low anyway.
		 */
		if (parse->sortClause)
			tuple_fraction = 0.0;

		/*
		 * Construct the plan for set operations.  The result will not need
		 * any work except perhaps a top-level sort and/or LIMIT.  Note that
		 * any special work for recursive unions is the responsibility of
		 * plan_set_operations.
		 */
		result_plan = plan_set_operations(root, tuple_fraction,
										  &set_sortclauses);

		/*
		 * Calculate pathkeys representing the sort order (if any) of the set
		 * operation's result.  We have to do this before overwriting the sort
		 * key information...
		 */
		current_pathkeys = make_pathkeys_for_sortclauses(root,
														 set_sortclauses,
													result_plan->targetlist);

		/*
		 * We should not need to call preprocess_targetlist, since we must be
		 * in a SELECT query node.  Instead, use the targetlist returned by
		 * plan_set_operations (since this tells whether it returned any
		 * resjunk columns!), and transfer any sort key information from the
		 * original tlist.
		 */
		Assert(parse->commandType == CMD_SELECT);

		tlist = postprocess_setop_tlist(copyObject(result_plan->targetlist),
										tlist);

		/*
		 * Can't handle FOR [KEY] UPDATE/SHARE here (parser should have
		 * checked already, but let's make sure).
		 */
		if (parse->rowMarks)
			ereport(ERROR,
					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
			/*------
			  translator: %s is a SQL row locking clause such as FOR UPDATE */
					 errmsg("%s is not allowed with UNION/INTERSECT/EXCEPT",
							LCS_asString(((RowMarkClause *)
									linitial(parse->rowMarks))->strength))));

		/*
		 * Calculate pathkeys that represent result ordering requirements
		 */
		Assert(parse->distinctClause == NIL);
		root->sort_pathkeys = make_pathkeys_for_sortclauses(root,
															parse->sortClause,
															tlist);
	}
	else
	{
		/* No set operations, do regular planning */
		List	   *sub_tlist;
		AttrNumber *groupColIdx = NULL;
		bool		need_tlist_eval = true;
		long		numGroups = 0;
		AggClauseCosts agg_costs;
		int			numGroupCols;
		double		path_rows;
		int			path_width;
		bool		use_hashed_grouping = false;
		WindowFuncLists *wflists = NULL;
		List	   *activeWindows = NIL;
		OnConflictExpr *onconfl;
		int			maxref = 0;
		int		   *tleref_to_colnum_map;
		List	   *rollup_lists = NIL;
		List	   *rollup_groupclauses = NIL;
		standard_qp_extra qp_extra;
		RelOptInfo *final_rel;
		Path	   *cheapest_path;
		Path	   *sorted_path;
		Path	   *best_path;

		MemSet(&agg_costs, 0, sizeof(AggClauseCosts));

		/* A recursive query should always have setOperations */
		Assert(!root->hasRecursion);

		/* Preprocess Grouping set, if any */
		if (parse->groupingSets)
			parse->groupingSets = expand_grouping_sets(parse->groupingSets, -1);

		if (parse->groupClause)
		{
			ListCell   *lc;

			foreach(lc, parse->groupClause)
			{
				SortGroupClause *gc = lfirst(lc);

				if (gc->tleSortGroupRef > maxref)
					maxref = gc->tleSortGroupRef;
			}
		}

		tleref_to_colnum_map = palloc((maxref + 1) * sizeof(int));

		if (parse->groupingSets)
		{
			ListCell   *lc;
			ListCell   *lc2;
			ListCell   *lc_set;
			List	   *sets = extract_rollup_sets(parse->groupingSets);

			foreach(lc_set, sets)
			{
				List	   *current_sets = reorder_grouping_sets(lfirst(lc_set),
													  (list_length(sets) == 1
													   ? parse->sortClause
													   : NIL));
				List	   *groupclause = preprocess_groupclause(root, linitial(current_sets));
				int			ref = 0;

				/*
				 * Now that we've pinned down an order for the groupClause for
				 * this list of grouping sets, we need to remap the entries in
				 * the grouping sets from sortgrouprefs to plain indices
				 * (0-based) into the groupClause for this collection of
				 * grouping sets.
				 */

				foreach(lc, groupclause)
				{
					SortGroupClause *gc = lfirst(lc);

					tleref_to_colnum_map[gc->tleSortGroupRef] = ref++;
				}

				foreach(lc, current_sets)
				{
					foreach(lc2, (List *) lfirst(lc))
					{
						lfirst_int(lc2) = tleref_to_colnum_map[lfirst_int(lc2)];
					}
				}

				rollup_lists = lcons(current_sets, rollup_lists);
				rollup_groupclauses = lcons(groupclause, rollup_groupclauses);
			}
		}
		else
		{
			/* Preprocess GROUP BY clause, if any */
			if (parse->groupClause)
				parse->groupClause = preprocess_groupclause(root, NIL);
			rollup_groupclauses = list_make1(parse->groupClause);
		}

		numGroupCols = list_length(parse->groupClause);

		/* Preprocess targetlist */
		tlist = preprocess_targetlist(root, tlist);

		onconfl = parse->onConflict;
		if (onconfl)
			onconfl->onConflictSet =
				preprocess_onconflict_targetlist(onconfl->onConflictSet,
												 parse->resultRelation,
												 parse->rtable);

		/*
		 * Expand any rangetable entries that have security barrier quals.
		 * This may add new security barrier subquery RTEs to the rangetable.
		 */
		expand_security_quals(root, tlist);
		root->glob->hasRowSecurity = parse->hasRowSecurity;

		/*
		 * Locate any window functions in the tlist.  (We don't need to look
		 * anywhere else, since expressions used in ORDER BY will be in there
		 * too.)  Note that they could all have been eliminated by constant
		 * folding, in which case we don't need to do any more work.
		 */
		if (parse->hasWindowFuncs)
		{
			wflists = find_window_functions((Node *) tlist,
											list_length(parse->windowClause));
			if (wflists->numWindowFuncs > 0)
				activeWindows = select_active_windows(root, wflists);
			else
				parse->hasWindowFuncs = false;
		}

		/*
		 * Generate appropriate target list for subplan; may be different from
		 * tlist if grouping or aggregation is needed.
		 */
		sub_tlist = make_subplanTargetList(root, tlist,
										   &groupColIdx, &need_tlist_eval);

		/*
		 * Do aggregate preprocessing, if the query has any aggs.
		 *
		 * Note: think not that we can turn off hasAggs if we find no aggs. It
		 * is possible for constant-expression simplification to remove all
		 * explicit references to aggs, but we still have to follow the
		 * aggregate semantics (eg, producing only one output row).
		 */
		if (parse->hasAggs)
		{
			/*
			 * Collect statistics about aggregates for estimating costs. Note:
			 * we do not attempt to detect duplicate aggregates here; a
			 * somewhat-overestimated cost is okay for our present purposes.
			 */
			count_agg_clauses(root, (Node *) tlist, &agg_costs);
			count_agg_clauses(root, parse->havingQual, &agg_costs);

			/*
			 * Preprocess MIN/MAX aggregates, if any.  Note: be careful about
			 * adding logic between here and the optimize_minmax_aggregates
			 * call.  Anything that is needed in MIN/MAX-optimizable cases
			 * will have to be duplicated in planagg.c.
			 */
			preprocess_minmax_aggregates(root, tlist);
		}

		/* Make tuple_fraction accessible to lower-level routines */
		root->tuple_fraction = tuple_fraction;

		/*
		 * Figure out whether there's a hard limit on the number of rows that
		 * query_planner's result subplan needs to return.  Even if we know a
		 * hard limit overall, it doesn't apply if the query has any
		 * grouping/aggregation operations.
		 */
		if (parse->groupClause ||
			parse->groupingSets ||
			parse->distinctClause ||
			parse->hasAggs ||
			parse->hasWindowFuncs ||
			root->hasHavingQual)
			root->limit_tuples = -1.0;
		else
			root->limit_tuples = limit_tuples;

		/* Set up data needed by standard_qp_callback */
		qp_extra.tlist = tlist;
		qp_extra.activeWindows = activeWindows;
		qp_extra.groupClause = llast(rollup_groupclauses);

		/*
		 * Generate the best unsorted and presorted paths for this Query (but
		 * note there may not be any presorted paths).  We also generate (in
		 * standard_qp_callback) pathkey representations of the query's sort
		 * clause, distinct clause, etc.
		 */
		final_rel = query_planner(root, sub_tlist,
								  standard_qp_callback, &qp_extra);

		/*
		 * Extract rowcount and width estimates for use below.
		 */
		path_rows = final_rel->rows;
		path_width = final_rel->width;

		/*
		 * If there's grouping going on, estimate the number of result groups.
		 * We couldn't do this any earlier because it depends on relation size
		 * estimates that are created within query_planner().
		 *
		 * Then convert tuple_fraction to fractional form if it is absolute,
		 * and if grouping or aggregation is involved, adjust tuple_fraction
		 * to describe the fraction of the underlying un-aggregated tuples
		 * that will be fetched.
		 */
		dNumGroups = 1;			/* in case not grouping */

		if (parse->groupClause)
		{
			List	   *groupExprs;

			if (parse->groupingSets)
			{
				ListCell   *lc,
						   *lc2;

				dNumGroups = 0;

				forboth(lc, rollup_groupclauses, lc2, rollup_lists)
				{
					ListCell   *lc3;

					groupExprs = get_sortgrouplist_exprs(lfirst(lc),
														 parse->targetList);

					foreach(lc3, lfirst(lc2))
					{
						List	   *gset = lfirst(lc3);

						dNumGroups += estimate_num_groups(root,
														  groupExprs,
														  path_rows,
														  &gset);
					}
				}
			}
			else
			{
				groupExprs = get_sortgrouplist_exprs(parse->groupClause,
													 parse->targetList);

				dNumGroups = estimate_num_groups(root, groupExprs, path_rows,
												 NULL);
			}

			/*
			 * In GROUP BY mode, an absolute LIMIT is relative to the number
			 * of groups not the number of tuples.  If the caller gave us a
			 * fraction, keep it as-is.  (In both cases, we are effectively
			 * assuming that all the groups are about the same size.)
			 */
			if (tuple_fraction >= 1.0)
				tuple_fraction /= dNumGroups;

			/*
			 * If there's more than one grouping set, we'll have to sort the
			 * entire input.
			 */
			if (list_length(rollup_lists) > 1)
				tuple_fraction = 0.0;

			/*
			 * If both GROUP BY and ORDER BY are specified, we will need two
			 * levels of sort --- and, therefore, certainly need to read all
			 * the tuples --- unless ORDER BY is a subset of GROUP BY.
			 * Likewise if we have both DISTINCT and GROUP BY, or if we have a
			 * window specification not compatible with the GROUP BY.
			 */
			if (!pathkeys_contained_in(root->sort_pathkeys,
									   root->group_pathkeys) ||
				!pathkeys_contained_in(root->distinct_pathkeys,
									   root->group_pathkeys) ||
				!pathkeys_contained_in(root->window_pathkeys,
									   root->group_pathkeys))
				tuple_fraction = 0.0;
		}
		else if (parse->hasAggs || root->hasHavingQual || parse->groupingSets)
		{
			/*
			 * Ungrouped aggregate will certainly want to read all the tuples,
			 * and it will deliver a single result row per grouping set (or 1
			 * if no grouping sets were explicitly given, in which case leave
			 * dNumGroups as-is)
			 */
			tuple_fraction = 0.0;
			if (parse->groupingSets)
				dNumGroups = list_length(parse->groupingSets);
		}
		else if (parse->distinctClause)
		{
			/*
			 * Since there was no grouping or aggregation, it's reasonable to
			 * assume the UNIQUE filter has effects comparable to GROUP BY.
			 * (If DISTINCT is used with grouping, we ignore its effects for
			 * rowcount estimation purposes; this amounts to assuming the
			 * grouped rows are distinct already.)
			 */
			List	   *distinctExprs;

			distinctExprs = get_sortgrouplist_exprs(parse->distinctClause,
													parse->targetList);
			dNumGroups = estimate_num_groups(root, distinctExprs, path_rows, NULL);

			/*
			 * Adjust tuple_fraction the same way as for GROUP BY, too.
			 */
			if (tuple_fraction >= 1.0)
				tuple_fraction /= dNumGroups;
		}
		else
		{
			/*
			 * Plain non-grouped, non-aggregated query: an absolute tuple
			 * fraction can be divided by the number of tuples.
			 */
			if (tuple_fraction >= 1.0)
				tuple_fraction /= path_rows;
		}

		/*
		 * Pick out the cheapest-total path as well as the cheapest presorted
		 * path for the requested pathkeys (if there is one).  We should take
		 * the tuple fraction into account when selecting the cheapest
		 * presorted path, but not when selecting the cheapest-total path,
		 * since if we have to sort then we'll have to fetch all the tuples.
		 * (But there's a special case: if query_pathkeys is NIL, meaning
		 * order doesn't matter, then the "cheapest presorted" path will be
		 * the cheapest overall for the tuple fraction.)
		 */
		cheapest_path = final_rel->cheapest_total_path;

		sorted_path =
			get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
													  root->query_pathkeys,
													  NULL,
													  tuple_fraction);

		/* Don't consider same path in both guises; just wastes effort */
		if (sorted_path == cheapest_path)
			sorted_path = NULL;

		/*
		 * Forget about the presorted path if it would be cheaper to sort the
		 * cheapest-total path.  Here we need consider only the behavior at
		 * the tuple_fraction point.  Also, limit_tuples is only relevant if
		 * not grouping/aggregating, so use root->limit_tuples in the
		 * cost_sort call.
		 */
		if (sorted_path)
		{
			Path		sort_path;		/* dummy for result of cost_sort */

			if (root->query_pathkeys == NIL ||
				pathkeys_contained_in(root->query_pathkeys,
									  cheapest_path->pathkeys))
			{
				/* No sort needed for cheapest path */
				sort_path.startup_cost = cheapest_path->startup_cost;
				sort_path.total_cost = cheapest_path->total_cost;
			}
			else
			{
				/* Figure cost for sorting */
				cost_sort(&sort_path, root, root->query_pathkeys,
						  cheapest_path->total_cost,
						  path_rows, path_width,
						  0.0, work_mem, root->limit_tuples);
			}

			if (compare_fractional_path_costs(sorted_path, &sort_path,
											  tuple_fraction) > 0)
			{
				/* Presorted path is a loser */
				sorted_path = NULL;
			}
		}

		/*
		 * Consider whether we want to use hashing instead of sorting.
		 */
		if (parse->groupClause)
		{
			/*
			 * If grouping, decide whether to use sorted or hashed grouping.
			 * If grouping sets are present, we can currently do only sorted
			 * grouping.
			 */

			if (parse->groupingSets)
			{
				use_hashed_grouping = false;
			}
			else
			{
				use_hashed_grouping =
					choose_hashed_grouping(root,
										   tuple_fraction, limit_tuples,
										   path_rows, path_width,
										   cheapest_path, sorted_path,
										   dNumGroups, &agg_costs);
			}

			/* Also convert # groups to long int --- but 'ware overflow! */
			numGroups = (long) Min(dNumGroups, (double) LONG_MAX);
		}
		else if (parse->distinctClause && sorted_path &&
				 !root->hasHavingQual && !parse->hasAggs && !activeWindows)
		{
			/*
			 * We'll reach the DISTINCT stage without any intermediate
			 * processing, so figure out whether we will want to hash or not
			 * so we can choose whether to use cheapest or sorted path.
			 */
			use_hashed_distinct =
				choose_hashed_distinct(root,
									   tuple_fraction, limit_tuples,
									   path_rows, path_width,
									   cheapest_path->startup_cost,
									   cheapest_path->total_cost,
									   sorted_path->startup_cost,
									   sorted_path->total_cost,
									   sorted_path->pathkeys,
									   dNumGroups);
			tested_hashed_distinct = true;
		}

		/*
		 * Select the best path.  If we are doing hashed grouping, we will
		 * always read all the input tuples, so use the cheapest-total path.
		 * Otherwise, the comparison above is correct.
		 */
		if (use_hashed_grouping || use_hashed_distinct || !sorted_path)
			best_path = cheapest_path;
		else
			best_path = sorted_path;

		/*
		 * Check to see if it's possible to optimize MIN/MAX aggregates. If
		 * so, we will forget all the work we did so far to choose a "regular"
		 * path ... but we had to do it anyway to be able to tell which way is
		 * cheaper.
		 */
		result_plan = optimize_minmax_aggregates(root,
												 tlist,
												 &agg_costs,
												 best_path);
		if (result_plan != NULL)
		{
			/*
			 * optimize_minmax_aggregates generated the full plan, with the
			 * right tlist, and it has no sort order.
			 */
			current_pathkeys = NIL;
		}
		else
		{
			/*
			 * Normal case --- create a plan according to query_planner's
			 * results.
			 */
			bool		need_sort_for_grouping = false;

			result_plan = create_plan(root, best_path);
			current_pathkeys = best_path->pathkeys;

			/* Detect if we'll need an explicit sort for grouping */
			if (parse->groupClause && !use_hashed_grouping &&
			  !pathkeys_contained_in(root->group_pathkeys, current_pathkeys))
			{
				need_sort_for_grouping = true;

				/*
				 * Always override create_plan's tlist, so that we don't sort
				 * useless data from a "physical" tlist.
				 */
				need_tlist_eval = true;
			}

			/*
			 * create_plan returns a plan with just a "flat" tlist of required
			 * Vars.  Usually we need to insert the sub_tlist as the tlist of
			 * the top plan node.  However, we can skip that if we determined
			 * that whatever create_plan chose to return will be good enough.
			 */
			if (need_tlist_eval)
			{
				/*
				 * If the top-level plan node is one that cannot do expression
				 * evaluation and its existing target list isn't already what
				 * we need, we must insert a Result node to project the
				 * desired tlist.
				 */
				if (!is_projection_capable_plan(result_plan) &&
					!tlist_same_exprs(sub_tlist, result_plan->targetlist))
				{
					result_plan = (Plan *) make_result(root,
													   sub_tlist,
													   NULL,
													   result_plan);
				}
				else
				{
					/*
					 * Otherwise, just replace the subplan's flat tlist with
					 * the desired tlist.
					 */
					result_plan->targetlist = sub_tlist;
				}

				/*
				 * Also, account for the cost of evaluation of the sub_tlist.
				 * See comments for add_tlist_costs_to_plan() for more info.
				 */
				add_tlist_costs_to_plan(root, result_plan, sub_tlist);
			}
			else
			{
				/*
				 * Since we're using create_plan's tlist and not the one
				 * make_subplanTargetList calculated, we have to refigure any
				 * grouping-column indexes make_subplanTargetList computed.
				 */
				locate_grouping_columns(root, tlist, result_plan->targetlist,
										groupColIdx);
			}

			/*
			 * groupColIdx is now cast in stone, so record a mapping from
			 * tleSortGroupRef to column index. setrefs.c needs this to
			 * finalize GROUPING() operations.
			 */

			if (parse->groupingSets)
			{
				AttrNumber *grouping_map = palloc0(sizeof(AttrNumber) * (maxref + 1));
				ListCell   *lc;
				int			i = 0;

				foreach(lc, parse->groupClause)
				{
					SortGroupClause *gc = lfirst(lc);

					grouping_map[gc->tleSortGroupRef] = groupColIdx[i++];
				}

				root->grouping_map = grouping_map;
			}

			/*
			 * Insert AGG or GROUP node if needed, plus an explicit sort step
			 * if necessary.
			 *
			 * HAVING clause, if any, becomes qual of the Agg or Group node.
			 */
			if (use_hashed_grouping)
			{
				/* Hashed aggregate plan --- no sort needed */
				result_plan = (Plan *) make_agg(root,
												tlist,
												(List *) parse->havingQual,
												AGG_HASHED,
												&agg_costs,
												numGroupCols,
												groupColIdx,
									extract_grouping_ops(parse->groupClause),
												NIL,
												numGroups,
												result_plan);
				/* Hashed aggregation produces randomly-ordered results */
				current_pathkeys = NIL;
			}
			else if (parse->hasAggs || (parse->groupingSets && parse->groupClause))
			{
				/*
				 * Output is in sorted order by group_pathkeys if, and only
				 * if, there is a single rollup operation on a non-empty list
				 * of grouping expressions.
				 */
				if (list_length(rollup_groupclauses) == 1
					&& list_length(linitial(rollup_groupclauses)) > 0)
					current_pathkeys = root->group_pathkeys;
				else
					current_pathkeys = NIL;

				result_plan = build_grouping_chain(root,
												   parse,
												   tlist,
												   need_sort_for_grouping,
												   rollup_groupclauses,
												   rollup_lists,
												   groupColIdx,
												   &agg_costs,
												   numGroups,
												   result_plan);

				/*
				 * these are destroyed by build_grouping_chain, so make sure
				 * we don't try and touch them again
				 */
				rollup_groupclauses = NIL;
				rollup_lists = NIL;
			}
			else if (parse->groupClause)
			{
				/*
				 * GROUP BY without aggregation, so insert a group node (plus
				 * the appropriate sort node, if necessary).
				 *
				 * Add an explicit sort if we couldn't make the path come out
				 * the way the GROUP node needs it.
				 */
				if (need_sort_for_grouping)
				{
					result_plan = (Plan *)
						make_sort_from_groupcols(root,
												 parse->groupClause,
												 groupColIdx,
												 result_plan);
					current_pathkeys = root->group_pathkeys;
				}

				result_plan = (Plan *) make_group(root,
												  tlist,
												  (List *) parse->havingQual,
												  numGroupCols,
												  groupColIdx,
									extract_grouping_ops(parse->groupClause),
												  dNumGroups,
												  result_plan);
				/* The Group node won't change sort ordering */
			}
			else if (root->hasHavingQual || parse->groupingSets)
			{
				int			nrows = list_length(parse->groupingSets);

				/*
				 * No aggregates, and no GROUP BY, but we have a HAVING qual
				 * or grouping sets (which by elimination of cases above must
				 * consist solely of empty grouping sets, since otherwise
				 * groupClause will be non-empty).
				 *
				 * This is a degenerate case in which we are supposed to emit
				 * either 0 or 1 row for each grouping set depending on
				 * whether HAVING succeeds.  Furthermore, there cannot be any
				 * variables in either HAVING or the targetlist, so we
				 * actually do not need the FROM table at all!	We can just
				 * throw away the plan-so-far and generate a Result node. This
				 * is a sufficiently unusual corner case that it's not worth
				 * contorting the structure of this routine to avoid having to
				 * generate the plan in the first place.
				 */
				result_plan = (Plan *) make_result(root,
												   tlist,
												   parse->havingQual,
												   NULL);

				/*
				 * Doesn't seem worthwhile writing code to cons up a
				 * generate_series or a values scan to emit multiple rows.
				 * Instead just clone the result in an Append.
				 */
				if (nrows > 1)
				{
					List	   *plans = list_make1(result_plan);

					while (--nrows > 0)
						plans = lappend(plans, copyObject(result_plan));

					result_plan = (Plan *) make_append(plans, tlist);
				}
			}
		}						/* end of non-minmax-aggregate case */

		/*
		 * Since each window function could require a different sort order, we
		 * stack up a WindowAgg node for each window, with sort steps between
		 * them as needed.
		 */
		if (activeWindows)
		{
			List	   *window_tlist;
			ListCell   *l;

			/*
			 * If the top-level plan node is one that cannot do expression
			 * evaluation, we must insert a Result node to project the desired
			 * tlist.  (In some cases this might not really be required, but
			 * it's not worth trying to avoid it.  In particular, think not to
			 * skip adding the Result if the initial window_tlist matches the
			 * top-level plan node's output, because we might change the tlist
			 * inside the following loop.)	Note that on second and subsequent
			 * passes through the following loop, the top-level node will be a
			 * WindowAgg which we know can project; so we only need to check
			 * once.
			 */
			if (!is_projection_capable_plan(result_plan))
			{
				result_plan = (Plan *) make_result(root,
												   NIL,
												   NULL,
												   result_plan);
			}

			/*
			 * The "base" targetlist for all steps of the windowing process is
			 * a flat tlist of all Vars and Aggs needed in the result.  (In
			 * some cases we wouldn't need to propagate all of these all the
			 * way to the top, since they might only be needed as inputs to
			 * WindowFuncs.  It's probably not worth trying to optimize that
			 * though.)  We also add window partitioning and sorting
			 * expressions to the base tlist, to ensure they're computed only
			 * once at the bottom of the stack (that's critical for volatile
			 * functions).  As we climb up the stack, we'll add outputs for
			 * the WindowFuncs computed at each level.
			 */
			window_tlist = make_windowInputTargetList(root,
													  tlist,
													  activeWindows);

			/*
			 * The copyObject steps here are needed to ensure that each plan
			 * node has a separately modifiable tlist.  (XXX wouldn't a
			 * shallow list copy do for that?)
			 */
			result_plan->targetlist = (List *) copyObject(window_tlist);

			foreach(l, activeWindows)
			{
				WindowClause *wc = (WindowClause *) lfirst(l);
				List	   *window_pathkeys;
				int			partNumCols;
				AttrNumber *partColIdx;
				Oid		   *partOperators;
				int			ordNumCols;
				AttrNumber *ordColIdx;
				Oid		   *ordOperators;

				window_pathkeys = make_pathkeys_for_window(root,
														   wc,
														   tlist);

				/*
				 * This is a bit tricky: we build a sort node even if we don't
				 * really have to sort.  Even when no explicit sort is needed,
				 * we need to have suitable resjunk items added to the input
				 * plan's tlist for any partitioning or ordering columns that
				 * aren't plain Vars.  (In theory, make_windowInputTargetList
				 * should have provided all such columns, but let's not assume
				 * that here.)	Furthermore, this way we can use existing
				 * infrastructure to identify which input columns are the
				 * interesting ones.
				 */
				if (window_pathkeys)
				{
					Sort	   *sort_plan;

					sort_plan = make_sort_from_pathkeys(root,
														result_plan,
														window_pathkeys,
														-1.0);
					if (!pathkeys_contained_in(window_pathkeys,
											   current_pathkeys))
					{
						/* we do indeed need to sort */
						result_plan = (Plan *) sort_plan;
						current_pathkeys = window_pathkeys;
					}
					/* In either case, extract the per-column information */
					get_column_info_for_window(root, wc, tlist,
											   sort_plan->numCols,
											   sort_plan->sortColIdx,
											   &partNumCols,
											   &partColIdx,
											   &partOperators,
											   &ordNumCols,
											   &ordColIdx,
											   &ordOperators);
				}
				else
				{
					/* empty window specification, nothing to sort */
					partNumCols = 0;
					partColIdx = NULL;
					partOperators = NULL;
					ordNumCols = 0;
					ordColIdx = NULL;
					ordOperators = NULL;
				}

				if (lnext(l))
				{
					/* Add the current WindowFuncs to the running tlist */
					window_tlist = add_to_flat_tlist(window_tlist,
										   wflists->windowFuncs[wc->winref]);
				}
				else
				{
					/* Install the original tlist in the topmost WindowAgg */
					window_tlist = tlist;
				}

				/* ... and make the WindowAgg plan node */
				result_plan = (Plan *)
					make_windowagg(root,
								   (List *) copyObject(window_tlist),
								   wflists->windowFuncs[wc->winref],
								   wc->winref,
								   partNumCols,
								   partColIdx,
								   partOperators,
								   ordNumCols,
								   ordColIdx,
								   ordOperators,
								   wc->frameOptions,
								   wc->startOffset,
								   wc->endOffset,
								   result_plan);
			}
		}
	}							/* end of if (setOperations) */

	/*
	 * If there is a DISTINCT clause, add the necessary node(s).
	 */
	if (parse->distinctClause)
	{
		double		dNumDistinctRows;
		long		numDistinctRows;

		/*
		 * If there was grouping or aggregation, use the current number of
		 * rows as the estimated number of DISTINCT rows (ie, assume the
		 * result was already mostly unique).  If not, use the number of
		 * distinct-groups calculated previously.
		 */
		if (parse->groupClause || parse->groupingSets || root->hasHavingQual || parse->hasAggs)
			dNumDistinctRows = result_plan->plan_rows;
		else
			dNumDistinctRows = dNumGroups;

		/* Also convert to long int --- but 'ware overflow! */
		numDistinctRows = (long) Min(dNumDistinctRows, (double) LONG_MAX);

		/* Choose implementation method if we didn't already */
		if (!tested_hashed_distinct)
		{
			/*
			 * At this point, either hashed or sorted grouping will have to
			 * work from result_plan, so we pass that as both "cheapest" and
			 * "sorted".
			 */
			use_hashed_distinct =
				choose_hashed_distinct(root,
									   tuple_fraction, limit_tuples,
									   result_plan->plan_rows,
									   result_plan->plan_width,
									   result_plan->startup_cost,
									   result_plan->total_cost,
									   result_plan->startup_cost,
									   result_plan->total_cost,
									   current_pathkeys,
									   dNumDistinctRows);
		}

		if (use_hashed_distinct)
		{
			/* Hashed aggregate plan --- no sort needed */
			result_plan = (Plan *) make_agg(root,
											result_plan->targetlist,
											NIL,
											AGG_HASHED,
											NULL,
										  list_length(parse->distinctClause),
								 extract_grouping_cols(parse->distinctClause,
													result_plan->targetlist),
								 extract_grouping_ops(parse->distinctClause),
											NIL,
											numDistinctRows,
											result_plan);
			/* Hashed aggregation produces randomly-ordered results */
			current_pathkeys = NIL;
		}
		else
		{
			/*
			 * Use a Unique node to implement DISTINCT.  Add an explicit sort
			 * if we couldn't make the path come out the way the Unique node
			 * needs it.  If we do have to sort, always sort by the more
			 * rigorous of DISTINCT and ORDER BY, to avoid a second sort
			 * below.  However, for regular DISTINCT, don't sort now if we
			 * don't have to --- sorting afterwards will likely be cheaper,
			 * and also has the possibility of optimizing via LIMIT.  But for
			 * DISTINCT ON, we *must* force the final sort now, else it won't
			 * have the desired behavior.
			 */
			List	   *needed_pathkeys;

			if (parse->hasDistinctOn &&
				list_length(root->distinct_pathkeys) <
				list_length(root->sort_pathkeys))
				needed_pathkeys = root->sort_pathkeys;
			else
				needed_pathkeys = root->distinct_pathkeys;

			if (!pathkeys_contained_in(needed_pathkeys, current_pathkeys))
			{
				if (list_length(root->distinct_pathkeys) >=
					list_length(root->sort_pathkeys))
					current_pathkeys = root->distinct_pathkeys;
				else
				{
					current_pathkeys = root->sort_pathkeys;
					/* Assert checks that parser didn't mess up... */
					Assert(pathkeys_contained_in(root->distinct_pathkeys,
												 current_pathkeys));
				}

				result_plan = (Plan *) make_sort_from_pathkeys(root,
															   result_plan,
															current_pathkeys,
															   -1.0);
			}

			result_plan = (Plan *) make_unique(result_plan,
											   parse->distinctClause);
			result_plan->plan_rows = dNumDistinctRows;
			/* The Unique node won't change sort ordering */
		}
	}

	/*
	 * If ORDER BY was given and we were not able to make the plan come out in
	 * the right order, add an explicit sort step.
	 */
	if (parse->sortClause)
	{
		if (!pathkeys_contained_in(root->sort_pathkeys, current_pathkeys))
		{
			result_plan = (Plan *) make_sort_from_pathkeys(root,
														   result_plan,
														 root->sort_pathkeys,
														   limit_tuples);
			current_pathkeys = root->sort_pathkeys;
		}
	}

	/*
	 * If there is a FOR [KEY] UPDATE/SHARE clause, add the LockRows node.
	 * (Note: we intentionally test parse->rowMarks not root->rowMarks here.
	 * If there are only non-locking rowmarks, they should be handled by the
	 * ModifyTable node instead.)
	 */
	if (parse->rowMarks)
	{
		result_plan = (Plan *) make_lockrows(result_plan,
											 root->rowMarks,
											 SS_assign_special_param(root));

		/*
		 * The result can no longer be assumed sorted, since locking might
		 * cause the sort key columns to be replaced with new values.
		 */
		current_pathkeys = NIL;
	}

	/*
	 * Finally, if there is a LIMIT/OFFSET clause, add the LIMIT node.
	 */
	if (limit_needed(parse))
	{
		result_plan = (Plan *) make_limit(result_plan,
										  parse->limitOffset,
										  parse->limitCount,
										  offset_est,
										  count_est);
	}

	/*
	 * Return the actual output ordering in query_pathkeys for possible use by
	 * an outer query level.
	 */
	root->query_pathkeys = current_pathkeys;

	return result_plan;
}


/*
 * Given a groupclause for a collection of grouping sets, produce the
 * corresponding groupColIdx.
 *
 * root->grouping_map maps the tleSortGroupRef to the actual column position in
 * the input tuple. So we get the ref from the entries in the groupclause and
 * look them up there.
 */
static AttrNumber *
remap_groupColIdx(PlannerInfo *root, List *groupClause)
{
	AttrNumber *grouping_map = root->grouping_map;
	AttrNumber *new_grpColIdx;
	ListCell   *lc;
	int			i;

	Assert(grouping_map);

	new_grpColIdx = palloc0(sizeof(AttrNumber) * list_length(groupClause));

	i = 0;
	foreach(lc, groupClause)
	{
		SortGroupClause *clause = lfirst(lc);

		new_grpColIdx[i++] = grouping_map[clause->tleSortGroupRef];
	}

	return new_grpColIdx;
}

/*
 * Build Agg and Sort nodes to implement sorted grouping with one or more
 * grouping sets. (A plain GROUP BY or just the presence of aggregates counts
 * for this purpose as a single grouping set; the calling code is responsible
 * for providing a non-empty rollup_groupclauses list for such cases, though
 * rollup_lists may be null.)
 *
 * The last entry in rollup_groupclauses (which is the one the input is sorted
 * on, if at all) is the one used for the returned Agg node. Any additional
 * rollups are attached, with corresponding sort info, to subsidiary Agg and
 * Sort nodes attached to the side of the real Agg node; these nodes don't
 * participate in the plan directly, but they are both a convenient way to
 * represent the required data and a convenient way to account for the costs
 * of execution.
 *
 * rollup_groupclauses and rollup_lists are destroyed by this function.
 */
static Plan *
build_grouping_chain(PlannerInfo *root,
					 Query *parse,
					 List *tlist,
					 bool need_sort_for_grouping,
					 List *rollup_groupclauses,
					 List *rollup_lists,
					 AttrNumber *groupColIdx,
					 AggClauseCosts *agg_costs,
					 long numGroups,
					 Plan *result_plan)
{
	AttrNumber *top_grpColIdx = groupColIdx;
	List	   *chain = NIL;

	/*
	 * Prepare the grpColIdx for the real Agg node first, because we may need
	 * it for sorting
	 */
	if (list_length(rollup_groupclauses) > 1)
	{
		Assert(rollup_lists && llast(rollup_lists));

		top_grpColIdx =
			remap_groupColIdx(root, llast(rollup_groupclauses));
	}

	/*
	 * If we need a Sort operation on the input, generate that.
	 */
	if (need_sort_for_grouping)
	{
		result_plan = (Plan *)
			make_sort_from_groupcols(root,
									 llast(rollup_groupclauses),
									 top_grpColIdx,
									 result_plan);
	}

	/*
	 * Generate the side nodes that describe the other sort and group
	 * operations besides the top one.
	 */
	while (list_length(rollup_groupclauses) > 1)
	{
		List	   *groupClause = linitial(rollup_groupclauses);
		List	   *gsets = linitial(rollup_lists);
		AttrNumber *new_grpColIdx;
		Plan	   *sort_plan;
		Plan	   *agg_plan;

		Assert(groupClause);
		Assert(gsets);

		new_grpColIdx = remap_groupColIdx(root, groupClause);

		sort_plan = (Plan *)
			make_sort_from_groupcols(root,
									 groupClause,
									 new_grpColIdx,
									 result_plan);

		/*
		 * sort_plan includes the cost of result_plan over again, which is not
		 * what we want (since it's not actually running that plan). So
		 * correct the cost figures.
		 */

		sort_plan->startup_cost -= result_plan->total_cost;
		sort_plan->total_cost -= result_plan->total_cost;

		agg_plan = (Plan *) make_agg(root,
									 tlist,
									 (List *) parse->havingQual,
									 AGG_SORTED,
									 agg_costs,
									 list_length(linitial(gsets)),
									 new_grpColIdx,
									 extract_grouping_ops(groupClause),
									 gsets,
									 numGroups,
									 sort_plan);

		sort_plan->lefttree = NULL;

		chain = lappend(chain, agg_plan);

		if (rollup_lists)
			rollup_lists = list_delete_first(rollup_lists);

		rollup_groupclauses = list_delete_first(rollup_groupclauses);
	}

	/*
	 * Now make the final Agg node
	 */
	{
		List	   *groupClause = linitial(rollup_groupclauses);
		List	   *gsets = rollup_lists ? linitial(rollup_lists) : NIL;
		int			numGroupCols;
		ListCell   *lc;

		if (gsets)
			numGroupCols = list_length(linitial(gsets));
		else
			numGroupCols = list_length(parse->groupClause);

		result_plan = (Plan *) make_agg(root,
										tlist,
										(List *) parse->havingQual,
								 (numGroupCols > 0) ? AGG_SORTED : AGG_PLAIN,
										agg_costs,
										numGroupCols,
										top_grpColIdx,
										extract_grouping_ops(groupClause),
										gsets,
										numGroups,
										result_plan);

		((Agg *) result_plan)->chain = chain;

		/*
		 * Add the additional costs. But only the total costs count, since the
		 * additional sorts aren't run on startup.
		 */
		foreach(lc, chain)
		{
			Plan	   *subplan = lfirst(lc);

			result_plan->total_cost += subplan->total_cost;

			/*
			 * Nuke stuff we don't need to avoid bloating debug output.
			 */

			subplan->targetlist = NIL;
			subplan->qual = NIL;
			subplan->lefttree->targetlist = NIL;
		}
	}

	return result_plan;
}

/*
 * add_tlist_costs_to_plan
 *
 * Estimate the execution costs associated with evaluating the targetlist
 * expressions, and add them to the cost estimates for the Plan node.
 *
 * If the tlist contains set-returning functions, also inflate the Plan's cost
 * and plan_rows estimates accordingly.  (Hence, this must be called *after*
 * any logic that uses plan_rows to, eg, estimate qual evaluation costs.)
 *
 * Note: during initial stages of planning, we mostly consider plan nodes with
 * "flat" tlists, containing just Vars.  So their evaluation cost is zero
 * according to the model used by cost_qual_eval() (or if you prefer, the cost
 * is factored into cpu_tuple_cost).  Thus we can avoid accounting for tlist
 * cost throughout query_planner() and subroutines.  But once we apply a
 * tlist that might contain actual operators, sub-selects, etc, we'd better
 * account for its cost.  Any set-returning functions in the tlist must also
 * affect the estimated rowcount.
 *
 * Once grouping_planner() has applied a general tlist to the topmost
 * scan/join plan node, any tlist eval cost for added-on nodes should be
 * accounted for as we create those nodes.  Presently, of the node types we
 * can add on later, only Agg, WindowAgg, and Group project new tlists (the
 * rest just copy their input tuples) --- so make_agg(), make_windowagg() and
 * make_group() are responsible for calling this function to account for their
 * tlist costs.
 */
void
add_tlist_costs_to_plan(PlannerInfo *root, Plan *plan, List *tlist)
{
	QualCost	tlist_cost;
	double		tlist_rows;

	cost_qual_eval(&tlist_cost, tlist, root);
	plan->startup_cost += tlist_cost.startup;
	plan->total_cost += tlist_cost.startup +
		tlist_cost.per_tuple * plan->plan_rows;

	tlist_rows = tlist_returns_set_rows(tlist);
	if (tlist_rows > 1)
	{
		/*
		 * We assume that execution costs of the tlist proper were all
		 * accounted for by cost_qual_eval.  However, it still seems
		 * appropriate to charge something more for the executor's general
		 * costs of processing the added tuples.  The cost is probably less
		 * than cpu_tuple_cost, though, so we arbitrarily use half of that.
		 */
		plan->total_cost += plan->plan_rows * (tlist_rows - 1) *
			cpu_tuple_cost / 2;

		plan->plan_rows *= tlist_rows;
	}
}

/*
 * Detect whether a plan node is a "dummy" plan created when a relation
 * is deemed not to need scanning due to constraint exclusion.
 *
 * Currently, such dummy plans are Result nodes with constant FALSE
 * filter quals (see set_dummy_rel_pathlist and create_append_plan).
 *
 * XXX this probably ought to be somewhere else, but not clear where.
 */
bool
is_dummy_plan(Plan *plan)
{
	if (IsA(plan, Result))
	{
		List	   *rcqual = (List *) ((Result *) plan)->resconstantqual;

		if (list_length(rcqual) == 1)
		{
			Const	   *constqual = (Const *) linitial(rcqual);

			if (constqual && IsA(constqual, Const))
			{
				if (!constqual->constisnull &&
					!DatumGetBool(constqual->constvalue))
					return true;
			}
		}
	}
	return false;
}

/*
 * Create a bitmapset of the RT indexes of live base relations
 *
 * Helper for preprocess_rowmarks ... at this point in the proceedings,
 * the only good way to distinguish baserels from appendrel children
 * is to see what is in the join tree.
 */
static Bitmapset *
get_base_rel_indexes(Node *jtnode)
{
	Bitmapset  *result;

	if (jtnode == NULL)
		return NULL;
	if (IsA(jtnode, RangeTblRef))
	{
		int			varno = ((RangeTblRef *) jtnode)->rtindex;

		result = bms_make_singleton(varno);
	}
	else if (IsA(jtnode, FromExpr))
	{
		FromExpr   *f = (FromExpr *) jtnode;
		ListCell   *l;

		result = NULL;
		foreach(l, f->fromlist)
			result = bms_join(result,
							  get_base_rel_indexes(lfirst(l)));
	}
	else if (IsA(jtnode, JoinExpr))
	{
		JoinExpr   *j = (JoinExpr *) jtnode;

		result = bms_join(get_base_rel_indexes(j->larg),
						  get_base_rel_indexes(j->rarg));
	}
	else
	{
		elog(ERROR, "unrecognized node type: %d",
			 (int) nodeTag(jtnode));
		result = NULL;			/* keep compiler quiet */
	}
	return result;
}

/*
 * preprocess_rowmarks - set up PlanRowMarks if needed
 */
static void
preprocess_rowmarks(PlannerInfo *root)
{
	Query	   *parse = root->parse;
	Bitmapset  *rels;
	List	   *prowmarks;
	ListCell   *l;
	int			i;

	if (parse->rowMarks)
	{
		/*
		 * We've got trouble if FOR [KEY] UPDATE/SHARE appears inside
		 * grouping, since grouping renders a reference to individual tuple
		 * CTIDs invalid.  This is also checked at parse time, but that's
		 * insufficient because of rule substitution, query pullup, etc.
		 */
		CheckSelectLocking(parse, ((RowMarkClause *)
								   linitial(parse->rowMarks))->strength);
	}
	else
	{
		/*
		 * We only need rowmarks for UPDATE, DELETE, or FOR [KEY]
		 * UPDATE/SHARE.
		 */
		if (parse->commandType != CMD_UPDATE &&
			parse->commandType != CMD_DELETE)
			return;
	}

	/*
	 * We need to have rowmarks for all base relations except the target. We
	 * make a bitmapset of all base rels and then remove the items we don't
	 * need or have FOR [KEY] UPDATE/SHARE marks for.
	 */
	rels = get_base_rel_indexes((Node *) parse->jointree);
	if (parse->resultRelation)
		rels = bms_del_member(rels, parse->resultRelation);

	/*
	 * Convert RowMarkClauses to PlanRowMark representation.
	 */
	prowmarks = NIL;
	foreach(l, parse->rowMarks)
	{
		RowMarkClause *rc = (RowMarkClause *) lfirst(l);
		RangeTblEntry *rte = rt_fetch(rc->rti, parse->rtable);
		PlanRowMark *newrc;

		/*
		 * Currently, it is syntactically impossible to have FOR UPDATE et al
		 * applied to an update/delete target rel.  If that ever becomes
		 * possible, we should drop the target from the PlanRowMark list.
		 */
		Assert(rc->rti != parse->resultRelation);

		/*
		 * Ignore RowMarkClauses for subqueries; they aren't real tables and
		 * can't support true locking.  Subqueries that got flattened into the
		 * main query should be ignored completely.  Any that didn't will get
		 * ROW_MARK_COPY items in the next loop.
		 */
		if (rte->rtekind != RTE_RELATION)
			continue;

		rels = bms_del_member(rels, rc->rti);

		newrc = makeNode(PlanRowMark);
		newrc->rti = newrc->prti = rc->rti;
		newrc->rowmarkId = ++(root->glob->lastRowMarkId);
		newrc->markType = select_rowmark_type(rte, rc->strength);
		newrc->allMarkTypes = (1 << newrc->markType);
		newrc->strength = rc->strength;
		newrc->waitPolicy = rc->waitPolicy;
		newrc->isParent = false;

		prowmarks = lappend(prowmarks, newrc);
	}

	/*
	 * Now, add rowmarks for any non-target, non-locked base relations.
	 */
	i = 0;
	foreach(l, parse->rtable)
	{
		RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
		PlanRowMark *newrc;

		i++;
		if (!bms_is_member(i, rels))
			continue;

		newrc = makeNode(PlanRowMark);
		newrc->rti = newrc->prti = i;
		newrc->rowmarkId = ++(root->glob->lastRowMarkId);
		newrc->markType = select_rowmark_type(rte, LCS_NONE);
		newrc->allMarkTypes = (1 << newrc->markType);
		newrc->strength = LCS_NONE;
		newrc->waitPolicy = LockWaitBlock;		/* doesn't matter */
		newrc->isParent = false;

		prowmarks = lappend(prowmarks, newrc);
	}

	root->rowMarks = prowmarks;
}

/*
 * Select RowMarkType to use for a given table
 */
RowMarkType
select_rowmark_type(RangeTblEntry *rte, LockClauseStrength strength)
{
	if (rte->rtekind != RTE_RELATION)
	{
		/* If it's not a table at all, use ROW_MARK_COPY */
		return ROW_MARK_COPY;
	}
	else if (rte->relkind == RELKIND_FOREIGN_TABLE)
	{
		/* Let the FDW select the rowmark type, if it wants to */
		FdwRoutine *fdwroutine = GetFdwRoutineByRelId(rte->relid);

		if (fdwroutine->GetForeignRowMarkType != NULL)
			return fdwroutine->GetForeignRowMarkType(rte, strength);
		/* Otherwise, use ROW_MARK_COPY by default */
		return ROW_MARK_COPY;
	}
	else
	{
		/* Regular table, apply the appropriate lock type */
		switch (strength)
		{
			case LCS_NONE:

				/*
				 * We don't need a tuple lock, only the ability to re-fetch
				 * the row.  Regular tables support ROW_MARK_REFERENCE, but if
				 * this RTE has security barrier quals, it will be turned into
				 * a subquery during planning, so use ROW_MARK_COPY.
				 *
				 * This is only necessary for LCS_NONE, since real tuple locks
				 * on an RTE with security barrier quals are supported by
				 * pushing the lock down into the subquery --- see
				 * expand_security_qual.
				 */
				if (rte->securityQuals != NIL)
					return ROW_MARK_COPY;
				return ROW_MARK_REFERENCE;
				break;
			case LCS_FORKEYSHARE:
				return ROW_MARK_KEYSHARE;
				break;
			case LCS_FORSHARE:
				return ROW_MARK_SHARE;
				break;
			case LCS_FORNOKEYUPDATE:
				return ROW_MARK_NOKEYEXCLUSIVE;
				break;
			case LCS_FORUPDATE:
				return ROW_MARK_EXCLUSIVE;
				break;
		}
		elog(ERROR, "unrecognized LockClauseStrength %d", (int) strength);
		return ROW_MARK_EXCLUSIVE;		/* keep compiler quiet */
	}
}

/*
 * preprocess_limit - do pre-estimation for LIMIT and/or OFFSET clauses
 *
 * We try to estimate the values of the LIMIT/OFFSET clauses, and pass the
 * results back in *count_est and *offset_est.  These variables are set to
 * 0 if the corresponding clause is not present, and -1 if it's present
 * but we couldn't estimate the value for it.  (The "0" convention is OK
 * for OFFSET but a little bit bogus for LIMIT: effectively we estimate
 * LIMIT 0 as though it were LIMIT 1.  But this is in line with the planner's
 * usual practice of never estimating less than one row.)  These values will
 * be passed to make_limit, which see if you change this code.
 *
 * The return value is the suitably adjusted tuple_fraction to use for
 * planning the query.  This adjustment is not overridable, since it reflects
 * plan actions that grouping_planner() will certainly take, not assumptions
 * about context.
 */
static double
preprocess_limit(PlannerInfo *root, double tuple_fraction,
				 int64 *offset_est, int64 *count_est)
{
	Query	   *parse = root->parse;
	Node	   *est;
	double		limit_fraction;

	/* Should not be called unless LIMIT or OFFSET */
	Assert(parse->limitCount || parse->limitOffset);

	/*
	 * Try to obtain the clause values.  We use estimate_expression_value
	 * primarily because it can sometimes do something useful with Params.
	 */
	if (parse->limitCount)
	{
		est = estimate_expression_value(root, parse->limitCount);
		if (est && IsA(est, Const))
		{
			if (((Const *) est)->constisnull)
			{
				/* NULL indicates LIMIT ALL, ie, no limit */
				*count_est = 0; /* treat as not present */
			}
			else
			{
				*count_est = DatumGetInt64(((Const *) est)->constvalue);
				if (*count_est <= 0)
					*count_est = 1;		/* force to at least 1 */
			}
		}
		else
			*count_est = -1;	/* can't estimate */
	}
	else
		*count_est = 0;			/* not present */

	if (parse->limitOffset)
	{
		est = estimate_expression_value(root, parse->limitOffset);
		if (est && IsA(est, Const))
		{
			if (((Const *) est)->constisnull)
			{
				/* Treat NULL as no offset; the executor will too */
				*offset_est = 0;	/* treat as not present */
			}
			else
			{
				*offset_est = DatumGetInt64(((Const *) est)->constvalue);
				if (*offset_est < 0)
					*offset_est = 0;	/* treat as not present */
			}
		}
		else
			*offset_est = -1;	/* can't estimate */
	}
	else
		*offset_est = 0;		/* not present */

	if (*count_est != 0)
	{
		/*
		 * A LIMIT clause limits the absolute number of tuples returned.
		 * However, if it's not a constant LIMIT then we have to guess; for
		 * lack of a better idea, assume 10% of the plan's result is wanted.
		 */
		if (*count_est < 0 || *offset_est < 0)
		{
			/* LIMIT or OFFSET is an expression ... punt ... */
			limit_fraction = 0.10;
		}
		else
		{
			/* LIMIT (plus OFFSET, if any) is max number of tuples needed */
			limit_fraction = (double) *count_est + (double) *offset_est;
		}

		/*
		 * If we have absolute limits from both caller and LIMIT, use the
		 * smaller value; likewise if they are both fractional.  If one is
		 * fractional and the other absolute, we can't easily determine which
		 * is smaller, but we use the heuristic that the absolute will usually
		 * be smaller.
		 */
		if (tuple_fraction >= 1.0)
		{
			if (limit_fraction >= 1.0)
			{
				/* both absolute */
				tuple_fraction = Min(tuple_fraction, limit_fraction);
			}
			else
			{
				/* caller absolute, limit fractional; use caller's value */
			}
		}
		else if (tuple_fraction > 0.0)
		{
			if (limit_fraction >= 1.0)
			{
				/* caller fractional, limit absolute; use limit */
				tuple_fraction = limit_fraction;
			}
			else
			{
				/* both fractional */
				tuple_fraction = Min(tuple_fraction, limit_fraction);
			}
		}
		else
		{
			/* no info from caller, just use limit */
			tuple_fraction = limit_fraction;
		}
	}
	else if (*offset_est != 0 && tuple_fraction > 0.0)
	{
		/*
		 * We have an OFFSET but no LIMIT.  This acts entirely differently
		 * from the LIMIT case: here, we need to increase rather than decrease
		 * the caller's tuple_fraction, because the OFFSET acts to cause more
		 * tuples to be fetched instead of fewer.  This only matters if we got
		 * a tuple_fraction > 0, however.
		 *
		 * As above, use 10% if OFFSET is present but unestimatable.
		 */
		if (*offset_est < 0)
			limit_fraction = 0.10;
		else
			limit_fraction = (double) *offset_est;

		/*
		 * If we have absolute counts from both caller and OFFSET, add them
		 * together; likewise if they are both fractional.  If one is
		 * fractional and the other absolute, we want to take the larger, and
		 * we heuristically assume that's the fractional one.
		 */
		if (tuple_fraction >= 1.0)
		{
			if (limit_fraction >= 1.0)
			{
				/* both absolute, so add them together */
				tuple_fraction += limit_fraction;
			}
			else
			{
				/* caller absolute, limit fractional; use limit */
				tuple_fraction = limit_fraction;
			}
		}
		else
		{
			if (limit_fraction >= 1.0)
			{
				/* caller fractional, limit absolute; use caller's value */
			}
			else
			{
				/* both fractional, so add them together */
				tuple_fraction += limit_fraction;
				if (tuple_fraction >= 1.0)
					tuple_fraction = 0.0;		/* assume fetch all */
			}
		}
	}

	return tuple_fraction;
}

/*
 * limit_needed - do we actually need a Limit plan node?
 *
 * If we have constant-zero OFFSET and constant-null LIMIT, we can skip adding
 * a Limit node.  This is worth checking for because "OFFSET 0" is a common
 * locution for an optimization fence.  (Because other places in the planner
 * merely check whether parse->limitOffset isn't NULL, it will still work as
 * an optimization fence --- we're just suppressing unnecessary run-time
 * overhead.)
 *
 * This might look like it could be merged into preprocess_limit, but there's
 * a key distinction: here we need hard constants in OFFSET/LIMIT, whereas
 * in preprocess_limit it's good enough to consider estimated values.
 */
static bool
limit_needed(Query *parse)
{
	Node	   *node;

	node = parse->limitCount;
	if (node)
	{
		if (IsA(node, Const))
		{
			/* NULL indicates LIMIT ALL, ie, no limit */
			if (!((Const *) node)->constisnull)
				return true;	/* LIMIT with a constant value */
		}
		else
			return true;		/* non-constant LIMIT */
	}

	node = parse->limitOffset;
	if (node)
	{
		if (IsA(node, Const))
		{
			/* Treat NULL as no offset; the executor would too */
			if (!((Const *) node)->constisnull)
			{
				int64		offset = DatumGetInt64(((Const *) node)->constvalue);

				if (offset != 0)
					return true;	/* OFFSET with a nonzero value */
			}
		}
		else
			return true;		/* non-constant OFFSET */
	}

	return false;				/* don't need a Limit plan node */
}


/*
 * preprocess_groupclause - do preparatory work on GROUP BY clause
 *
 * The idea here is to adjust the ordering of the GROUP BY elements
 * (which in itself is semantically insignificant) to match ORDER BY,
 * thereby allowing a single sort operation to both implement the ORDER BY
 * requirement and set up for a Unique step that implements GROUP BY.
 *
 * In principle it might be interesting to consider other orderings of the
 * GROUP BY elements, which could match the sort ordering of other
 * possible plans (eg an indexscan) and thereby reduce cost.  We don't
 * bother with that, though.  Hashed grouping will frequently win anyway.
 *
 * Note: we need no comparable processing of the distinctClause because
 * the parser already enforced that that matches ORDER BY.
 *
 * For grouping sets, the order of items is instead forced to agree with that
 * of the grouping set (and items not in the grouping set are skipped). The
 * work of sorting the order of grouping set elements to match the ORDER BY if
 * possible is done elsewhere.
 */
static List *
preprocess_groupclause(PlannerInfo *root, List *force)
{
	Query	   *parse = root->parse;
	List	   *new_groupclause = NIL;
	bool		partial_match;
	ListCell   *sl;
	ListCell   *gl;

	/* For grouping sets, we need to force the ordering */
	if (force)
	{
		foreach(sl, force)
		{
			Index		ref = lfirst_int(sl);
			SortGroupClause *cl = get_sortgroupref_clause(ref, parse->groupClause);

			new_groupclause = lappend(new_groupclause, cl);
		}

		return new_groupclause;
	}

	/* If no ORDER BY, nothing useful to do here */
	if (parse->sortClause == NIL)
		return parse->groupClause;

	/*
	 * Scan the ORDER BY clause and construct a list of matching GROUP BY
	 * items, but only as far as we can make a matching prefix.
	 *
	 * This code assumes that the sortClause contains no duplicate items.
	 */
	foreach(sl, parse->sortClause)
	{
		SortGroupClause *sc = (SortGroupClause *) lfirst(sl);

		foreach(gl, parse->groupClause)
		{
			SortGroupClause *gc = (SortGroupClause *) lfirst(gl);

			if (equal(gc, sc))
			{
				new_groupclause = lappend(new_groupclause, gc);
				break;
			}
		}
		if (gl == NULL)
			break;				/* no match, so stop scanning */
	}

	/* Did we match all of the ORDER BY list, or just some of it? */
	partial_match = (sl != NULL);

	/* If no match at all, no point in reordering GROUP BY */
	if (new_groupclause == NIL)
		return parse->groupClause;

	/*
	 * Add any remaining GROUP BY items to the new list, but only if we were
	 * able to make a complete match.  In other words, we only rearrange the
	 * GROUP BY list if the result is that one list is a prefix of the other
	 * --- otherwise there's no possibility of a common sort.  Also, give up
	 * if there are any non-sortable GROUP BY items, since then there's no
	 * hope anyway.
	 */
	foreach(gl, parse->groupClause)
	{
		SortGroupClause *gc = (SortGroupClause *) lfirst(gl);

		if (list_member_ptr(new_groupclause, gc))
			continue;			/* it matched an ORDER BY item */
		if (partial_match)
			return parse->groupClause;	/* give up, no common sort possible */
		if (!OidIsValid(gc->sortop))
			return parse->groupClause;	/* give up, GROUP BY can't be sorted */
		new_groupclause = lappend(new_groupclause, gc);
	}

	/* Success --- install the rearranged GROUP BY list */
	Assert(list_length(parse->groupClause) == list_length(new_groupclause));
	return new_groupclause;
}

/*
 * Extract lists of grouping sets that can be implemented using a single
 * rollup-type aggregate pass each. Returns a list of lists of grouping sets.
 *
 * Input must be sorted with smallest sets first. Result has each sublist
 * sorted with smallest sets first.
 *
 * We want to produce the absolute minimum possible number of lists here to
 * avoid excess sorts. Fortunately, there is an algorithm for this; the problem
 * of finding the minimal partition of a partially-ordered set into chains
 * (which is what we need, taking the list of grouping sets as a poset ordered
 * by set inclusion) can be mapped to the problem of finding the maximum
 * cardinality matching on a bipartite graph, which is solvable in polynomial
 * time with a worst case of no worse than O(n^2.5) and usually much
 * better. Since our N is at most 4096, we don't need to consider fallbacks to
 * heuristic or approximate methods.  (Planning time for a 12-d cube is under
 * half a second on my modest system even with optimization off and assertions
 * on.)
 */
static List *
extract_rollup_sets(List *groupingSets)
{
	int			num_sets_raw = list_length(groupingSets);
	int			num_empty = 0;
	int			num_sets = 0;	/* distinct sets */
	int			num_chains = 0;
	List	   *result = NIL;
	List	  **results;
	List	  **orig_sets;
	Bitmapset **set_masks;
	int		   *chains;
	short	  **adjacency;
	short	   *adjacency_buf;
	BipartiteMatchState *state;
	int			i;
	int			j;
	int			j_size;
	ListCell   *lc1 = list_head(groupingSets);
	ListCell   *lc;

	/*
	 * Start by stripping out empty sets.  The algorithm doesn't require this,
	 * but the planner currently needs all empty sets to be returned in the
	 * first list, so we strip them here and add them back after.
	 */
	while (lc1 && lfirst(lc1) == NIL)
	{
		++num_empty;
		lc1 = lnext(lc1);
	}

	/* bail out now if it turns out that all we had were empty sets. */
	if (!lc1)
		return list_make1(groupingSets);

	/*----------
	 * We don't strictly need to remove duplicate sets here, but if we don't,
	 * they tend to become scattered through the result, which is a bit
	 * confusing (and irritating if we ever decide to optimize them out).
	 * So we remove them here and add them back after.
	 *
	 * For each non-duplicate set, we fill in the following:
	 *
	 * orig_sets[i] = list of the original set lists
	 * set_masks[i] = bitmapset for testing inclusion
	 * adjacency[i] = array [n, v1, v2, ... vn] of adjacency indices
	 *
	 * chains[i] will be the result group this set is assigned to.
	 *
	 * We index all of these from 1 rather than 0 because it is convenient
	 * to leave 0 free for the NIL node in the graph algorithm.
	 *----------
	 */
	orig_sets = palloc0((num_sets_raw + 1) * sizeof(List *));
	set_masks = palloc0((num_sets_raw + 1) * sizeof(Bitmapset *));
	adjacency = palloc0((num_sets_raw + 1) * sizeof(short *));
	adjacency_buf = palloc((num_sets_raw + 1) * sizeof(short));

	j_size = 0;
	j = 0;
	i = 1;

	for_each_cell(lc, lc1)
	{
		List	   *candidate = lfirst(lc);
		Bitmapset  *candidate_set = NULL;
		ListCell   *lc2;
		int			dup_of = 0;

		foreach(lc2, candidate)
		{
			candidate_set = bms_add_member(candidate_set, lfirst_int(lc2));
		}

		/* we can only be a dup if we're the same length as a previous set */
		if (j_size == list_length(candidate))
		{
			int			k;

			for (k = j; k < i; ++k)
			{
				if (bms_equal(set_masks[k], candidate_set))
				{
					dup_of = k;
					break;
				}
			}
		}
		else if (j_size < list_length(candidate))
		{
			j_size = list_length(candidate);
			j = i;
		}

		if (dup_of > 0)
		{
			orig_sets[dup_of] = lappend(orig_sets[dup_of], candidate);
			bms_free(candidate_set);
		}
		else
		{
			int			k;
			int			n_adj = 0;

			orig_sets[i] = list_make1(candidate);
			set_masks[i] = candidate_set;

			/* fill in adjacency list; no need to compare equal-size sets */

			for (k = j - 1; k > 0; --k)
			{
				if (bms_is_subset(set_masks[k], candidate_set))
					adjacency_buf[++n_adj] = k;
			}

			if (n_adj > 0)
			{
				adjacency_buf[0] = n_adj;
				adjacency[i] = palloc((n_adj + 1) * sizeof(short));
				memcpy(adjacency[i], adjacency_buf, (n_adj + 1) * sizeof(short));
			}
			else
				adjacency[i] = NULL;

			++i;
		}
	}

	num_sets = i - 1;

	/*
	 * Apply the graph matching algorithm to do the work.
	 */
	state = BipartiteMatch(num_sets, num_sets, adjacency);

	/*
	 * Now, the state->pair* fields have the info we need to assign sets to
	 * chains. Two sets (u,v) belong to the same chain if pair_uv[u] = v or
	 * pair_vu[v] = u (both will be true, but we check both so that we can do
	 * it in one pass)
	 */
	chains = palloc0((num_sets + 1) * sizeof(int));

	for (i = 1; i <= num_sets; ++i)
	{
		int			u = state->pair_vu[i];
		int			v = state->pair_uv[i];

		if (u > 0 && u < i)
			chains[i] = chains[u];
		else if (v > 0 && v < i)
			chains[i] = chains[v];
		else
			chains[i] = ++num_chains;
	}

	/* build result lists. */
	results = palloc0((num_chains + 1) * sizeof(List *));

	for (i = 1; i <= num_sets; ++i)
	{
		int			c = chains[i];

		Assert(c > 0);

		results[c] = list_concat(results[c], orig_sets[i]);
	}

	/* push any empty sets back on the first list. */
	while (num_empty-- > 0)
		results[1] = lcons(NIL, results[1]);

	/* make result list */
	for (i = 1; i <= num_chains; ++i)
		result = lappend(result, results[i]);

	/*
	 * Free all the things.
	 *
	 * (This is over-fussy for small sets but for large sets we could have
	 * tied up a nontrivial amount of memory.)
	 */
	BipartiteMatchFree(state);
	pfree(results);
	pfree(chains);
	for (i = 1; i <= num_sets; ++i)
		if (adjacency[i])
			pfree(adjacency[i]);
	pfree(adjacency);
	pfree(adjacency_buf);
	pfree(orig_sets);
	for (i = 1; i <= num_sets; ++i)
		bms_free(set_masks[i]);
	pfree(set_masks);

	return result;
}

/*
 * Reorder the elements of a list of grouping sets such that they have correct
 * prefix relationships.
 *
 * The input must be ordered with smallest sets first; the result is returned
 * with largest sets first.
 *
 * If we're passed in a sortclause, we follow its order of columns to the
 * extent possible, to minimize the chance that we add unnecessary sorts.
 * (We're trying here to ensure that GROUPING SETS ((a,b,c),(c)) ORDER BY c,b,a
 * gets implemented in one pass.)
 */
static List *
reorder_grouping_sets(List *groupingsets, List *sortclause)
{
	ListCell   *lc;
	ListCell   *lc2;
	List	   *previous = NIL;
	List	   *result = NIL;

	foreach(lc, groupingsets)
	{
		List	   *candidate = lfirst(lc);
		List	   *new_elems = list_difference_int(candidate, previous);

		if (list_length(new_elems) > 0)
		{
			while (list_length(sortclause) > list_length(previous))
			{
				SortGroupClause *sc = list_nth(sortclause, list_length(previous));
				int			ref = sc->tleSortGroupRef;

				if (list_member_int(new_elems, ref))
				{
					previous = lappend_int(previous, ref);
					new_elems = list_delete_int(new_elems, ref);
				}
				else
				{
					/* diverged from the sortclause; give up on it */
					sortclause = NIL;
					break;
				}
			}

			foreach(lc2, new_elems)
			{
				previous = lappend_int(previous, lfirst_int(lc2));
			}
		}

		result = lcons(list_copy(previous), result);
		list_free(new_elems);
	}

	list_free(previous);

	return result;
}

/*
 * Compute query_pathkeys and other pathkeys during plan generation
 */
static void
standard_qp_callback(PlannerInfo *root, void *extra)
{
	Query	   *parse = root->parse;
	standard_qp_extra *qp_extra = (standard_qp_extra *) extra;
	List	   *tlist = qp_extra->tlist;
	List	   *activeWindows = qp_extra->activeWindows;

	/*
	 * Calculate pathkeys that represent grouping/ordering requirements.  The
	 * sortClause is certainly sort-able, but GROUP BY and DISTINCT might not
	 * be, in which case we just leave their pathkeys empty.
	 */
	if (qp_extra->groupClause &&
		grouping_is_sortable(qp_extra->groupClause))
		root->group_pathkeys =
			make_pathkeys_for_sortclauses(root,
										  qp_extra->groupClause,
										  tlist);
	else
		root->group_pathkeys = NIL;

	/* We consider only the first (bottom) window in pathkeys logic */
	if (activeWindows != NIL)
	{
		WindowClause *wc = (WindowClause *) linitial(activeWindows);

		root->window_pathkeys = make_pathkeys_for_window(root,
														 wc,
														 tlist);
	}
	else
		root->window_pathkeys = NIL;

	if (parse->distinctClause &&
		grouping_is_sortable(parse->distinctClause))
		root->distinct_pathkeys =
			make_pathkeys_for_sortclauses(root,
										  parse->distinctClause,
										  tlist);
	else
		root->distinct_pathkeys = NIL;

	root->sort_pathkeys =
		make_pathkeys_for_sortclauses(root,
									  parse->sortClause,
									  tlist);

	/*
	 * Figure out whether we want a sorted result from query_planner.
	 *
	 * If we have a sortable GROUP BY clause, then we want a result sorted
	 * properly for grouping.  Otherwise, if we have window functions to
	 * evaluate, we try to sort for the first window.  Otherwise, if there's a
	 * sortable DISTINCT clause that's more rigorous than the ORDER BY clause,
	 * we try to produce output that's sufficiently well sorted for the
	 * DISTINCT.  Otherwise, if there is an ORDER BY clause, we want to sort
	 * by the ORDER BY clause.
	 *
	 * Note: if we have both ORDER BY and GROUP BY, and ORDER BY is a superset
	 * of GROUP BY, it would be tempting to request sort by ORDER BY --- but
	 * that might just leave us failing to exploit an available sort order at
	 * all.  Needs more thought.  The choice for DISTINCT versus ORDER BY is
	 * much easier, since we know that the parser ensured that one is a
	 * superset of the other.
	 */
	if (root->group_pathkeys)
		root->query_pathkeys = root->group_pathkeys;
	else if (root->window_pathkeys)
		root->query_pathkeys = root->window_pathkeys;
	else if (list_length(root->distinct_pathkeys) >
			 list_length(root->sort_pathkeys))
		root->query_pathkeys = root->distinct_pathkeys;
	else if (root->sort_pathkeys)
		root->query_pathkeys = root->sort_pathkeys;
	else
		root->query_pathkeys = NIL;
}

/*
 * choose_hashed_grouping - should we use hashed grouping?
 *
 * Returns TRUE to select hashing, FALSE to select sorting.
 */
static bool
choose_hashed_grouping(PlannerInfo *root,
					   double tuple_fraction, double limit_tuples,
					   double path_rows, int path_width,
					   Path *cheapest_path, Path *sorted_path,
					   double dNumGroups, AggClauseCosts *agg_costs)
{
	Query	   *parse = root->parse;
	int			numGroupCols = list_length(parse->groupClause);
	bool		can_hash;
	bool		can_sort;
	Size		hashentrysize;
	List	   *target_pathkeys;
	List	   *current_pathkeys;
	Path		hashed_p;
	Path		sorted_p;

	/*
	 * Executor doesn't support hashed aggregation with DISTINCT or ORDER BY
	 * aggregates.  (Doing so would imply storing *all* the input values in
	 * the hash table, and/or running many sorts in parallel, either of which
	 * seems like a certain loser.)  We similarly don't support ordered-set
	 * aggregates in hashed aggregation, but that case is included in the
	 * numOrderedAggs count.
	 */
	can_hash = (agg_costs->numOrderedAggs == 0 &&
				grouping_is_hashable(parse->groupClause));
	can_sort = grouping_is_sortable(parse->groupClause);

	/* Quick out if only one choice is workable */
	if (!(can_hash && can_sort))
	{
		if (can_hash)
			return true;
		else if (can_sort)
			return false;
		else
			ereport(ERROR,
					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
					 errmsg("could not implement GROUP BY"),
					 errdetail("Some of the datatypes only support hashing, while others only support sorting.")));
	}

	/* Prefer sorting when enable_hashagg is off */
	if (!enable_hashagg)
		return false;

	/*
	 * Don't do it if it doesn't look like the hashtable will fit into
	 * work_mem.
	 */

	/* Estimate per-hash-entry space at tuple width... */
	hashentrysize = MAXALIGN(path_width) + MAXALIGN(SizeofMinimalTupleHeader);
	/* plus space for pass-by-ref transition values... */
	hashentrysize += agg_costs->transitionSpace;
	/* plus the per-hash-entry overhead */
	hashentrysize += hash_agg_entry_size(agg_costs->numAggs);

	if (hashentrysize * dNumGroups > work_mem * 1024L)
		return false;

	/*
	 * When we have both GROUP BY and DISTINCT, use the more-rigorous of
	 * DISTINCT and ORDER BY as the assumed required output sort order. This
	 * is an oversimplification because the DISTINCT might get implemented via
	 * hashing, but it's not clear that the case is common enough (or that our
	 * estimates are good enough) to justify trying to solve it exactly.
	 */
	if (list_length(root->distinct_pathkeys) >
		list_length(root->sort_pathkeys))
		target_pathkeys = root->distinct_pathkeys;
	else
		target_pathkeys = root->sort_pathkeys;

	/*
	 * See if the estimated cost is no more than doing it the other way. While
	 * avoiding the need for sorted input is usually a win, the fact that the
	 * output won't be sorted may be a loss; so we need to do an actual cost
	 * comparison.
	 *
	 * We need to consider cheapest_path + hashagg [+ final sort] versus
	 * either cheapest_path [+ sort] + group or agg [+ final sort] or
	 * presorted_path + group or agg [+ final sort] where brackets indicate a
	 * step that may not be needed.  We assume grouping_planner() will have
	 * passed us a presorted path only if it's a winner compared to
	 * cheapest_path for this purpose.
	 *
	 * These path variables are dummies that just hold cost fields; we don't
	 * make actual Paths for these steps.
	 */
	cost_agg(&hashed_p, root, AGG_HASHED, agg_costs,
			 numGroupCols, dNumGroups,
			 cheapest_path->startup_cost, cheapest_path->total_cost,
			 path_rows);
	/* Result of hashed agg is always unsorted */
	if (target_pathkeys)
		cost_sort(&hashed_p, root, target_pathkeys, hashed_p.total_cost,
				  dNumGroups, path_width,
				  0.0, work_mem, limit_tuples);

	if (sorted_path)
	{
		sorted_p.startup_cost = sorted_path->startup_cost;
		sorted_p.total_cost = sorted_path->total_cost;
		current_pathkeys = sorted_path->pathkeys;
	}
	else
	{
		sorted_p.startup_cost = cheapest_path->startup_cost;
		sorted_p.total_cost = cheapest_path->total_cost;
		current_pathkeys = cheapest_path->pathkeys;
	}
	if (!pathkeys_contained_in(root->group_pathkeys, current_pathkeys))
	{
		cost_sort(&sorted_p, root, root->group_pathkeys, sorted_p.total_cost,
				  path_rows, path_width,
				  0.0, work_mem, -1.0);
		current_pathkeys = root->group_pathkeys;
	}

	if (parse->hasAggs)
		cost_agg(&sorted_p, root, AGG_SORTED, agg_costs,
				 numGroupCols, dNumGroups,
				 sorted_p.startup_cost, sorted_p.total_cost,
				 path_rows);
	else
		cost_group(&sorted_p, root, numGroupCols, dNumGroups,
				   sorted_p.startup_cost, sorted_p.total_cost,
				   path_rows);
	/* The Agg or Group node will preserve ordering */
	if (target_pathkeys &&
		!pathkeys_contained_in(target_pathkeys, current_pathkeys))
		cost_sort(&sorted_p, root, target_pathkeys, sorted_p.total_cost,
				  dNumGroups, path_width,
				  0.0, work_mem, limit_tuples);

	/*
	 * Now make the decision using the top-level tuple fraction.
	 */
	if (compare_fractional_path_costs(&hashed_p, &sorted_p,
									  tuple_fraction) < 0)
	{
		/* Hashed is cheaper, so use it */
		return true;
	}
	return false;
}

/*
 * choose_hashed_distinct - should we use hashing for DISTINCT?
 *
 * This is fairly similar to choose_hashed_grouping, but there are enough
 * differences that it doesn't seem worth trying to unify the two functions.
 * (One difference is that we sometimes apply this after forming a Plan,
 * so the input alternatives can't be represented as Paths --- instead we
 * pass in the costs as individual variables.)
 *
 * But note that making the two choices independently is a bit bogus in
 * itself.  If the two could be combined into a single choice operation
 * it'd probably be better, but that seems far too unwieldy to be practical,
 * especially considering that the combination of GROUP BY and DISTINCT
 * isn't very common in real queries.  By separating them, we are giving
 * extra preference to using a sorting implementation when a common sort key
 * is available ... and that's not necessarily wrong anyway.
 *
 * Returns TRUE to select hashing, FALSE to select sorting.
 */
static bool
choose_hashed_distinct(PlannerInfo *root,
					   double tuple_fraction, double limit_tuples,
					   double path_rows, int path_width,
					   Cost cheapest_startup_cost, Cost cheapest_total_cost,
					   Cost sorted_startup_cost, Cost sorted_total_cost,
					   List *sorted_pathkeys,
					   double dNumDistinctRows)
{
	Query	   *parse = root->parse;
	int			numDistinctCols = list_length(parse->distinctClause);
	bool		can_sort;
	bool		can_hash;
	Size		hashentrysize;
	List	   *current_pathkeys;
	List	   *needed_pathkeys;
	Path		hashed_p;
	Path		sorted_p;

	/*
	 * If we have a sortable DISTINCT ON clause, we always use sorting. This
	 * enforces the expected behavior of DISTINCT ON.
	 */
	can_sort = grouping_is_sortable(parse->distinctClause);
	if (can_sort && parse->hasDistinctOn)
		return false;

	can_hash = grouping_is_hashable(parse->distinctClause);

	/* Quick out if only one choice is workable */
	if (!(can_hash && can_sort))
	{
		if (can_hash)
			return true;
		else if (can_sort)
			return false;
		else
			ereport(ERROR,
					(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
					 errmsg("could not implement DISTINCT"),
					 errdetail("Some of the datatypes only support hashing, while others only support sorting.")));
	}

	/* Prefer sorting when enable_hashagg is off */
	if (!enable_hashagg)
		return false;

	/*
	 * Don't do it if it doesn't look like the hashtable will fit into
	 * work_mem.
	 */

	/* Estimate per-hash-entry space at tuple width... */
	hashentrysize = MAXALIGN(path_width) + MAXALIGN(SizeofMinimalTupleHeader);
	/* plus the per-hash-entry overhead */
	hashentrysize += hash_agg_entry_size(0);

	if (hashentrysize * dNumDistinctRows > work_mem * 1024L)
		return false;

	/*
	 * See if the estimated cost is no more than doing it the other way. While
	 * avoiding the need for sorted input is usually a win, the fact that the
	 * output won't be sorted may be a loss; so we need to do an actual cost
	 * comparison.
	 *
	 * We need to consider cheapest_path + hashagg [+ final sort] versus
	 * sorted_path [+ sort] + group [+ final sort] where brackets indicate a
	 * step that may not be needed.
	 *
	 * These path variables are dummies that just hold cost fields; we don't
	 * make actual Paths for these steps.
	 */
	cost_agg(&hashed_p, root, AGG_HASHED, NULL,
			 numDistinctCols, dNumDistinctRows,
			 cheapest_startup_cost, cheapest_total_cost,
			 path_rows);

	/*
	 * Result of hashed agg is always unsorted, so if ORDER BY is present we
	 * need to charge for the final sort.
	 */
	if (parse->sortClause)
		cost_sort(&hashed_p, root, root->sort_pathkeys, hashed_p.total_cost,
				  dNumDistinctRows, path_width,
				  0.0, work_mem, limit_tuples);

	/*
	 * Now for the GROUP case.  See comments in grouping_planner about the
	 * sorting choices here --- this code should match that code.
	 */
	sorted_p.startup_cost = sorted_startup_cost;
	sorted_p.total_cost = sorted_total_cost;
	current_pathkeys = sorted_pathkeys;
	if (parse->hasDistinctOn &&
		list_length(root->distinct_pathkeys) <
		list_length(root->sort_pathkeys))
		needed_pathkeys = root->sort_pathkeys;
	else
		needed_pathkeys = root->distinct_pathkeys;
	if (!pathkeys_contained_in(needed_pathkeys, current_pathkeys))
	{
		if (list_length(root->distinct_pathkeys) >=
			list_length(root->sort_pathkeys))
			current_pathkeys = root->distinct_pathkeys;
		else
			current_pathkeys = root->sort_pathkeys;
		cost_sort(&sorted_p, root, current_pathkeys, sorted_p.total_cost,
				  path_rows, path_width,
				  0.0, work_mem, -1.0);
	}
	cost_group(&sorted_p, root, numDistinctCols, dNumDistinctRows,
			   sorted_p.startup_cost, sorted_p.total_cost,
			   path_rows);
	if (parse->sortClause &&
		!pathkeys_contained_in(root->sort_pathkeys, current_pathkeys))
		cost_sort(&sorted_p, root, root->sort_pathkeys, sorted_p.total_cost,
				  dNumDistinctRows, path_width,
				  0.0, work_mem, limit_tuples);

	/*
	 * Now make the decision using the top-level tuple fraction.
	 */
	if (compare_fractional_path_costs(&hashed_p, &sorted_p,
									  tuple_fraction) < 0)
	{
		/* Hashed is cheaper, so use it */
		return true;
	}
	return false;
}

/*
 * make_subplanTargetList
 *	  Generate appropriate target list when grouping is required.
 *
 * When grouping_planner inserts grouping or aggregation plan nodes
 * above the scan/join plan constructed by query_planner+create_plan,
 * we typically want the scan/join plan to emit a different target list
 * than the outer plan nodes should have.  This routine generates the
 * correct target list for the scan/join subplan.
 *
 * The initial target list passed from the parser already contains entries
 * for all ORDER BY and GROUP BY expressions, but it will not have entries
 * for variables used only in HAVING clauses; so we need to add those
 * variables to the subplan target list.  Also, we flatten all expressions
 * except GROUP BY items into their component variables; the other expressions
 * will be computed by the inserted nodes rather than by the subplan.
 * For example, given a query like
 *		SELECT a+b,SUM(c+d) FROM table GROUP BY a+b;
 * we want to pass this targetlist to the subplan:
 *		a+b,c,d
 * where the a+b target will be used by the Sort/Group steps, and the
 * other targets will be used for computing the final results.
 *
 * If we are grouping or aggregating, *and* there are no non-Var grouping
 * expressions, then the returned tlist is effectively dummy; we do not
 * need to force it to be evaluated, because all the Vars it contains
 * should be present in the "flat" tlist generated by create_plan, though
 * possibly in a different order.  In that case we'll use create_plan's tlist,
 * and the tlist made here is only needed as input to query_planner to tell
 * it which Vars are needed in the output of the scan/join plan.
 *
 * 'tlist' is the query's target list.
 * 'groupColIdx' receives an array of column numbers for the GROUP BY
 *			expressions (if there are any) in the returned target list.
 * 'need_tlist_eval' is set true if we really need to evaluate the
 *			returned tlist as-is.  (Note: locate_grouping_columns assumes
 *			that if this is FALSE, all grouping columns are simple Vars.)
 *
 * The result is the targetlist to be passed to query_planner.
 */
static List *
make_subplanTargetList(PlannerInfo *root,
					   List *tlist,
					   AttrNumber **groupColIdx,
					   bool *need_tlist_eval)
{
	Query	   *parse = root->parse;
	List	   *sub_tlist;
	List	   *non_group_cols;
	List	   *non_group_vars;
	int			numCols;

	*groupColIdx = NULL;

	/*
	 * If we're not grouping or aggregating, there's nothing to do here;
	 * query_planner should receive the unmodified target list.
	 */
	if (!parse->hasAggs && !parse->groupClause && !parse->groupingSets && !root->hasHavingQual &&
		!parse->hasWindowFuncs)
	{
		*need_tlist_eval = true;
		return tlist;
	}

	/*
	 * Otherwise, we must build a tlist containing all grouping columns, plus
	 * any other Vars mentioned in the targetlist and HAVING qual.
	 */
	sub_tlist = NIL;
	non_group_cols = NIL;
	*need_tlist_eval = false;	/* only eval if not flat tlist */

	numCols = list_length(parse->groupClause);
	if (numCols > 0)
	{
		/*
		 * If grouping, create sub_tlist entries for all GROUP BY columns, and
		 * make an array showing where the group columns are in the sub_tlist.
		 *
		 * Note: with this implementation, the array entries will always be
		 * 1..N, but we don't want callers to assume that.
		 */
		AttrNumber *grpColIdx;
		ListCell   *tl;

		grpColIdx = (AttrNumber *) palloc0(sizeof(AttrNumber) * numCols);
		*groupColIdx = grpColIdx;

		foreach(tl, tlist)
		{
			TargetEntry *tle = (TargetEntry *) lfirst(tl);
			int			colno;

			colno = get_grouping_column_index(parse, tle);
			if (colno >= 0)
			{
				/*
				 * It's a grouping column, so add it to the result tlist and
				 * remember its resno in grpColIdx[].
				 */
				TargetEntry *newtle;

				newtle = makeTargetEntry(tle->expr,
										 list_length(sub_tlist) + 1,
										 NULL,
										 false);
				sub_tlist = lappend(sub_tlist, newtle);

				Assert(grpColIdx[colno] == 0);	/* no dups expected */
				grpColIdx[colno] = newtle->resno;

				if (!(newtle->expr && IsA(newtle->expr, Var)))
					*need_tlist_eval = true;	/* tlist contains non Vars */
			}
			else
			{
				/*
				 * Non-grouping column, so just remember the expression for
				 * later call to pull_var_clause.  There's no need for
				 * pull_var_clause to examine the TargetEntry node itself.
				 */
				non_group_cols = lappend(non_group_cols, tle->expr);
			}
		}
	}
	else
	{
		/*
		 * With no grouping columns, just pass whole tlist to pull_var_clause.
		 * Need (shallow) copy to avoid damaging input tlist below.
		 */
		non_group_cols = list_copy(tlist);
	}

	/*
	 * If there's a HAVING clause, we'll need the Vars it uses, too.
	 */
	if (parse->havingQual)
		non_group_cols = lappend(non_group_cols, parse->havingQual);

	/*
	 * Pull out all the Vars mentioned in non-group cols (plus HAVING), and
	 * add them to the result tlist if not already present.  (A Var used
	 * directly as a GROUP BY item will be present already.)  Note this
	 * includes Vars used in resjunk items, so we are covering the needs of
	 * ORDER BY and window specifications.  Vars used within Aggrefs will be
	 * pulled out here, too.
	 */
	non_group_vars = pull_var_clause((Node *) non_group_cols,
									 PVC_RECURSE_AGGREGATES,
									 PVC_INCLUDE_PLACEHOLDERS);
	sub_tlist = add_to_flat_tlist(sub_tlist, non_group_vars);

	/* clean up cruft */
	list_free(non_group_vars);
	list_free(non_group_cols);

	return sub_tlist;
}

/*
 * get_grouping_column_index
 *		Get the GROUP BY column position, if any, of a targetlist entry.
 *
 * Returns the index (counting from 0) of the TLE in the GROUP BY list, or -1
 * if it's not a grouping column.  Note: the result is unique because the
 * parser won't make multiple groupClause entries for the same TLE.
 */
static int
get_grouping_column_index(Query *parse, TargetEntry *tle)
{
	int			colno = 0;
	Index		ressortgroupref = tle->ressortgroupref;
	ListCell   *gl;

	/* No need to search groupClause if TLE hasn't got a sortgroupref */
	if (ressortgroupref == 0)
		return -1;

	foreach(gl, parse->groupClause)
	{
		SortGroupClause *grpcl = (SortGroupClause *) lfirst(gl);

		if (grpcl->tleSortGroupRef == ressortgroupref)
			return colno;
		colno++;
	}

	return -1;
}

/*
 * locate_grouping_columns
 *		Locate grouping columns in the tlist chosen by create_plan.
 *
 * This is only needed if we don't use the sub_tlist chosen by
 * make_subplanTargetList.  We have to forget the column indexes found
 * by that routine and re-locate the grouping exprs in the real sub_tlist.
 * We assume the grouping exprs are just Vars (see make_subplanTargetList).
 */
static void
locate_grouping_columns(PlannerInfo *root,
						List *tlist,
						List *sub_tlist,
						AttrNumber *groupColIdx)
{
	int			keyno = 0;
	ListCell   *gl;

	/*
	 * No work unless grouping.
	 */
	if (!root->parse->groupClause)
	{
		Assert(groupColIdx == NULL);
		return;
	}
	Assert(groupColIdx != NULL);

	foreach(gl, root->parse->groupClause)
	{
		SortGroupClause *grpcl = (SortGroupClause *) lfirst(gl);
		Var		   *groupexpr = (Var *) get_sortgroupclause_expr(grpcl, tlist);
		TargetEntry *te;

		/*
		 * The grouping column returned by create_plan might not have the same
		 * typmod as the original Var.  (This can happen in cases where a
		 * set-returning function has been inlined, so that we now have more
		 * knowledge about what it returns than we did when the original Var
		 * was created.)  So we can't use tlist_member() to search the tlist;
		 * instead use tlist_member_match_var.  For safety, still check that
		 * the vartype matches.
		 */
		if (!(groupexpr && IsA(groupexpr, Var)))
			elog(ERROR, "grouping column is not a Var as expected");
		te = tlist_member_match_var(groupexpr, sub_tlist);
		if (!te)
			elog(ERROR, "failed to locate grouping columns");
		Assert(((Var *) te->expr)->vartype == groupexpr->vartype);
		groupColIdx[keyno++] = te->resno;
	}
}

/*
 * postprocess_setop_tlist
 *	  Fix up targetlist returned by plan_set_operations().
 *
 * We need to transpose sort key info from the orig_tlist into new_tlist.
 * NOTE: this would not be good enough if we supported resjunk sort keys
 * for results of set operations --- then, we'd need to project a whole
 * new tlist to evaluate the resjunk columns.  For now, just ereport if we
 * find any resjunk columns in orig_tlist.
 */
static List *
postprocess_setop_tlist(List *new_tlist, List *orig_tlist)
{
	ListCell   *l;
	ListCell   *orig_tlist_item = list_head(orig_tlist);

	foreach(l, new_tlist)
	{
		TargetEntry *new_tle = (TargetEntry *) lfirst(l);
		TargetEntry *orig_tle;

		/* ignore resjunk columns in setop result */
		if (new_tle->resjunk)
			continue;

		Assert(orig_tlist_item != NULL);
		orig_tle = (TargetEntry *) lfirst(orig_tlist_item);
		orig_tlist_item = lnext(orig_tlist_item);
		if (orig_tle->resjunk)	/* should not happen */
			elog(ERROR, "resjunk output columns are not implemented");
		Assert(new_tle->resno == orig_tle->resno);
		new_tle->ressortgroupref = orig_tle->ressortgroupref;
	}
	if (orig_tlist_item != NULL)
		elog(ERROR, "resjunk output columns are not implemented");
	return new_tlist;
}

/*
 * select_active_windows
 *		Create a list of the "active" window clauses (ie, those referenced
 *		by non-deleted WindowFuncs) in the order they are to be executed.
 */
static List *
select_active_windows(PlannerInfo *root, WindowFuncLists *wflists)
{
	List	   *result;
	List	   *actives;
	ListCell   *lc;

	/* First, make a list of the active windows */
	actives = NIL;
	foreach(lc, root->parse->windowClause)
	{
		WindowClause *wc = (WindowClause *) lfirst(lc);

		/* It's only active if wflists shows some related WindowFuncs */
		Assert(wc->winref <= wflists->maxWinRef);
		if (wflists->windowFuncs[wc->winref] != NIL)
			actives = lappend(actives, wc);
	}

	/*
	 * Now, ensure that windows with identical partitioning/ordering clauses
	 * are adjacent in the list.  This is required by the SQL standard, which
	 * says that only one sort is to be used for such windows, even if they
	 * are otherwise distinct (eg, different names or framing clauses).
	 *
	 * There is room to be much smarter here, for example detecting whether
	 * one window's sort keys are a prefix of another's (so that sorting for
	 * the latter would do for the former), or putting windows first that
	 * match a sort order available for the underlying query.  For the moment
	 * we are content with meeting the spec.
	 */
	result = NIL;
	while (actives != NIL)
	{
		WindowClause *wc = (WindowClause *) linitial(actives);
		ListCell   *prev;
		ListCell   *next;

		/* Move wc from actives to result */
		actives = list_delete_first(actives);
		result = lappend(result, wc);

		/* Now move any matching windows from actives to result */
		prev = NULL;
		for (lc = list_head(actives); lc; lc = next)
		{
			WindowClause *wc2 = (WindowClause *) lfirst(lc);

			next = lnext(lc);
			/* framing options are NOT to be compared here! */
			if (equal(wc->partitionClause, wc2->partitionClause) &&
				equal(wc->orderClause, wc2->orderClause))
			{
				actives = list_delete_cell(actives, lc, prev);
				result = lappend(result, wc2);
			}
			else
				prev = lc;
		}
	}

	return result;
}

/*
 * make_windowInputTargetList
 *	  Generate appropriate target list for initial input to WindowAgg nodes.
 *
 * When grouping_planner inserts one or more WindowAgg nodes into the plan,
 * this function computes the initial target list to be computed by the node
 * just below the first WindowAgg.  This list must contain all values needed
 * to evaluate the window functions, compute the final target list, and
 * perform any required final sort step.  If multiple WindowAggs are needed,
 * each intermediate one adds its window function results onto this tlist;
 * only the topmost WindowAgg computes the actual desired target list.
 *
 * This function is much like make_subplanTargetList, though not quite enough
 * like it to share code.  As in that function, we flatten most expressions
 * into their component variables.  But we do not want to flatten window
 * PARTITION BY/ORDER BY clauses, since that might result in multiple
 * evaluations of them, which would be bad (possibly even resulting in
 * inconsistent answers, if they contain volatile functions).  Also, we must
 * not flatten GROUP BY clauses that were left unflattened by
 * make_subplanTargetList, because we may no longer have access to the
 * individual Vars in them.
 *
 * Another key difference from make_subplanTargetList is that we don't flatten
 * Aggref expressions, since those are to be computed below the window
 * functions and just referenced like Vars above that.
 *
 * 'tlist' is the query's final target list.
 * 'activeWindows' is the list of active windows previously identified by
 *			select_active_windows.
 *
 * The result is the targetlist to be computed by the plan node immediately
 * below the first WindowAgg node.
 */
static List *
make_windowInputTargetList(PlannerInfo *root,
						   List *tlist,
						   List *activeWindows)
{
	Query	   *parse = root->parse;
	Bitmapset  *sgrefs;
	List	   *new_tlist;
	List	   *flattenable_cols;
	List	   *flattenable_vars;
	ListCell   *lc;

	Assert(parse->hasWindowFuncs);

	/*
	 * Collect the sortgroupref numbers of window PARTITION/ORDER BY clauses
	 * into a bitmapset for convenient reference below.
	 */
	sgrefs = NULL;
	foreach(lc, activeWindows)
	{
		WindowClause *wc = (WindowClause *) lfirst(lc);
		ListCell   *lc2;

		foreach(lc2, wc->partitionClause)
		{
			SortGroupClause *sortcl = (SortGroupClause *) lfirst(lc2);

			sgrefs = bms_add_member(sgrefs, sortcl->tleSortGroupRef);
		}
		foreach(lc2, wc->orderClause)
		{
			SortGroupClause *sortcl = (SortGroupClause *) lfirst(lc2);

			sgrefs = bms_add_member(sgrefs, sortcl->tleSortGroupRef);
		}
	}

	/* Add in sortgroupref numbers of GROUP BY clauses, too */
	foreach(lc, parse->groupClause)
	{
		SortGroupClause *grpcl = (SortGroupClause *) lfirst(lc);

		sgrefs = bms_add_member(sgrefs, grpcl->tleSortGroupRef);
	}

	/*
	 * Construct a tlist containing all the non-flattenable tlist items, and
	 * save aside the others for a moment.
	 */
	new_tlist = NIL;
	flattenable_cols = NIL;

	foreach(lc, tlist)
	{
		TargetEntry *tle = (TargetEntry *) lfirst(lc);

		/*
		 * Don't want to deconstruct window clauses or GROUP BY items.  (Note
		 * that such items can't contain window functions, so it's okay to
		 * compute them below the WindowAgg nodes.)
		 */
		if (tle->ressortgroupref != 0 &&
			bms_is_member(tle->ressortgroupref, sgrefs))
		{
			/* Don't want to deconstruct this value, so add to new_tlist */
			TargetEntry *newtle;

			newtle = makeTargetEntry(tle->expr,
									 list_length(new_tlist) + 1,
									 NULL,
									 false);
			/* Preserve its sortgroupref marking, in case it's volatile */
			newtle->ressortgroupref = tle->ressortgroupref;
			new_tlist = lappend(new_tlist, newtle);
		}
		else
		{
			/*
			 * Column is to be flattened, so just remember the expression for
			 * later call to pull_var_clause.  There's no need for
			 * pull_var_clause to examine the TargetEntry node itself.
			 */
			flattenable_cols = lappend(flattenable_cols, tle->expr);
		}
	}

	/*
	 * Pull out all the Vars and Aggrefs mentioned in flattenable columns, and
	 * add them to the result tlist if not already present.  (Some might be
	 * there already because they're used directly as window/group clauses.)
	 *
	 * Note: it's essential to use PVC_INCLUDE_AGGREGATES here, so that the
	 * Aggrefs are placed in the Agg node's tlist and not left to be computed
	 * at higher levels.
	 */
	flattenable_vars = pull_var_clause((Node *) flattenable_cols,
									   PVC_INCLUDE_AGGREGATES,
									   PVC_INCLUDE_PLACEHOLDERS);
	new_tlist = add_to_flat_tlist(new_tlist, flattenable_vars);

	/* clean up cruft */
	list_free(flattenable_vars);
	list_free(flattenable_cols);

	return new_tlist;
}

/*
 * make_pathkeys_for_window
 *		Create a pathkeys list describing the required input ordering
 *		for the given WindowClause.
 *
 * The required ordering is first the PARTITION keys, then the ORDER keys.
 * In the future we might try to implement windowing using hashing, in which
 * case the ordering could be relaxed, but for now we always sort.
 */
static List *
make_pathkeys_for_window(PlannerInfo *root, WindowClause *wc,
						 List *tlist)
{
	List	   *window_pathkeys;
	List	   *window_sortclauses;

	/* Throw error if can't sort */
	if (!grouping_is_sortable(wc->partitionClause))
		ereport(ERROR,
				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
				 errmsg("could not implement window PARTITION BY"),
				 errdetail("Window partitioning columns must be of sortable datatypes.")));
	if (!grouping_is_sortable(wc->orderClause))
		ereport(ERROR,
				(errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
				 errmsg("could not implement window ORDER BY"),
		errdetail("Window ordering columns must be of sortable datatypes.")));

	/* Okay, make the combined pathkeys */
	window_sortclauses = list_concat(list_copy(wc->partitionClause),
									 list_copy(wc->orderClause));
	window_pathkeys = make_pathkeys_for_sortclauses(root,
													window_sortclauses,
													tlist);
	list_free(window_sortclauses);
	return window_pathkeys;
}

/*----------
 * get_column_info_for_window
 *		Get the partitioning/ordering column numbers and equality operators
 *		for a WindowAgg node.
 *
 * This depends on the behavior of make_pathkeys_for_window()!
 *
 * We are given the target WindowClause and an array of the input column
 * numbers associated with the resulting pathkeys.  In the easy case, there
 * are the same number of pathkey columns as partitioning + ordering columns
 * and we just have to copy some data around.  However, it's possible that
 * some of the original partitioning + ordering columns were eliminated as
 * redundant during the transformation to pathkeys.  (This can happen even
 * though the parser gets rid of obvious duplicates.  A typical scenario is a
 * window specification "PARTITION BY x ORDER BY y" coupled with a clause
 * "WHERE x = y" that causes the two sort columns to be recognized as
 * redundant.)	In that unusual case, we have to work a lot harder to
 * determine which keys are significant.
 *
 * The method used here is a bit brute-force: add the sort columns to a list
 * one at a time and note when the resulting pathkey list gets longer.  But
 * it's a sufficiently uncommon case that a faster way doesn't seem worth
 * the amount of code refactoring that'd be needed.
 *----------
 */
static void
get_column_info_for_window(PlannerInfo *root, WindowClause *wc, List *tlist,
						   int numSortCols, AttrNumber *sortColIdx,
						   int *partNumCols,
						   AttrNumber **partColIdx,
						   Oid **partOperators,
						   int *ordNumCols,
						   AttrNumber **ordColIdx,
						   Oid **ordOperators)
{
	int			numPart = list_length(wc->partitionClause);
	int			numOrder = list_length(wc->orderClause);

	if (numSortCols == numPart + numOrder)
	{
		/* easy case */
		*partNumCols = numPart;
		*partColIdx = sortColIdx;
		*partOperators = extract_grouping_ops(wc->partitionClause);
		*ordNumCols = numOrder;
		*ordColIdx = sortColIdx + numPart;
		*ordOperators = extract_grouping_ops(wc->orderClause);
	}
	else
	{
		List	   *sortclauses;
		List	   *pathkeys;
		int			scidx;
		ListCell   *lc;

		/* first, allocate what's certainly enough space for the arrays */
		*partNumCols = 0;
		*partColIdx = (AttrNumber *) palloc(numPart * sizeof(AttrNumber));
		*partOperators = (Oid *) palloc(numPart * sizeof(Oid));
		*ordNumCols = 0;
		*ordColIdx = (AttrNumber *) palloc(numOrder * sizeof(AttrNumber));
		*ordOperators = (Oid *) palloc(numOrder * sizeof(Oid));
		sortclauses = NIL;
		pathkeys = NIL;
		scidx = 0;
		foreach(lc, wc->partitionClause)
		{
			SortGroupClause *sgc = (SortGroupClause *) lfirst(lc);
			List	   *new_pathkeys;

			sortclauses = lappend(sortclauses, sgc);
			new_pathkeys = make_pathkeys_for_sortclauses(root,
														 sortclauses,
														 tlist);
			if (list_length(new_pathkeys) > list_length(pathkeys))
			{
				/* this sort clause is actually significant */
				(*partColIdx)[*partNumCols] = sortColIdx[scidx++];
				(*partOperators)[*partNumCols] = sgc->eqop;
				(*partNumCols)++;
				pathkeys = new_pathkeys;
			}
		}
		foreach(lc, wc->orderClause)
		{
			SortGroupClause *sgc = (SortGroupClause *) lfirst(lc);
			List	   *new_pathkeys;

			sortclauses = lappend(sortclauses, sgc);
			new_pathkeys = make_pathkeys_for_sortclauses(root,
														 sortclauses,
														 tlist);
			if (list_length(new_pathkeys) > list_length(pathkeys))
			{
				/* this sort clause is actually significant */
				(*ordColIdx)[*ordNumCols] = sortColIdx[scidx++];
				(*ordOperators)[*ordNumCols] = sgc->eqop;
				(*ordNumCols)++;
				pathkeys = new_pathkeys;
			}
		}
		/* complain if we didn't eat exactly the right number of sort cols */
		if (scidx != numSortCols)
			elog(ERROR, "failed to deconstruct sort operators into partitioning/ordering operators");
	}
}


/*
 * expression_planner
 *		Perform planner's transformations on a standalone expression.
 *
 * Various utility commands need to evaluate expressions that are not part
 * of a plannable query.  They can do so using the executor's regular
 * expression-execution machinery, but first the expression has to be fed
 * through here to transform it from parser output to something executable.
 *
 * Currently, we disallow sublinks in standalone expressions, so there's no
 * real "planning" involved here.  (That might not always be true though.)
 * What we must do is run eval_const_expressions to ensure that any function
 * calls are converted to positional notation and function default arguments
 * get inserted.  The fact that constant subexpressions get simplified is a
 * side-effect that is useful when the expression will get evaluated more than
 * once.  Also, we must fix operator function IDs.
 *
 * Note: this must not make any damaging changes to the passed-in expression
 * tree.  (It would actually be okay to apply fix_opfuncids to it, but since
 * we first do an expression_tree_mutator-based walk, what is returned will
 * be a new node tree.)
 */
Expr *
expression_planner(Expr *expr)
{
	Node	   *result;

	/*
	 * Convert named-argument function calls, insert default arguments and
	 * simplify constant subexprs
	 */
	result = eval_const_expressions(NULL, (Node *) expr);

	/* Fill in opfuncid values if missing */
	fix_opfuncids(result);

	return (Expr *) result;
}


/*
 * plan_cluster_use_sort
 *		Use the planner to decide how CLUSTER should implement sorting
 *
 * tableOid is the OID of a table to be clustered on its index indexOid
 * (which is already known to be a btree index).  Decide whether it's
 * cheaper to do an indexscan or a seqscan-plus-sort to execute the CLUSTER.
 * Return TRUE to use sorting, FALSE to use an indexscan.
 *
 * Note: caller had better already hold some type of lock on the table.
 */
bool
plan_cluster_use_sort(Oid tableOid, Oid indexOid)
{
	PlannerInfo *root;
	Query	   *query;
	PlannerGlobal *glob;
	RangeTblEntry *rte;
	RelOptInfo *rel;
	IndexOptInfo *indexInfo;
	QualCost	indexExprCost;
	Cost		comparisonCost;
	Path	   *seqScanPath;
	Path		seqScanAndSortPath;
	IndexPath  *indexScanPath;
	ListCell   *lc;

	/* Set up mostly-dummy planner state */
	query = makeNode(Query);
	query->commandType = CMD_SELECT;

	glob = makeNode(PlannerGlobal);

	root = makeNode(PlannerInfo);
	root->parse = query;
	root->glob = glob;
	root->query_level = 1;
	root->planner_cxt = CurrentMemoryContext;
	root->wt_param_id = -1;

	/* Build a minimal RTE for the rel */
	rte = makeNode(RangeTblEntry);
	rte->rtekind = RTE_RELATION;
	rte->relid = tableOid;
	rte->relkind = RELKIND_RELATION;	/* Don't be too picky. */
	rte->lateral = false;
	rte->inh = false;
	rte->inFromCl = true;
	query->rtable = list_make1(rte);

	/* Set up RTE/RelOptInfo arrays */
	setup_simple_rel_arrays(root);

	/* Build RelOptInfo */
	rel = build_simple_rel(root, 1, RELOPT_BASEREL);

	/* Locate IndexOptInfo for the target index */
	indexInfo = NULL;
	foreach(lc, rel->indexlist)
	{
		indexInfo = (IndexOptInfo *) lfirst(lc);
		if (indexInfo->indexoid == indexOid)
			break;
	}

	/*
	 * It's possible that get_relation_info did not generate an IndexOptInfo
	 * for the desired index; this could happen if it's not yet reached its
	 * indcheckxmin usability horizon, or if it's a system index and we're
	 * ignoring system indexes.  In such cases we should tell CLUSTER to not
	 * trust the index contents but use seqscan-and-sort.
	 */
	if (lc == NULL)				/* not in the list? */
		return true;			/* use sort */

	/*
	 * Rather than doing all the pushups that would be needed to use
	 * set_baserel_size_estimates, just do a quick hack for rows and width.
	 */
	rel->rows = rel->tuples;
	rel->width = get_relation_data_width(tableOid, NULL);

	root->total_table_pages = rel->pages;

	/*
	 * Determine eval cost of the index expressions, if any.  We need to
	 * charge twice that amount for each tuple comparison that happens during
	 * the sort, since tuplesort.c will have to re-evaluate the index
	 * expressions each time.  (XXX that's pretty inefficient...)
	 */
	cost_qual_eval(&indexExprCost, indexInfo->indexprs, root);
	comparisonCost = 2.0 * (indexExprCost.startup + indexExprCost.per_tuple);

	/* Estimate the cost of seq scan + sort */
	seqScanPath = create_seqscan_path(root, rel, NULL);
	cost_sort(&seqScanAndSortPath, root, NIL,
			  seqScanPath->total_cost, rel->tuples, rel->width,
			  comparisonCost, maintenance_work_mem, -1.0);

	/* Estimate the cost of index scan */
	indexScanPath = create_index_path(root, indexInfo,
									  NIL, NIL, NIL, NIL, NIL,
									  ForwardScanDirection, false,
									  NULL, 1.0);

	return (seqScanAndSortPath.total_cost < indexScanPath->path.total_cost);
}