/*------------------------------------------------------------------------- * * planner . c * The query optimizer external interface . * * Portions Copyright ( c ) 1996 - 2025 , 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/genam.h" #include "access/parallel.h" #include "access/sysattr.h" #include "access/table.h" #include "catalog/pg_aggregate.h" #include "catalog/pg_inherits.h" #include "catalog/pg_proc.h" #include "catalog/pg_type.h" #include "executor/executor.h" #include "foreign/fdwapi.h" #include "jit/jit.h" #include "lib/bipartite_match.h" #include "lib/knapsack.h" #include "miscadmin.h" #include "nodes/makefuncs.h" #include "nodes/nodeFuncs.h" #ifdef OPTIMIZER_DEBUG#include "nodes/print.h" #endif #include "nodes/supportnodes.h" #include "optimizer/appendinfo.h" #include "optimizer/clauses.h" #include "optimizer/cost.h" #include "optimizer/optimizer.h" #include "optimizer/paramassign.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/parse_agg.h" #include "parser/parse_clause.h" #include "parser/parse_relation.h" #include "parser/parsetree.h" #include "partitioning/partdesc.h" #include "rewrite/rewriteManip.h" #include "utils/acl.h" #include "utils/backend_status.h" #include "utils/lsyscache.h" #include "utils/rel.h" #include "utils/selfuncs.h" /* GUC parameters */ double cursor_tuple_fraction = DEFAULT_CURSOR_TUPLE_FRACTION;int debug_parallel_query = DEBUG_PARALLEL_OFF;bool parallel_leader_participation = true ;bool enable_distinct_reordering = true ;/* Hook for plugins to get control in planner() */ /* Hook for plugins to get control when grouping_planner() plans upper rels */ /* 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 #define EXPRKIND_ARBITER_ELEM 10 #define EXPRKIND_TABLEFUNC 11 #define EXPRKIND_TABLEFUNC_LATERAL 12 #define EXPRKIND_GROUPEXPR 13 /* * Data specific to grouping sets typedef struct double dNumHashGroups;bool any_hashable;int *tleref_to_colnum_map;/* * Temporary structure for use during WindowClause reordering in order to be * able to sort WindowClauses on partitioning / ordering prefix . typedef struct /* A List of unique ordering/partitioning /* Passthrough data for standard_qp_callback */ typedef struct /* active windows, if any */ /* grouping sets data, if any */ /* parent set operation or NULL if not a /* * Context for the find_having_collation_conflicts walker . * * ancestor_collids is a stack of inputcollids contributed by collation - aware * ancestors of the current node . Entries are pushed before recursing into a * node ' s children and popped afterwards , so the stack reflects exactly the * inputcollids on the current root - to - node path . typedef struct /* Local functions */ static Node *preprocess_expression(PlannerInfo *root, Node *expr, int kind);static void preprocess_qual_conditions(PlannerInfo *root, Node *jtnode);static Bitmapset *find_having_collation_conflicts(Query *parse,static bool having_collation_conflict_walker(Node *node,static void grouping_planner(PlannerInfo *root, double tuple_fraction,static grouping_sets_data *preprocess_grouping_sets(PlannerInfo *root);static List *remap_to_groupclause_idx(List *groupClause, List *gsets,int *tleref_to_colnum_map);static void preprocess_rowmarks(PlannerInfo *root);static double preprocess_limit(PlannerInfo *root,double tuple_fraction,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 double get_number_of_groups(PlannerInfo *root,double path_rows,static RelOptInfo *create_grouping_paths(PlannerInfo *root,bool target_parallel_safe,static bool is_degenerate_grouping(PlannerInfo *root);static void create_degenerate_grouping_paths(PlannerInfo *root,static RelOptInfo *make_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,bool target_parallel_safe,static void create_ordinary_grouping_paths(PlannerInfo *root,const AggClauseCosts *agg_costs,static void consider_groupingsets_paths(PlannerInfo *root,bool is_sorted,bool can_hash,const AggClauseCosts *agg_costs,double dNumGroups);static RelOptInfo *create_window_paths(PlannerInfo *root,bool output_target_parallel_safe,static void create_one_window_path(PlannerInfo *root,static RelOptInfo *create_distinct_paths(PlannerInfo *root,static void create_partial_distinct_paths(PlannerInfo *root,static RelOptInfo *create_final_distinct_paths(PlannerInfo *root,static List *get_useful_pathkeys_for_distinct(PlannerInfo *root,static RelOptInfo *create_ordered_paths(PlannerInfo *root,bool target_parallel_safe,double limit_tuples);static PathTarget *make_group_input_target(PlannerInfo *root,static PathTarget *make_partial_grouping_target(PlannerInfo *root,static List *postprocess_setop_tlist(List *new_tlist, List *orig_tlist);static void optimize_window_clauses(PlannerInfo *root,static List *select_active_windows(PlannerInfo *root, WindowFuncLists *wflists);static void name_active_windows(List *activeWindows);static PathTarget *make_window_input_target(PlannerInfo *root,static List *make_pathkeys_for_window(PlannerInfo *root, WindowClause *wc,static PathTarget *make_sort_input_target(PlannerInfo *root,bool *have_postponed_srfs);static void adjust_paths_for_srfs(PlannerInfo *root, RelOptInfo *rel,static void add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,const AggClauseCosts *agg_costs,double dNumGroups,static RelOptInfo *create_partial_grouping_paths(PlannerInfo *root,bool force_rel_creation);static Path *make_ordered_path(PlannerInfo *root,double limit_tuples);static void gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel);static bool can_partial_agg(PlannerInfo *root);static void apply_scanjoin_target_to_paths(PlannerInfo *root,bool scanjoin_target_parallel_safe,bool tlist_same_exprs);static void create_partitionwise_grouping_paths(PlannerInfo *root,const AggClauseCosts *agg_costs,static bool group_by_has_partkey(RelOptInfo *input_rel,static int common_prefix_cmp(const void *a, const void *b);static List *generate_setop_child_grouplist(SetOperationStmt *op,/***************************************************************************** * * 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 . * const char *query_string, int cursorOptions,if (planner_hook)else false );return result;const char *query_string, int cursorOptions,double tuple_fraction;/* * 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 . 0 ;0 ;0 ;false ;false ;/* * Assess whether it ' s feasible to use parallel mode for this query . We * can ' t do this in a standalone backend , or if the command will try to * modify any data , or if this is a cursor operation , or if GUCs are set * to values that don ' t permit parallelism , or if parallel - unsafe * functions are present in the query tree . * * ( Note that we do allow CREATE TABLE AS , SELECT INTO , and CREATE * MATERIALIZED VIEW to use parallel plans , but this is safe only because * the command is writing into a completely new table which workers won ' t * be able to see . If the workers could see the table , the fact that * group locking would cause them to ignore the leader ' s heavyweight GIN * page locks would make this unsafe . We ' ll have to fix that somehow if * we want to allow parallel inserts in general ; updates and deletes have * additional problems especially around combo CIDs . ) * * For now , we don ' t try to use parallel mode if we ' re running inside a * parallel worker . We might eventually be able to relax this * restriction , but for now it seems best not to have parallel workers * trying to create their own parallel workers . if ((cursorOptions & CURSOR_OPT_PARALLEL_OK) != 0 &&0 &&/* all the cheap tests pass, so scan the query tree */ else /* skip the query tree scan, just assume it's unsafe */ false ;/* * glob - > parallelModeNeeded is normally set to false here and changed to * true during plan creation if a Gather or Gather Merge plan is actually * created ( cf . create_gather_plan , create_gather_merge_plan ) . * * However , if debug_parallel_query = on or debug_parallel_query = * regress , then we impose parallel mode whenever it ' s safe to do so , even * if the final plan doesn ' t use parallelism . It ' s not safe to do so if * the query contains anything parallel - unsafe ; parallelModeOK will be * false in that case . Note that parallelModeOK can ' t change after this * point . Otherwise , everything in the query is either parallel - safe or * parallel - restricted , and in either case it should be OK to impose * parallel - mode restrictions . If that ends up breaking something , then * either some function the user included in the query is incorrectly * labeled as parallel - safe or parallel - restricted when in reality it ' s * parallel - unsafe , or else the query planner itself has a bug . /* 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 . /* * 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 )0 .0 ;else if (tuple_fraction <= 0 .0 )1 e-10 ;else /* Default assumption is we need all the tuples */ 0 .0 ;/* primary planning entry point (may recurse for subqueries) */ false , tuple_fraction, NULL);/* Select best Path and turn it into a Plan */ /* * 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))/* * Optionally add a Gather node for testing purposes , provided this is * actually a safe thing to do . * * We can add Gather even when top_plan has parallel - safe initPlans , but * then we have to move the initPlans to the Gather node because of * SS_finalize_plan ' s limitations . That would cause cosmetic breakage of * regression tests when debug_parallel_query = regress , because initPlans * that would normally appear on the top_plan move to the Gather , causing * them to disappear from EXPLAIN output . That doesn ' t seem worth kluging * EXPLAIN to hide , so skip it when debug_parallel_query = regress . if (debug_parallel_query != DEBUG_PARALLEL_OFF &&bool unsafe_initplans;1 ;true ;/* Transfer any initPlans to the new top node */ /* * Since this Gather has no parallel - aware descendants to signal to , * we don ' t need a rescan Param . 1 ;/* * Ideally we ' d use cost_gather here , but setting up dummy path data * to satisfy it doesn ' t seem much cleaner than knowing what it does . false ;false ;/* * Delete the initplans ' cost from top_plan . We needn ' t add it to the * Gather node , since the above coding already included it there . /* use parallel mode for parallel plans. */ true ;/* * If any Params were generated , run through the plan tree and compute * each plan node ' s extParam / allParam sets . Ideally we ' d merge this into * set_plan_references ' tree traversal , but for now it has to be separate * because we need to visit subplans before not after main plan . if (glob->paramExecTypes != NIL)/* final cleanup of the plan */ /* ... and the subplans (both regular subplans and initplans) */ /* build the PlannedStmt result */ /* utilityStmt should be null, but we might as well copy it */ if (jit_enabled && jit_above_cost >= 0 &&/* * Decide how much effort should be put into generating better code . if (jit_optimize_above_cost >= 0 &&if (jit_inline_above_cost >= 0 &&/* * Decide which operations should be JITed . if (jit_expressions)if (jit_tuple_deforming)if (glob->partition_directory != NULL)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 . * setops is used for set operation subqueries to provide the subquery with * the context in which it ' s being used so that Paths correctly sorted for the * set operation can be generated . NULL when not planning a set operation * child , or when a child of a set op that isn ' t interested in sorted input . * * 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 the PlannerInfo struct ( " root " ) that contains all data generated * while planning the subquery . In particular , the Path ( s ) attached to * the ( UPPERREL_FINAL , NULL ) upperrel represent our conclusions about the * cheapest way ( s ) to implement the query . The top level will select the * best Path and pass it through createplan . c to produce a finished Plan . * - - - - - - - - - - - - - - - - - - - - bool hasRecursion, double tuple_fraction,int havingIdx;bool hasOuterJoins;bool hasResultRTEs;/* Create a PlannerInfo data structure for this subquery */ 1 : 1 ;false ;0 ;/* we'll find out leaf-ness later */ 0 , sizeof (root->upper_rels));0 , sizeof (root->upper_targets));0 ;false ;false ;false ;if (hasRecursion)else 1 ;false ;/* * Create the top - level join domain . This won ' t have valid contents until * deconstruct_jointree fills it in , but the node needs to exist before * that so we can build EquivalenceClasses referencing it . /* * If there is a WITH list , process each WITH query and either convert it * to RTE_SUBQUERY RTE ( s ) or build an initplan SubPlan structure for it . if (parse->cteList)/* * If it ' s a MERGE command , transform the joinlist as appropriate . /* * If the FROM clause is empty , replace it with a dummy RTE_RESULT RTE , so * that we don ' t need so many special cases to deal with that situation . /* * 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)/* * Scan the rangetable for function RTEs , do const - simplification on them , * and then inline them if possible ( producing subqueries that might get * pulled up next ) . Recursion issues here are handled in the same way as * for SubLinks . /* * Scan the rangetable for relations with virtual generated columns , and * replace all Var nodes in the query that reference these columns with * the generation expressions . Recursion issues here are handled in the * same way as for SubLinks . /* * Check to see if any subqueries in the jointree can be merged into this * query . /* * 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)/* * Survey the rangetable to see what kinds of entries are present . We can * skip some later processing if relevant SQL features are not used ; for * example if there are no JOIN RTEs we can avoid the expense of doing * flatten_join_alias_vars ( ) . This must be done after we have finished * adding rangetable entries , of course . ( Note : actually , processing of * inherited or partitioned rels can cause RTEs for their child tables to * get added later ; but those must all be RTE_RELATION entries , so they * don ' t invalidate the conclusions drawn here . ) false ;false ;0 ;false ;false ;switch (rte->rtekind)case RTE_RELATION:if (rte->inh)/* * Check to see if the relation actually has any children ; * if not , clear the inh flag so we can treat it as a * plain base relation . * * Note : this could give a false - positive result , if the * rel once had children but no longer does . We used to * be able to clear rte - > inh later on when we discovered * that , but no more ; we have to handle such cases as * full - fledged inheritance . break ;case RTE_JOIN:true ;if (IS_OUTER_JOIN(rte->jointype))true ;break ;case RTE_RESULT:true ;break ;case RTE_GROUP:1 ;break ;default :/* No work here for other RTE types */ break ;if (rte->lateral)true ;/* * We can also determine the maximum security level required for any * securityQuals now . Addition of inheritance - child RTEs won ' t affect * this , because child tables don ' t have their own securityQuals ; see * expand_single_inheritance_child ( ) . if (rte->securityQuals)/* * If we have now verified that the query target relation is * non - inheriting , mark it as a leaf target . if (parse->resultRelation)if (!rte->inh)/* * This would be a convenient time to check access permissions for all * relations mentioned in the query , since it would be better to fail now , * before doing any detailed planning . However , for historical reasons , * we leave this to be done at executor startup . * * Note , however , that we do need to check access permissions for any view * relations mentioned in the query , in order to prevent information being * leaked by selectivity estimation functions , which only check view owner * permissions on underlying tables ( see all_rows_selectable ( ) and its * callers ) . This is a little ugly , because it means that access * permissions for views will be checked twice , which is another reason * why it would be better to do all the ACL checks here . if (rte->perminfoindex != 0 &&bool result;if (!result)/* * Preprocess RowMark information . We need to do this after subquery * pullup , so that all base relations are present . /* * 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 . /* * 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 . if (wco->qual != NULL)/* partitionClause/orderClause are sort/group expressions */ if (parse->onConflict)/* exclRelTlist contains only Vars, so no preprocessing needed */ /* Also need to preprocess expressions within RTEs */ int kind;if (rte->rtekind == RTE_RELATION)if (rte->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)else if (rte->rtekind == RTE_FUNCTION)/* Preprocess the function expression(s) fully */ else if (rte->rtekind == RTE_TABLEFUNC)/* Preprocess the function expression(s) fully */ else if (rte->rtekind == RTE_VALUES)/* Preprocess the values lists fully */ else if (rte->rtekind == RTE_GROUP)/* Preprocess the groupexprs list fully */ /* * Process each element of the securityQuals list as if it were a * separate qual expression ( as indeed it is ) . We need to do it this * way to get proper canonicalization of AND / OR structure . Note that * this converts each element into an implicit - AND sublist . /* * Now that we are done preprocessing expressions , and in particular done * flattening join alias variables , get rid of the joinaliasvars lists . * They no longer match what expressions in the rest of the tree look * like , because we have not preprocessed expressions in those lists ( and * do not want to ; for example , expanding a SubLink there would result in * a useless unreferenced subplan ) . Leaving them in place simply creates * a hazard for later scans of the tree . We could try to prevent that by * using QTW_IGNORE_JOINALIASES in every tree scan done after this point , * but that doesn ' t sound very reliable . if (root->hasJoinRTEs)/* * Before we flatten GROUP Vars , check which HAVING clauses have collation * conflicts . When GROUP BY uses a nondeterministic collation , values * that are " equal " for grouping may be distinguishable under a different * collation . If such a HAVING clause were moved to WHERE , it would * filter individual rows before grouping , potentially eliminating some * members of a group and thereby changing aggregate results . * * We do this check before flatten_group_exprs because we can easily * identify grouping expressions by checking whether a Var references * RTE_GROUP , and such Vars directly carry the GROUP BY collation as their * varcollid . After flattening , these Vars are replaced by the underlying * expressions , and we would have to match expressions in the HAVING * clause back to grouping expressions , which is much more complex . if (parse->hasGroupRTE)else /* * Replace any Vars in the subquery ' s targetlist and havingQual that * reference GROUP outputs with the underlying grouping expressions . * * Note that we need to perform this replacement after we ' ve preprocessed * the grouping expressions . This is to ensure that there is only one * instance of SubPlan for each SubLink contained within the grouping * expressions . if (parse->hasGroupRTE)/* Constant-folding might have removed all set-returning functions */ if (parse->hasTargetSRFs)/* * If we have grouping sets , expand the groupingSets tree of this query to * a flat list of grouping sets . We need to do this before optimizing * HAVING , since we can ' t easily tell if there ' s an empty grouping set * until we have this representation . if (parse->groupingSets)1 );/* * 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 ) . We also can ' t do this if there are any grouping * sets and the clause references any columns that are nullable by the * grouping sets ; the nulled values of those columns are not available * before the grouping step . ( The test on groupClause might seem wrong , * but it ' s okay : it ' s just an optimization to avoid running pull_varnos * when there cannot be any Vars in the HAVING clause . ) * * We also cannot do this if the HAVING clause uses a different collation * than the GROUP BY for any grouping expression whose GROUP BY collation * is nondeterministic . This is detected before flatten_group_exprs ( see * find_having_collation_conflicts above ) and recorded in the * havingCollationConflicts bitmapset . The bitmapset indexes remain valid * here because flatten_group_exprs uses expression_tree_mutator , which * preserves the list length and ordering of havingQual . * * 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 no empty grouping set 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 have to keep the clause in HAVING to * ensure that we don ' t emit a bogus aggregated row . But then the HAVING * clause must be degenerate ( variable - free ) , so we can copy it into WHERE * so that query_planner ( ) can use it in a gating Result node . ( This could * be done better , but it seems not worth optimizing . ) * * Note that a HAVING clause may contain expressions that are not fully * preprocessed . This can happen if these expressions are part of * grouping items . In such cases , they are replaced with GROUP Vars in * the parser and then replaced back after we ' re done with expression * preprocessing on havingQual . This is not an issue if the clause * remains in HAVING , because these expressions will be matched to lower * target items in setrefs . c . However , if the clause is moved or copied * into WHERE , we need to ensure that these expressions are fully * preprocessed . * * Note that both havingQual and parse - > jointree - > quals are in * implicitly - ANDed - list form at this point , even though they are declared * as Node * . 0 ;if (contain_agg_clause(havingclause) ||/* keep it in HAVING */ else if (parse->groupClause &&/* There is GROUP BY, but no empty grouping set */ /* Preprocess the HAVING clause fully */ /* ... and move it to WHERE */ else /* There is an empty grouping set (perhaps implicitly) */ /* Preprocess the HAVING clause fully */ /* ... and put a copy in WHERE */ /* ... and also keep it in HAVING */ /* * 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)/* * If we have any RTE_RESULT relations , see if they can be deleted from * the jointree . We also rely on this processing to flatten single - child * FromExprs underneath outer joins . This step is most effectively done * after we ' ve done expression preprocessing and outer join reduction . if (hasResultRTEs || hasOuterJoins)/* * Do the main planning . /* * Capture the set of outer - level param IDs we have access to , for use in * extParam / allParam calculations later . /* * If any initPlans were created in this query level , adjust the surviving * Paths ' costs and parallel - safety flags to account for them . The * initPlans won ' t actually get attached to the plan tree till * create_plan ( ) runs , but we must include their effects now . /* * Make sure we ' ve identified the cheapest Path for the final rel . ( By * doing this here not in grouping_planner , we include initPlan costs in * the decision , though it ' s unlikely that will change anything . ) return root;/* * 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 *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 first , since any expressions * we may extract from the joinaliasvars lists have not been preprocessed . * For example , if we did this after sublink processing , sublinks expanded * out from join aliases would not get processed . But we can skip this in * non - lateral RTE functions , VALUES lists , and TABLESAMPLE clauses , since * they can ' t contain any Vars of the current query level . if (root->hasJoinRTEs &&/* * Simplify constant expressions . For function RTEs , this was already * done by preprocess_function_rtes . ( But note we must do it again for * EXPRKIND_RTFUNC_LATERAL , because those might by now contain * un - simplified subexpressions inserted by flattening of subqueries or * join alias variables . ) * * 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 . if (kind != EXPRKIND_RTFUNC)/* * If it ' s a qual or havingQual , canonicalize it . if (kind == EXPRKIND_QUAL)false );#ifdef OPTIMIZER_DEBUG"After canonicalize_qual()\n" );#endif /* * Check for ANY ScalarArrayOpExpr with Const arrays and set the * hashfuncid of any that might execute more quickly by using hash lookups * instead of a linear search . if (kind == EXPRKIND_QUAL || kind == EXPRKIND_TARGET)/* Expand SubLinks to SubPlans */ if (root->parse->hasSubLinks)/* * 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 )/* * 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)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 if (jtnode == NULL)return ;if (IsA(jtnode, RangeTblRef))/* nothing to do here */ else if (IsA(jtnode, FromExpr))else if (IsA(jtnode, JoinExpr))else "unrecognized node type: %d" ,int ) nodeTag(jtnode));/* * find_having_collation_conflicts * Identify HAVING clauses that must not be moved to WHERE due to collation * mismatches with GROUP BY . * * This must be called before flatten_group_exprs , while the HAVING clause * still contains GROUP Vars ( Vars referencing RTE_GROUP ) . These GROUP Vars * carry the GROUP BY collation as their varcollid . A GROUP Var with a * nondeterministic varcollid conflicts whenever some collation - aware ancestor * on its path applies a different inputcollid : that operator would distinguish * values which the GROUP BY considers equal , so the clause is unsafe to push * to WHERE . * * Returns a Bitmapset of zero - based indexes into the havingQual list for * clauses that have collation conflicts and must stay in HAVING . static Bitmapset *int idx;if (parse->havingQual == NULL)return NULL;0 ;if (having_collation_conflict_walker(clause, &ctx))return result;/* * Walker function for find_having_collation_conflicts . * * Walk the clause top - down , maintaining a stack of inputcollids contributed * by collation - aware ancestors . At each GROUP Var with a nondeterministic * varcollid , the clause has a conflict if any ancestor ' s inputcollid differs * from the GROUP Var ' s varcollid . Most collation - aware nodes expose their * inputcollid through exprInputCollation ( ) . Two structural exceptions need * special handling : * * - RowCompareExpr carries one inputcollid per column in inputcollids [ ] , so we * descend into its ( largs [ i ] , rargs [ i ] ) pairs explicitly with the matching * collation pushed onto the stack . * * - A simple CASE ( CaseExpr with a non - NULL arg ) holds the arg outside the * WHEN ' s OpExpr , even though the WHEN ' s OpExpr is the place where the * comparison ' s inputcollid lives . Parse analysis builds each WHEN as * " OpExpr ( CaseTestExpr op val ) " - - the CaseTestExpr is a placeholder for * the arg . Before walking cexpr - > arg we therefore push every WHEN ' s * inputcollid onto the ancestor stack , so a GROUP Var at the arg is * checked against the same collations the WHEN comparisons would apply . * The WHEN bodies and defresult are then walked under the unchanged stack * so their own collation contexts are picked up by the default path . static bool bool result;if (node == NULL)return false ;if (IsA(node, Var))/* We should not see any upper-level Vars here */ 0 );if (var->varno == ctx->group_rtindex &&if (collid != var->varcollid)return true ;return false ;if (IsA(node, RowCompareExpr))/* * Each column of a row comparison is compared under its own * inputcollids [ i ] . Walk each ( largs [ i ] , rargs [ i ] ) pair with that * collation pushed , so a Var in column i is checked against the * collation that actually applies to it . bool found;if (OidIsValid(collid))if (OidIsValid(collid))if (found)return true ;return false ;if (IsA(node, CaseExpr) && ((CaseExpr *) node)->arg != NULL)int saved_len = list_length(ctx->ancestor_collids);bool found;/* * Push every WHEN ' s inputcollid before walking cexpr - > arg , since each * WHEN implicitly compares the arg under that inputcollid . if (OidIsValid(collid))if (found)return true ;/* * Walk the WHEN bodies and defresult under the unchanged ancestor * stack ; any inputcollids inside them are picked up by the default * path . if (having_collation_conflict_walker((Node *) cw->expr, ctx) ||return true ;return having_collation_conflict_walker((Node *) cexpr->defresult,if (OidIsValid(this_collid))if (OidIsValid(this_collid))return result;/* * 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 . return (Expr *) preprocess_expression(root, (Node *) expr, EXPRKIND_PHV);/*-------------------- * grouping_planner * Perform planning steps related to grouping , aggregation , etc . * * This function adds all required top - level processing to the scan / join * Path ( s ) 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 ) . * setops is used for set operation subqueries to provide the subquery with * the context in which it ' s being used so that Paths correctly sorted for the * set operation can be generated . NULL when not planning a set operation * child , or when a child of a set op that isn ' t interested in sorted input . * * Returns nothing ; the useful output is in the Paths we attach to the * ( UPPERREL_FINAL , NULL ) upperrel in * root . In addition , * root - > processed_tlist contains the final processed targetlist . * * Note that we have not done set_cheapest ( ) on the final rel ; it ' s convenient * to leave this to the caller . * - - - - - - - - - - - - - - - - - - - - static void double tuple_fraction,0 ;0 ;double limit_tuples = -1 .0 ;bool have_postponed_srfs = false ;bool final_target_parallel_safe;/* Tweak caller-supplied tuple_fraction if have LIMIT/OFFSET */ if (parse->limitCount || parse->limitOffset)/* * 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 )double ) count_est + (double ) offset_est;/* Make tuple_fraction accessible to lower-level routines */ if (parse->setOperations)/* * Construct Paths for set operations . The results 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 . /* * We should not need to call preprocess_targetlist , since we must be * in a SELECT query node . Instead , use the processed_tlist returned * by plan_set_operations ( since this tells whether it returned any * resjunk columns ! ) , and transfer any sort key information from the * original tlist . /* for safety, copy processed_tlist instead of modifying in-place */ /* Also extract the PathTarget form of the setop result tlist */ /* And check whether it's parallel safe */ /* The setop result tlist couldn't contain any SRFs */ /* * Can ' t handle FOR [ KEY ] UPDATE / SHARE here ( parser should have * checked already , but let ' s make sure ) . if (parse->rowMarks)/*------ "%s is not allowed with UNION/INTERSECT/EXCEPT" ,/* * Calculate pathkeys that represent result ordering requirements else /* No set operations, do regular planning */ bool sort_input_target_parallel_safe;bool grouping_target_parallel_safe;bool scanjoin_target_parallel_safe;bool scanjoin_target_same_exprs;bool have_grouping;/* A recursive query should always have setOperations */ /* Preprocess grouping sets and GROUP BY clause, if any */ if (parse->groupingSets)else if (parse->groupClause)/* Preprocess regular GROUP BY clause, if any */ /* * Preprocess targetlist . Note that much of the remaining planning * work will be done with the PathTarget representation of tlists , but * we must also maintain the full representation of the final tlist so * that we can transfer its decoration ( resnames etc ) to the topmost * tlist of the finished Plan . This is kept in processed_tlist . /* * Mark all the aggregates with resolved aggtranstypes , and detect * aggregates that are duplicates or can share transition state . We * must do this before slicing and dicing the tlist into various * pathtargets , else some copies of the Aggref nodes might escape * being marked . if (parse->hasAggs)/* * 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)if (wflists->numWindowFuncs > 0 )/* * See if any modifications can be made to each WindowClause * to allow the executor to execute the WindowFuncs more * quickly . /* Extract the list of windows actually in use. */ /* Make sure they all have names, for EXPLAIN's use. */ else false ;/* * Preprocess MIN / MAX aggregates , if any . Note : be careful about * adding logic between here and the query_planner ( ) call . Anything * that is needed in MIN / MAX - optimizable cases will have to be * duplicated in planagg . c . if (parse->hasAggs)/* * 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 , or SRFs in the tlist . if (parse->groupClause ||1 .0 ;else /* Set up data needed by standard_qp_callback */ /* * If we ' re a subquery for a set operation , store the SetOperationStmt * in qp_extra . /* * Generate the best unsorted and presorted paths for the scan / join * portion of this Query , ie the processing represented by the * FROM / WHERE clauses . ( 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 . /* * Convert the query ' s result tlist into PathTarget format . * * Note : this cannot be done before query_planner ( ) has performed * appendrel expansion , because that might add resjunk entries to * root - > processed_tlist . Waiting till afterwards is also helpful * because the target width estimates can use per - Var width numbers * that were obtained within query_planner ( ) . /* * If ORDER BY was given , consider whether we should use a post - sort * projection , and compute the adjusted target for preceding steps if * so . if (parse->sortClause)else /* * If we have window functions to deal with , the output from any * grouping step needs to be what the window functions want ; * otherwise , it should be sort_input_target . if (activeWindows)else /* * If we have grouping or aggregation to do , the topmost scan / join * plan node must emit what the grouping step wants ; otherwise , it * should emit grouping_target . if (have_grouping)else /* * If there are any SRFs in the targetlist , we must separate each of * these PathTargets into SRF - computing and SRF - free targets . Replace * each of the named targets with a SRF - free version , and remember the * list of additional projection steps we need to add afterwards . if (parse->hasTargetSRFs)/* final_target doesn't recompute any SRFs in sort_input_target */ /* likewise for sort_input_target vs. grouping_target */ /* likewise for grouping_target vs. scanjoin_target */ /* scanjoin_target will not have any SRFs precomputed for it */ else /* initialize lists; for most of these, dummy values are OK */ /* Apply scan/join target. */ 1 /* * Save the various upper - rel PathTargets we just computed into * root - > upper_targets [ ] . The core code doesn ' t use this , but it * provides a convenient place for extensions to get at the info . For * consistency , we save all the intermediate targets , even though some * of the corresponding upperrels might not be needed for this query . /* * If we have grouping and / or aggregation , consider ways to implement * that . We build a new upperrel representing the output of this * phase . if (have_grouping)/* Fix things up if grouping_target contains SRFs */ if (parse->hasTargetSRFs)/* * If we have window functions , consider ways to implement those . We * build a new upperrel representing the output of this phase . if (activeWindows)/* Fix things up if sort_input_target contains SRFs */ if (parse->hasTargetSRFs)/* * If there is a DISTINCT clause , consider ways to implement that . We * build a new upperrel representing the output of this phase . if (parse->distinctClause)/* end of if (setOperations) */ /* * If ORDER BY was given , consider ways to implement that , and generate a * new upperrel containing only paths that emit the correct ordering and * project the correct final_target . We can apply the original * limit_tuples limit in sort costing here , but only if there are no * postponed SRFs . if (parse->sortClause)1 .0 :/* Fix things up if final_target contains SRFs */ if (parse->hasTargetSRFs)/* * Now we are prepared to build the final - output upperrel . /* * If the input rel is marked consider_parallel and there ' s nothing that ' s * not parallel - safe in the LIMIT clause , then the final_rel can be marked * consider_parallel as well . Note that if the query has rowMarks or is * not a SELECT , consider_parallel will be false for every relation in the * query . if (current_rel->consider_parallel &&true ;/* * If the current_rel belongs to a single FDW , so does the final_rel . /* * Generate paths for the final_rel . Insert all surviving paths , with * LockRows , Limit , and / or ModifyTable steps added if needed . /* * 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 . However , root - > rowMarks * is what goes into the LockRows node . ) if (parse->rowMarks)/* * If there is a LIMIT / OFFSET clause , add the LIMIT node . if (limit_needed(parse))/* * If this is an INSERT / UPDATE / DELETE / MERGE , add the ModifyTable node . if (parse->commandType != CMD_SELECT)if (bms_membership(root->all_result_relids) == BMS_MULTIPLE)/* Inherited UPDATE/DELETE/MERGE */ int resultRelation = -1 ;/* Pass the root result rel forward to the executor. */ /* Add only leaf children to ModifyTable. */ while ((resultRelation = bms_next_member(root->leaf_result_relids,0 )/* * Also exclude any leaf rels that have turned dummy since * being added to the list , for example , by being excluded * by constraint exclusion . if (IS_DUMMY_REL(this_result_rel))continue ;/* Build per-target-rel lists needed by ModifyTable */ if (parse->commandType == CMD_UPDATE)if (this_result_rel != top_result_rel)if (parse->withCheckOptions)if (this_result_rel != top_result_rel)if (parse->returningList)if (this_result_rel != top_result_rel)if (parse->mergeActionList)/* * Copy MergeActions and translate stuff that * references attribute numbers . if (leaf_action->commandType == CMD_UPDATE)if (parse->commandType == CMD_MERGE)if (this_result_rel != top_result_rel)if (resultRelations == NIL)/* * We managed to exclude every child rel , so generate a * dummy one - relation plan using info for the top target * rel ( even though that may not be a leaf target ) . * Although it ' s clear that no data will be updated or * deleted , we still need to have a ModifyTable node so * that any statement triggers will be executed . ( This * could be cleaner if we fixed nodeModifyTable . c to allow * zero target relations , but that probably wouldn ' t be a * net win . ) if (parse->commandType == CMD_UPDATE)if (parse->withCheckOptions)if (parse->returningList)if (parse->mergeActionList)if (parse->commandType == CMD_MERGE)else /* Single-relation INSERT/UPDATE/DELETE/MERGE. */ 0 ; /* there's no separate root rel */ if (parse->commandType == CMD_UPDATE)if (parse->withCheckOptions)if (parse->returningList)if (parse->mergeActionList)if (parse->commandType == CMD_MERGE)/* * 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)else /* And shove it into final_rel */ /* * Generate partial paths for final_rel , too , if outer query levels might * be able to make use of them . if (final_rel->consider_parallel && root->query_level > 1 &&/* * If there is an FDW that ' s responsible for all baserels of the query , * let it consider adding ForeignPaths . if (final_rel->fdwroutine &&/* Let extensions possibly add some more paths */ if (create_upper_paths_hook)/* Note: currently, we leave it to callers to do set_cheapest() */ /* * Do preprocessing for groupingSets clause and related data . * * We expect that parse - > groupingSets has already been expanded into a flat * list of grouping sets ( that is , just integer Lists of ressortgroupref * numbers ) by expand_grouping_sets ( ) . This function handles the preliminary * steps of organizing the grouping sets into lists of rollups , and preparing * annotations which will later be filled in with size estimates . static grouping_sets_data *int maxref = 0 ;sizeof (grouping_sets_data));/* * We don ' t currently make any attempt to optimize the groupClause when * there are grouping sets , so just duplicate it in processed_groupClause . /* Detect unhashable and unsortable grouping expressions */ false ;if (parse->groupClause)if (ref > maxref)if (!gc->hashable)if (!OidIsValid(gc->sortop))/* Allocate workspace array for remapping */ int *) palloc((maxref + 1 ) * sizeof (int ));/* * If we have any unsortable sets , we must extract them before trying to * prepare rollups . Unsortable sets don ' t go through * reorder_grouping_sets , so we must apply the GroupingSetData annotation * here . if (!bms_is_empty(gd->unsortable_refs))if (bms_overlap_list(gd->unsortable_refs, gset))/* * We must enforce here that an unsortable set is hashable ; * later code assumes this . Parse analysis only checks that * every individual column is either hashable or sortable . * * Note that passing this test doesn ' t guarantee we can * generate a plan ; there might be other showstoppers . if (bms_overlap_list(gd->unhashable_refs, gset))"could not implement GROUP BY" ),"Some of the datatypes only support hashing, while others only support sorting." )));else if (sortable_sets)else else /* * Reorder the current list of grouping sets into correct prefix * order . If only one aggregation pass is needed , try to make the * list match the ORDER BY clause ; if more than one pass is needed , we * don ' t bother with that . * * Note that this reorders the sets from smallest - member - first to * largest - member - first , and applies the GroupingSetData annotations , * though the data will be filled in later . 1 /* * Get the initial ( and therefore largest ) grouping set . /* * Order the groupClause appropriately . If the first grouping set is * empty , then the groupClause must also be empty ; otherwise we have * to force the groupClause to match that grouping set ' s order . * * ( The first grouping set can be empty even though parse - > groupClause * is not empty only if all non - empty grouping sets are unsortable . * The groupClauses for hashed grouping sets are built later on . ) if (gs->set)else /* * Is it hashable ? We pretend empty sets are hashable even though we * actually force them not to be hashed later . But don ' t bother if * there ' s nothing but empty sets ( since in that case we can ' t hash * anything ) . if (gs->set &&true ;true ;/* * 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 . We keep the * original form for later use , though . if (gd->unsortable_sets)/* * We have not yet pinned down a groupclause for this , but we will * need index - based lists for estimation purposes . Construct * hash_sets_idx based on the entire original groupclause for now . true ;return gd;/* * Given a groupclause and a list of GroupingSetData , return equivalent sets * ( without annotation ) mapped to indexes into the given groupclause . static List *int *tleref_to_colnum_map)int ref = 0 ;return result;/* * preprocess_rowmarks - set up PlanRowMarks if needed static void 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 . else /* * We only need rowmarks for UPDATE , DELETE , MERGE , or FOR [ KEY ] * UPDATE / SHARE . if (parse->commandType != CMD_UPDATE &&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 . false , false );if (parse->resultRelation)/* * Convert RowMarkClauses to PlanRowMark representation . /* * 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 . /* * 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 ;1 << newrc->markType);false ;/* * Now , add rowmarks for any non - target , non - locked base relations . 0 ;if (!bms_is_member(i, rels))continue ;1 << newrc->markType);/* doesn't matter */ false ;/* * Select RowMarkType to use for a given table 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 */ 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 . 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 ;"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 create_limit_path , 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 double tuple_fraction,double limit_fraction;/* Should not be called unless LIMIT or OFFSET */ /* * Try to obtain the clause values . We use estimate_expression_value * primarily because it can sometimes do something useful with Params . if (parse->limitCount)if (est && IsA(est, Const ))if (((Const *) est)->constisnull)/* NULL indicates LIMIT ALL, ie, no limit */ 0 ; /* treat as not present */ else Const *) est)->constvalue);if (*count_est <= 0 )1 ; /* force to at least 1 */ else 1 ; /* can't estimate */ else 0 ; /* not present */ if (parse->limitOffset)if (est && IsA(est, Const ))if (((Const *) est)->constisnull)/* Treat NULL as no offset; the executor will too */ 0 ; /* treat as not present */ else Const *) est)->constvalue);if (*offset_est < 0 )0 ; /* treat as not present */ else 1 ; /* can't estimate */ else 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 ... */ 0 .10 ;else /* LIMIT (plus OFFSET, if any) is max number of tuples needed */ 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 */ 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 */ else /* both fractional */ else /* no info from caller, just use limit */ 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 )0 .10 ;else 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 */ else /* caller absolute, limit fractional; use limit */ else if (limit_fraction >= 1 .0 )/* caller fractional, limit absolute; use caller's value */ else /* both fractional, so add them together */ if (tuple_fraction >= 1 .0 )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 . bool 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 */ if (node)if (IsA(node, Const ))/* Treat NULL as no offset; the executor would too */ if (!((Const *) node)->constisnull)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 . * We also consider partial match between GROUP BY and ORDER BY elements , * which could allow to implement ORDER BY using the incremental sort . * * We also 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 . This is implemented during the generation of grouping * paths . See get_useful_group_keys_orderings ( ) for details . * * Note : we need no comparable processing of the distinctClause because * the parser already enforced that that matches ORDER BY . * * Note : we return a fresh List , but its elements are the same * SortGroupClauses appearing in parse - > groupClause . This is important * because later processing may modify the processed_groupClause list . * * 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 */* For grouping sets, we need to force the ordering */ if (force)return new_groupclause;/* If no ORDER BY, nothing useful to do here */ if (parse->sortClause == NIL)return list_copy(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 . if (equal(gc, sc))break ;if (gl == NULL)break ; /* no match, so stop scanning */ /* If no match at all, no point in reordering GROUP BY */ if (new_groupclause == NIL)return list_copy(parse->groupClause);/* * Add any remaining GROUP BY items to the new list . We don ' t require a * complete match , because even partial match allows ORDER BY to be * implemented using incremental sort . Also , give up if there are any * non - sortable GROUP BY items , since then there ' s no hope anyway . if (list_member_ptr(new_groupclause, gc))continue ; /* it matched an ORDER BY item */ if (!OidIsValid(gc->sortop)) /* give up, GROUP BY can't be sorted */ return list_copy(parse->groupClause);/* Success --- install the rearranged GROUP BY list */ 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 *int num_sets_raw = list_length(groupingSets);int num_empty = 0 ;int num_sets = 0 ; /* distinct sets */ int num_chains = 0 ;int *chains;short **adjacency;short *adjacency_buf;int i;int j;int j_size;/* * 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)/* 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 . * - - - - - - - - - - 1 ) * sizeof (List *));1 ) * sizeof (Bitmapset *));1 ) * sizeof (short *));1 ) * sizeof (short ));0 ;0 ;1 ;int dup_of = 0 ;/* 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))break ;else if (j_size < list_length(candidate))if (dup_of > 0 )else int k;int n_adj = 0 ;/* 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))if (n_adj > 0 )0 ] = n_adj;1 ) * sizeof (short ));1 ) * sizeof (short ));else 1 ;/* * Apply the graph matching algorithm to do the work . /* * 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 ) 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)else if (v > 0 && v < i)else /* build result lists. */ 1 ) * sizeof (List *));for (i = 1 ; i <= num_sets; ++i)int c = chains[i];0 );/* push any empty sets back on the first list. */ while (num_empty-- > 0 )1 ] = lcons(NIL, results[1 ]);/* make result list */ for (i = 1 ; i <= num_chains; ++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 . ) for (i = 1 ; i <= num_sets; ++i)if (adjacency[i])for (i = 1 ; i <= num_sets; ++i)return result;/* * Reorder the elements of a list of grouping sets such that they have correct * prefix relationships . Also inserts the GroupingSetData annotations . * * The input must be ordered with smallest sets first ; the result is returned * with largest sets first . Note that the result shares no list substructure * with the input , so it ' s safe for the caller to modify it later . * * 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 *while (list_length(sortclause) > list_length(previous) &&int ref = sc->tleSortGroupRef;if (list_member_int(new_elems, ref))else /* diverged from the sortclause; give up on it */ break ;return result;/* * has_volatile_pathkey * Returns true if any PathKey in ' keys ' has an EquivalenceClass * containing a volatile function . Otherwise returns false . static bool if (pathkey->pk_eclass->ec_has_volatile)return true ;return false ;/* * adjust_group_pathkeys_for_groupagg * Add pathkeys to root - > group_pathkeys to reflect the best set of * pre - ordered input for ordered aggregates . * * We define " best " as the pathkeys that suit the largest number of * aggregate functions . We find these by looking at the first ORDER BY / * DISTINCT aggregate and take the pathkeys for that before searching for * other aggregates that require the same or a more strict variation of the * same pathkeys . We then repeat that process for any remaining aggregates * with different pathkeys and if we find another set of pathkeys that suits a * larger number of aggregates then we select those pathkeys instead . * * When the best pathkeys are found we also mark each Aggref that can use * those pathkeys as aggpresorted = true . * * Note : When an aggregate function ' s ORDER BY / DISTINCT clause contains any * volatile functions , we never make use of these pathkeys . We want to ensure * that sorts using volatile functions are done independently in each Aggref * rather than once at the query level . If we were to allow this then Aggrefs * with compatible sort orders would all transition their rows in the same * order if those pathkeys were deemed to be the best pathkeys to sort on . * Whereas , if some other set of Aggref ' s pathkeys happened to be deemed * better pathkeys to sort on , then the volatile function Aggrefs would be * left to perform their sorts individually . To avoid this inconsistent * behavior which could make Aggref results depend on what other Aggrefs the * query contains , we always force Aggrefs with volatile functions to perform * their own sorts . static void int i;/* Shouldn't be here if there are grouping sets */ /* Shouldn't be here unless there are some ordered aggregates */ 0 );/* Do nothing if disabled */ if (!enable_presorted_aggregate)return ;/* * Make a first pass over all AggInfos to collect a Bitmapset containing * the indexes of all AggInfos to be processed below . if (AGGKIND_IS_ORDERED_SET(aggref->aggkind))continue ;/* Skip unless there's a DISTINCT or ORDER BY clause */ if (aggref->aggdistinct == NIL && aggref->aggorder == NIL)continue ;/* Additional safety checks are needed if there's a FILTER clause */ if (aggref->aggfilter != NULL)bool allow_presort = true ;/* * When the Aggref has a FILTER clause , it ' s possible that the * filter removes rows that cannot be sorted because the * expression to sort by results in an error during its * evaluation . This is a problem for presorting as that happens * before the FILTER , whereas without presorting , the Aggregate * node will apply the FILTER * before * sorting . So that we never * try to sort anything that might error , here we aim to skip over * any Aggrefs with arguments with expressions which , when * evaluated , could cause an ERROR . Vars and Consts are ok . There * may be more cases that should be allowed , but more thought * needs to be given . Err on the side of caution . while (IsA(expr, RelabelType))/* Common case, Vars and Consts are ok */ if (IsA(expr, Var) || IsA(expr, Const ))continue ;/* Unsupported. Don't try to presort for this Aggref */ false ;break ;/* Skip unsupported Aggrefs */ if (!allow_presort)continue ;/* * Now process all the unprocessed_aggs to find the best set of pathkeys * for the given set of aggregates . * * On the first outer loop here ' bestaggs ' will be empty . We ' ll populate * this during the first loop using the pathkeys for the very first * AggInfo then taking any stronger pathkeys from any other AggInfos with * a more strict set of compatible pathkeys . Once the outer loop is * complete , we mark off all the aggregates with compatible pathkeys then * remove those from the unprocessed_aggs and repeat the process to try to * find another set of pathkeys that are suitable for a larger number of * aggregates . The outer loop will stop when there are not enough * unprocessed aggregates for it to be possible to find a set of pathkeys * to suit a larger number of aggregates . while (bms_num_members(unprocessed_aggs) > bms_num_members(bestaggs))1 ;while ((i = bms_next_member(unprocessed_aggs, i)) >= 0 )if (aggref->aggdistinct != NIL)else /* * Ignore Aggrefs which have volatile functions in their ORDER BY * or DISTINCT clause . if (has_volatile_pathkey(pathkeys))continue ;/* * When not set yet , take the pathkeys from the first unprocessed * aggregate . if (currpathkeys == NIL)/* include the GROUP BY pathkeys, if they exist */ if (grouppathkeys != NIL)/* record that we found pathkeys for this aggregate */ else /* now look for a stronger set of matching pathkeys */ /* include the GROUP BY pathkeys, if they exist */ if (grouppathkeys != NIL)/* are 'pathkeys' compatible or better than 'currpathkeys'? */ switch (compare_pathkeys(currpathkeys, pathkeys))case PATHKEYS_BETTER2:/* 'pathkeys' are stronger, use these ones instead */ /* FALLTHROUGH */ case PATHKEYS_BETTER1:/* 'pathkeys' are less strict */ /* FALLTHROUGH */ case PATHKEYS_EQUAL:/* mark this aggregate as covered by 'currpathkeys' */ break ;case PATHKEYS_DIFFERENT:break ;/* remove the aggregates that we've just processed */ /* * If this pass included more aggregates than the previous best then * use these ones as the best set . if (bms_num_members(aggindexes) > bms_num_members(bestaggs))/* * If we found any ordered aggregates , update root - > group_pathkeys to add * the best set of aggregate pathkeys . Note that bestpathkeys includes * the original GROUP BY pathkeys already . if (bestpathkeys != NIL)/* * Now that we ' ve found the best set of aggregates we can set the * presorted flag to indicate to the executor that it needn ' t bother * performing a sort for these Aggrefs . We ' re able to do this now as * there ' s no chance of a Hash Aggregate plan as create_grouping_paths * will not mark the GROUP BY as GROUPING_CAN_USE_HASH due to the presence * of ordered aggregates . 1 ;while ((i = bms_next_member(bestaggs, i)) >= 0 )true ;/* * Compute query_pathkeys and other pathkeys during plan generation static void void *extra)/* * Calculate pathkeys that represent grouping / ordering and / or ordered * aggregate requirements . if (qp_extra->gset_data)/* * With grouping sets , just use the first RollupData ' s groupClause . We * don ' t make any effort to optimize grouping clauses when there are * grouping sets , nor can we combine aggregate ordering keys with * grouping . if (grouping_is_sortable(groupClause))bool sortable;/* * The groupClause is logically below the grouping step . So if * there is an RTE entry for the grouping step , we need to remove * its RT index from the sort expressions before we make PathKeys * for them . false ,false );else 0 ;else if (parse->groupClause || root->numOrderedAggs > 0 )/* * With a plain GROUP BY list , we can remove any grouping items that * are proven redundant by EquivalenceClass processing . For example , * we can remove y given " WHERE x = y GROUP BY x , y " . These aren ' t * especially common cases , but they ' re nearly free to detect . Note * that we remove redundant items from processed_groupClause but not * the original parse - > groupClause . bool sortable;/* * Convert group clauses into pathkeys . Set the ec_sortref field of * EquivalenceClass ' es if it ' s not set yet . true ,false ,true );if (!sortable)/* Can't sort; no point in considering aggregate ordering either */ 0 ;else /* If we have ordered aggs, consider adding onto group_pathkeys */ if (root->numOrderedAggs > 0 )else 0 ;/* We consider only the first (bottom) window in pathkeys logic */ if (activeWindows != NIL)else /* * As with GROUP BY , we can discard any DISTINCT items that are proven * redundant by EquivalenceClass processing . The non - redundant list is * kept in root - > processed_distinctClause , leaving the original * parse - > distinctClause alone . if (parse->distinctClause)bool sortable;/* Make a copy since pathkey processing can modify the list */ true ,false ,false );if (!sortable)else /* setting setop_pathkeys might be useful to the union planner */ if (qp_extra->setop != NULL)bool sortable;false ,false ,false );if (!sortable)else /* * 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 . Otherwise , if we ' re a subquery being planned * for a set operation which can benefit from presorted results and have a * sortable targetlist , we want to sort by the target list . * * 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)else if (root->window_pathkeys)else if (list_length(root->distinct_pathkeys) >else if (root->sort_pathkeys)else if (root->setop_pathkeys != NIL)else /* * Estimate number of groups produced by grouping clauses ( 1 if not grouping ) * * path_rows : number of output rows from scan / join step * gd : grouping sets data including list of grouping sets and their clauses * target_list : target list containing group clause references * * If doing grouping sets , we also annotate the gsets data with the estimates * for each set and each individual rollup list , with a view to later * determining whether some combination of them could be hashed instead . static double double path_rows,double dNumGroups;if (parse->groupClause)if (parse->groupingSets)/* Add up the estimates for each grouping set */ /* keep Coverity happy */ 0 ;0 .0 ;double numGroups = estimate_num_groups(root,if (gd->hash_sets_idx)0 ;double numGroups = estimate_num_groups(root,else /* Plain GROUP BY -- estimate based on optimized groupClause */ else if (parse->groupingSets)/* Empty grouping sets ... one result row for each one */ else if (parse->hasAggs || root->hasHavingQual)/* Plain aggregation, one result row */ 1 ;else /* Not grouping */ 1 ;return dNumGroups;/* * create_grouping_paths * * Build a new upperrel containing Paths for grouping and / or aggregation . * Along the way , we also build an upperrel for Paths which are partially * grouped and / or aggregated . A partially grouped and / or aggregated path * needs a FinalizeAggregate node to complete the aggregation . Currently , * the only partially grouped paths we build are also partial paths ; that * is , they need a Gather and then a FinalizeAggregate . * * input_rel : contains the source - data Paths * target : the pathtarget for the result Paths to compute * gd : grouping sets data including list of grouping sets and their clauses * * Note : all Paths in input_rel are expected to return the target computed * by make_group_input_target . static RelOptInfo *bool target_parallel_safe,0 , sizeof (AggClauseCosts));/* * Create grouping relation to hold fully aggregated grouping and / or * aggregation paths . /* * Create either paths for a degenerate grouping or paths for ordinary * grouping , as appropriate . if (is_degenerate_grouping(root))else int flags = 0 ;/* * Determine whether it ' s possible to perform sort - based * implementations of grouping . ( Note that if processed_groupClause * is empty , grouping_is_sortable ( ) is trivially true , and all the * pathkeys_contained_in ( ) tests will succeed too , so that we ' ll * consider every surviving input path . ) * * If we have grouping sets , we might be able to sort some but not all * of them ; in this case , we need can_sort to be true as long as we * must consider any sorted - input plan . if ((gd && gd->rollups != NIL)/* * Determine whether we should consider hash - based implementations of * grouping . * * Hashed aggregation only applies if we ' re grouping . If we have * grouping sets , some groups might be hashable but others not ; in * this case we set can_hash true as long as there is nothing globally * preventing us from hashing ( and we should therefore consider plans * with hashes ) . * * 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 also included in the numOrderedAggs count . * * Note : grouping_is_hashable ( ) is much more expensive to check than * the other gating conditions , so we want to do it last . if ((parse->groupClause != NIL &&0 &&/* * Determine whether partial aggregation is possible . if (can_partial_agg(root))false ;/* * Determine whether partitionwise aggregation is in theory possible . * It can be disabled by the user , and for now , we don ' t try to * support grouping sets . create_ordinary_grouping_paths ( ) will check * additional conditions , such as whether input_rel is partitioned . if (enable_partitionwise_aggregate && !parse->groupingSets)else return grouped_rel;/* * make_grouping_rel * * Create a new grouping rel and set basic properties . * * input_rel represents the underlying scan / join relation . * target is the output expected from the grouping relation . static RelOptInfo *bool target_parallel_safe,if (IS_OTHER_REL(input_rel))else /* * By tradition , the relids set for the main grouping relation is * NULL . ( This could be changed , but might require adjustments * elsewhere . ) /* Set target. */ /* * If the input relation is not parallel - safe , then the grouped relation * can ' t be parallel - safe , either . Otherwise , it ' s parallel - safe if the * target list and HAVING quals are parallel - safe . if (input_rel->consider_parallel && target_parallel_safe &&true ;/* * If the input rel belongs to a single FDW , so does the grouped rel . return grouped_rel;/* * is_degenerate_grouping * * A degenerate grouping is one in which the query has a HAVING qual and / or * grouping sets , but no aggregates and no GROUP BY ( which implies that the * grouping sets are all empty ) . static bool return (root->hasHavingQual || parse->groupingSets) &&/* * create_degenerate_grouping_paths * * When the grouping is degenerate ( see is_degenerate_grouping ) , we are * supposed to emit either zero or one 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 module to avoid having to generate the earlier paths * in the first place . static void int nrows;if (nrows > 1 )/* * Doesn ' t seem worthwhile writing code to cons up a generate_series * or a values scan to emit multiple rows . Instead just make N clones * and append them . ( With a volatile HAVING clause , this means you * might get between 0 and N output rows . Offhand I think that ' s * desired . ) while (--nrows >= 0 )0 ,false ,1 );else /* No grouping sets, or just one, so one output row */ /* * create_ordinary_grouping_paths * * Create grouping paths for the ordinary ( that is , non - degenerate ) case . * * We need to consider sorted and hashed aggregation in the same function , * because otherwise ( 1 ) it would be harder to throw an appropriate error * message if neither way works , and ( 2 ) we should not allow hashtable size * considerations to dissuade us from using hashing if sorting is not possible . * * * partially_grouped_rel_p will be set to the partially grouped rel which this * function creates , or to NULL if it doesn ' t create one . static void const AggClauseCosts *agg_costs,double dNumGroups;/* * If this is the topmost grouping relation or if the parent relation is * doing some form of partitionwise aggregation , then we may be able to do * it at this level also . However , if the input relation is not * partitioned , partitionwise aggregate is impossible . if (extra->patype != PARTITIONWISE_AGGREGATE_NONE &&/* * If this is the topmost relation or if the parent relation is doing * full partitionwise aggregation , then we can do full partitionwise * aggregation provided that the GROUP BY clause contains all of the * partitioning columns at this level and the collation used by GROUP * BY matches the partitioning collation . Otherwise , we can do at * most partial partitionwise aggregation . But if partial aggregation * is not supported in general then we can ' t use it for partitionwise * aggregation either . * * Check parse - > groupClause not processed_groupClause , because it ' s * okay if some of the partitioning columns were proved redundant . if (extra->patype == PARTITIONWISE_AGGREGATE_FULL &&else if ((extra->flags & GROUPING_CAN_PARTIAL_AGG) != 0 )else /* * Before generating paths for grouped_rel , we first generate any possible * partially grouped paths ; that way , later code can easily consider both * parallel and non - parallel approaches to grouping . if ((extra->flags & GROUPING_CAN_PARTIAL_AGG) != 0 )bool force_rel_creation;/* * If we ' re doing partitionwise aggregation at this level , force * creation of a partially_grouped_rel so we can add partitionwise * paths to it . /* Set out parameter. */ /* Apply partitionwise aggregation technique, if possible. */ if (patype != PARTITIONWISE_AGGREGATE_NONE)/* If we are doing partial aggregation only, return. */ if (extra->patype == PARTITIONWISE_AGGREGATE_PARTIAL)if (partially_grouped_rel->pathlist)return ;/* Gather any partially grouped partial paths. */ if (partially_grouped_rel && partially_grouped_rel->partial_pathlist)/* * Estimate number of groups . /* Build final grouping paths */ /* Give a helpful error if we failed to find any implementation */ if (grouped_rel->pathlist == NIL)"could not implement GROUP BY" ),"Some of the datatypes only support hashing, while others only support sorting." )));/* * If there is an FDW that ' s responsible for all baserels of the query , * let it consider adding ForeignPaths . if (grouped_rel->fdwroutine &&/* Let extensions possibly add some more paths */ if (create_upper_paths_hook)/* * For a given input path , consider the possible ways of doing grouping sets on * it , by combinations of hashing and sorting . This can be called multiple * times , so it ' s important that it not scribble on input . No result is * returned , but any generated paths are added to grouped_rel . static void bool is_sorted,bool can_hash,const AggClauseCosts *agg_costs,double dNumGroups)/* * If we ' re not being offered sorted input , then only consider plans that * can be done entirely by hashing . * * We can hash everything if it looks like it ' ll fit in hash_mem . But if * the input is actually sorted despite not being advertised as such , we * prefer to make use of that in order to use less memory . * * If none of the grouping sets are sortable , then ignore the hash_mem * limit and generate a path anyway , since otherwise we ' ll just fail . if (!is_sorted)double hashsize;double exclude_groups = 0 .0 ;/* * If the input is coincidentally sorted usefully ( which can happen * even if is_sorted is false , since that only means that our caller * has set up the sorting for us ) , then save some hashtable space by * making use of that . But we need to watch out for degenerate cases : * * 1 ) If there are any empty grouping sets , then group_pathkeys might * be NIL if all non - empty grouping sets are unsortable . In this case , * there will be a rollup containing only empty groups , and the * pathkeys_contained_in test is vacuously true ; this is ok . * * XXX : the above relies on the fact that group_pathkeys is generated * from the first rollup . If we add the ability to consider multiple * sort orders for grouping input , this assumption might fail . * * 2 ) If there are no empty sets and only unsortable sets , then the * rollups list will be empty ( and thus l_start = = NULL ) , and * group_pathkeys will be NIL ; we must ensure that the vacuously - true * pathkeys_contained_in test doesn ' t cause us to crash . if (l_start != NULL &&/* * gd - > rollups is empty if we have only unsortable columns to work * with . Override hash_mem in that case ; otherwise , we ' ll rely on the * sorted - input case to generate usable mixed paths . if (hashsize > hash_mem_limit && gd->rollups)return ; /* nope, won't fit */ /* * We need to burst the existing rollups list into individual grouping * sets and recompute a groupClause for each set . /* * If we find an unhashable rollup that ' s not been skipped by the * " actually sorted " check above , we can ' t cope ; we ' d need sorted * input ( with a different sort order ) but we can ' t get that here . * So bail out ; we ' ll get a valid path from the is_sorted case * instead . * * The mere presence of empty grouping sets doesn ' t make a rollup * unhashable ( see preprocess_grouping_sets ) , we handle those * specially below . if (!rollup->hashable)return ;if (gset == NIL)/* Empty grouping sets can't be hashed. */ else true ;true ;/* * If we didn ' t find anything nonempty to hash , then bail . We ' ll * generate a path from the is_sorted case . if (new_rollups == NIL)return ;/* * If there were empty grouping sets they should have been in the * first rollup . if (unhashed_rollup)else if (empty_sets)false ;false ;return ;/* * If we have sorted input but nothing we can do with it , bail . if (gd->rollups == NIL)return ;/* * Given sorted input , we try and make two paths : one sorted and one mixed * sort / hash . ( We need to try both because hashagg might be disabled , or * some columns might not be sortable . ) * * can_hash is passed in as false if some obstacle elsewhere ( such as * ordered aggs ) means that we shouldn ' t consider hashing at all . if (can_hash && gd->any_hashable)double availspace = hash_mem_limit;/* * Account first for space needed for groups we can ' t sort at all . if (availspace > 0 && list_length(gd->rollups) > 1 )double scale;int num_rollups = list_length(gd->rollups);int k_capacity;int *k_weights = palloc(num_rollups * sizeof (int ));int i;/* * We treat this as a knapsack problem : the knapsack capacity * represents hash_mem , the item weights are the estimated memory * usage of the hashtables needed to implement a single rollup , * and we really ought to use the cost saving as the item value ; * however , currently the costs assigned to sort nodes don ' t * reflect the comparison costs well , and so we treat all items as * of equal value ( each rollup we hash instead saves us one sort ) . * * To use the discrete knapsack , we need to scale the values to a * reasonably small bounded range . We choose to allow a 5 % error * margin ; we have no more than 4096 rollups in the worst possible * case , which with a 5 % error margin will require a bit over 42 MB * of workspace . ( Anyone wanting to plan queries that complex had * better have the memory for it . In more reasonable cases , with * no more than a couple of dozen rollups , the memory usage will * be negligible . ) * * k_capacity is naturally bounded , but we clamp the values for * scale and weight ( below ) to avoid overflows or underflows ( or * uselessly trying to use a scale factor less than 1 byte ) . 20 .0 * num_rollups), 1 .0 );int ) floor(availspace / scale);/* * We leave the first rollup out of consideration since it ' s the * one that matches the input sort order . We assign indexes " i " * to only those entries considered for hashing ; the second loop , * below , must use the same condition . 0 ;1 )if (rollup->hashable)double sz = estimate_hashagg_tablesize(root,/* * If sz is enormous , but hash_mem ( and hence scale ) is * small , avoid integer overflow here . int ) Min(floor(sz / scale),1 .0 );/* * Apply knapsack algorithm ; compute the set of items which * maximizes the value stored ( in this case the number of sorts * saved ) while keeping the total size ( approximately ) within * capacity . if (i > 0 )if (!bms_is_empty(hash_items))0 ;1 )if (rollup->hashable)if (bms_is_member(i, hash_items))else else if (!rollups && hash_sets)true ;true ;if (rollups)/* * Now try the simple sorted case . if (!gd->unsortable_sets)/* * create_window_paths * * Build a new upperrel containing Paths for window - function evaluation . * * input_rel : contains the source - data Paths * input_target : result of make_window_input_target * output_target : what the topmost WindowAggPath should return * wflists : result of find_window_functions * activeWindows : result of select_active_windows * * Note : all Paths in input_rel are expected to return input_target . static RelOptInfo *bool output_target_parallel_safe,/* For now, do all work in the (WINDOW, NULL) upperrel */ /* * If the input relation is not parallel - safe , then the window relation * can ' t be parallel - safe , either . Otherwise , we need to examine the * target list and active windows for non - parallel - safe constructs . if (input_rel->consider_parallel && output_target_parallel_safe &&true ;/* * If the input rel belongs to a single FDW , so does the window rel . /* * Consider computing window functions starting from the existing * cheapest - total path ( which will likely require a sort ) as well as any * existing paths that satisfy or partially satisfy root - > window_pathkeys . int presorted_keys;if (path == input_rel->cheapest_total_path ||0 )/* * If there is an FDW that ' s responsible for all baserels of the query , * let it consider adding ForeignPaths . if (window_rel->fdwroutine &&/* Let extensions possibly add some more paths */ if (create_upper_paths_hook)/* Now choose the best path(s) */ return window_rel;/* * Stack window - function implementation steps atop the given Path , and * add the result to window_rel . * * window_rel : upperrel to contain result * path : input Path to use ( must return input_target ) * input_target : result of make_window_input_target * output_target : what the topmost WindowAggPath should return * wflists : result of find_window_functions * activeWindows : result of select_active_windows static void /* * Since each window clause could require a different sort order , we stack * up a WindowAgg node for each clause , with sort steps between them as * needed . ( We assume that select_active_windows chose a good order for * executing the clauses in . ) * * input_target should contain all Vars and Aggs needed for 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 . ) It must also * contain all window partitioning and sorting expressions , 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 . int presorted_keys;bool is_sorted;bool topwindow;/* Sort if necessary */ if (!is_sorted)/* * No presorted keys or incremental sort disabled , just perform a * complete sort . if (presorted_keys == 0 || !enable_incremental_sort)1 .0 );else /* * Since we have presorted keys and incremental sort is * enabled , just use incremental sort . 1 .0 );if (lnext(activeWindows, l))/* * Add the current WindowFuncs to the output target for this * intermediate WindowAggPath . We must copy window_target to * avoid changing the previous path ' s target . * * Note : a WindowFunc adds nothing to the target ' s eval costs ; but * we do need to account for the increase in tlist width . 0 );1 );else /* Install the goal target in the topmost WindowAgg */ /* mark the final item in the list as the top-level window */ 1 ;/* * Collect the WindowFuncRunConditions from each WindowFunc and * convert them into OpExprs if (wfuncrc->wfunc_left)else false ,if (!topwindow)/* * create_distinct_paths * * Build a new upperrel containing Paths for SELECT DISTINCT evaluation . * * input_rel : contains the source - data Paths * target : the pathtarget for the result Paths to compute * * Note : input paths should already compute the desired pathtarget , since * Sort / Unique won ' t project anything . static RelOptInfo */* For now, do all work in the (DISTINCT, NULL) upperrel */ /* * We don ' t compute anything at this level , so distinct_rel will be * parallel - safe if the input rel is parallel - safe . In particular , if * there is a DISTINCT ON ( . . . ) clause , any path for the input_rel will * output those expressions , and will not be parallel - safe unless those * expressions are parallel - safe . /* * If the input rel belongs to a single FDW , so does the distinct_rel . /* build distinct paths based on input_rel's pathlist */ /* now build distinct paths based on input_rel's partial_pathlist */ /* Give a helpful error if we failed to create any paths */ if (distinct_rel->pathlist == NIL)"could not implement DISTINCT" ),"Some of the datatypes only support hashing, while others only support sorting." )));/* * If there is an FDW that ' s responsible for all baserels of the query , * let it consider adding ForeignPaths . if (distinct_rel->fdwroutine &&/* Let extensions possibly add some more paths */ if (create_upper_paths_hook)/* Now choose the best path(s) */ return distinct_rel;/* * create_partial_distinct_paths * * Process ' input_rel ' partial paths and add unique / aggregate paths to the * UPPERREL_PARTIAL_DISTINCT rel . For paths created , add Gather / GatherMerge * paths on top and add a final unique / aggregate path to remove any duplicate * produced from combining rows from parallel workers . static void double numDistinctRows;/* nothing to do when there are no partial paths in the input rel */ if (!input_rel->consider_parallel || input_rel->partial_pathlist == NIL)return ;/* can't do parallel DISTINCT ON */ if (parse->hasDistinctOn)return ;/* * If input_rel belongs to a single FDW , so does the partial_distinct_rel . /* estimate how many distinct rows we'll get from each worker */ /* * Try sorting the cheapest path and incrementally sorting any paths with * presorted keys and put a unique paths atop of those . We ' ll also * attempt to reorder the required pathkeys to match the input path ' s * pathkeys as much as possible , in hopes of avoiding a possible need to * re - sort . if (grouping_is_sortable(root->processed_distinctClause))0 );1 .0 );if (sorted_path == NULL)continue ;/* * An empty distinct_pathkeys means all tuples have the same * value for the DISTINCT clause . See * create_final_distinct_paths ( ) if (root->distinct_pathkeys == NIL)1 , InvalidOid,sizeof (int64),1 ), false ,/* * Apply a LimitPath onto the partial path to restrict the * tuples from each worker to 1 . * create_final_distinct_paths will need to apply an * additional LimitPath to restrict this to a single row * after the Gather node . If the query already has a * LIMIT clause , then we could end up with three Limit * nodes in the final plan . Consolidating the top two of * these could be done , but does not seem worth troubling * over . 0 , 1 ));else /* * Now try hash aggregate paths , if enabled and hashing is possible . Since * we ' re not on the hook to ensure we do our best to create at least one * path here , we treat enable_hashagg as a hard off - switch rather than the * slightly softer variant in create_final_distinct_paths . if (enable_hashagg && grouping_is_hashable(root->processed_distinctClause))/* * If there is an FDW that ' s responsible for all baserels of the query , * let it consider adding ForeignPaths . if (partial_distinct_rel->fdwroutine &&/* Let extensions possibly add some more partial paths */ if (create_upper_paths_hook)if (partial_distinct_rel->partial_pathlist != NIL)true );/* * Finally , create paths to distinctify the final result . This step * is needed to remove any duplicates due to combining rows from * parallel workers . /* * create_final_distinct_paths * Create distinct paths in ' distinct_rel ' based on ' input_rel ' pathlist * * input_rel : contains the source - data paths * distinct_rel : destination relation for storing created paths static RelOptInfo *double numDistinctRows;bool allow_hash;/* Estimate number of distinct rows there will be */ if (parse->groupClause || parse->groupingSets || parse->hasAggs ||/* * If there was grouping or aggregation , use the number of input rows * as the estimated number of DISTINCT rows ( ie , assume the input is * already mostly unique ) . else /* * Otherwise , the UNIQUE filter has effects comparable to GROUP BY . /* * Consider sort - based implementations of DISTINCT , if possible . if (grouping_is_sortable(root->processed_distinctClause))/* * Firstly , if we have any adequately - presorted paths , just stick a * Unique node on those . We also , consider doing an explicit sort of * the cheapest input path and Unique ' ing that . If any paths have * presorted keys then we ' ll create an incremental sort atop of those * before adding a unique node on the top . We ' ll also attempt to * reorder the required pathkeys to match the input path ' s pathkeys as * much as possible , in hopes of avoiding a possible need to re - sort . * * When we have DISTINCT ON , we must sort by the more rigorous of * DISTINCT and ORDER BY , else it won ' t have the desired behavior . * Also , if we do have to do an explicit sort , we might as well use * the more rigorous ordering to avoid a second sort later . ( Note * that the parser will have ensured that one clause is a prefix of * the other . ) double limittuples = root->distinct_pathkeys == NIL ? 1 .0 : -1 .0 ;if (parse->hasDistinctOn &&else 0 );if (sorted_path == NULL)continue ;/* * distinct_pathkeys may have become empty if all of the * pathkeys were determined to be redundant . If all of the * pathkeys are redundant then each DISTINCT target must only * allow a single value , therefore all resulting tuples must * be identical ( or at least indistinguishable by an equality * check ) . We can uniquify these tuples simply by just taking * the first tuple . All we do here is add a path to do " LIMIT * 1 " atop of ' sorted_path ' . When doing a DISTINCT ON we may * still have a non - NIL sort_pathkeys list , so we must still * only do this with paths which are correctly sorted by * sort_pathkeys . if (root->distinct_pathkeys == NIL)1 , InvalidOid,sizeof (int64),1 ), false ,/* * If the query already has a LIMIT clause , then we could * end up with a duplicate LimitPath in the final plan . * That does not seem worth troubling over too much . 0 , 1 ));else /* * Consider hash - based implementations of DISTINCT , if possible . * * If we were not able to make any other types of path , we * must * hash or * die trying . If we do have other choices , there are two things that * should prevent selection of hashing : if the query uses DISTINCT ON * ( because it won ' t really have the expected behavior if we hash ) , or if * enable_hashagg is off . * * Note : grouping_is_hashable ( ) is much more expensive to check than the * other gating conditions , so we want to do it last . if (distinct_rel->pathlist == NIL)true ; /* we have no alternatives */ else if (parse->hasDistinctOn || !enable_hashagg)false ; /* policy-based decision not to hash */ else true ; /* default */ if (allow_hash && grouping_is_hashable(root->processed_distinctClause))/* Generate hashed aggregate path --- no sort needed */ return distinct_rel;/* * get_useful_pathkeys_for_distinct * Get useful orderings of pathkeys for distinctClause by reordering * ' needed_pathkeys ' to match the given ' path_pathkeys ' as much as possible . * * This returns a list of pathkeys that can be useful for DISTINCT or DISTINCT * ON clause . For convenience , it always includes the given ' needed_pathkeys ' . static List */* always include the given 'needed_pathkeys' */ if (!enable_distinct_reordering)return useful_pathkeys_list;/* * Scan the given ' path_pathkeys ' and construct a list of PathKey nodes * that match ' needed_pathkeys ' , but only up to the longest matching * prefix . * * When we have DISTINCT ON , we must ensure that the resulting pathkey * list matches initial distinctClause pathkeys ; otherwise , it won ' t have * the desired behavior . /* * The PathKey nodes are canonical , so they can be checked for * equality by simple pointer comparison . if (!list_member_ptr(needed_pathkeys, pathkey))break ;if (root->parse->hasDistinctOn &&break ;/* If no match at all, no point in reordering needed_pathkeys */ if (useful_pathkeys == NIL)return useful_pathkeys_list;/* * If not full match , the resulting pathkey list is not useful without * incremental sort . if (list_length(useful_pathkeys) < list_length(needed_pathkeys) &&return useful_pathkeys_list;/* Append the remaining PathKey nodes in needed_pathkeys */ /* * If the resulting pathkey list is the same as the ' needed_pathkeys ' , * just drop it . if (compare_pathkeys(needed_pathkeys,return useful_pathkeys_list;return useful_pathkeys_list;/* * create_ordered_paths * * Build a new upperrel containing Paths for ORDER BY evaluation . * * All paths in the result must satisfy the ORDER BY ordering . * The only new paths we need consider are an explicit full sort * and incremental sort on the cheapest - total existing path . * * input_rel : contains the source - data Paths * target : the output tlist the result Paths must emit * limit_tuples : estimated bound on the number of output tuples , * or - 1 if no LIMIT or couldn ' t estimate * * XXX This only looks at sort_pathkeys . I wonder if it needs to look at the * other pathkeys ( grouping , . . . ) like generate_useful_gather_paths . static RelOptInfo *bool target_parallel_safe,double limit_tuples)/* For now, do all work in the (ORDERED, NULL) upperrel */ /* * If the input relation is not parallel - safe , then the ordered relation * can ' t be parallel - safe , either . Otherwise , it ' s parallel - safe if the * target list is parallel - safe . if (input_rel->consider_parallel && target_parallel_safe)true ;/* * If the input rel belongs to a single FDW , so does the ordered_rel . bool is_sorted;int presorted_keys;if (is_sorted)else /* * Try at least sorting the cheapest path and also try * incrementally sorting any path which is partially sorted * already ( no need to deal with paths which have presorted keys * when incremental sort is disabled unless it ' s the cheapest * input path ) . if (input_path != cheapest_input_path &&0 || !enable_incremental_sort))continue ;/* * We ' ve no need to consider both a sort and incremental sort . * We ' ll just do a sort if there are no presorted keys and an * incremental sort when there are presorted keys . if (presorted_keys == 0 || !enable_incremental_sort)else /* * If the pathtarget of the result path has different expressions from * the target to be applied , a projection step is needed . if (!equal(sorted_path->pathtarget->exprs, target->exprs))/* * generate_gather_paths ( ) will have already generated a simple Gather * path for the best parallel path , if any , and the loop above will have * considered sorting it . Similarly , generate_gather_paths ( ) will also * have generated order - preserving Gather Merge plans which can be used * without sorting if they happen to match the sort_pathkeys , and the loop * above will have handled those as well . However , there ' s one more * possibility : it may make sense to sort the cheapest partial path or * incrementally sort any partial path that is partially sorted according * to the required output order and then use Gather Merge . if (ordered_rel->consider_parallel && root->sort_pathkeys != NIL &&bool is_sorted;int presorted_keys;double total_groups;if (is_sorted)continue ;/* * Try at least sorting the cheapest path and also try * incrementally sorting any path which is partially sorted * already ( no need to deal with paths which have presorted keys * when incremental sort is disabled unless it ' s the cheapest * partial path ) . if (input_path != cheapest_partial_path &&0 || !enable_incremental_sort))continue ;/* * We ' ve no need to consider both a sort and incremental sort . * We ' ll just do a sort if there are no presorted keys and an * incremental sort when there are presorted keys . if (presorted_keys == 0 || !enable_incremental_sort)else /* * If the pathtarget of the result path has different expressions * from the target to be applied , a projection step is needed . if (!equal(sorted_path->pathtarget->exprs, target->exprs))/* * If there is an FDW that ' s responsible for all baserels of the query , * let it consider adding ForeignPaths . if (ordered_rel->fdwroutine &&/* Let extensions possibly add some more paths */ if (create_upper_paths_hook)/* * No need to bother with set_cheapest here ; grouping_planner does not * need us to do it . return ordered_rel;/* * make_group_input_target * Generate appropriate PathTarget for initial input to grouping nodes . * * If there is grouping or aggregation , the scan / join subplan cannot emit * the query ' s final targetlist ; for example , it certainly can ' t emit any * aggregate function calls . This routine generates the correct target * for the scan / join subplan . * * The query 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 ; other expressions * will be computed by the upper plan 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 . * * ' final_target ' is the query ' s final target list ( in PathTarget form ) * * The result is the PathTarget to be computed by the Paths returned from * query_planner ( ) . static PathTarget *int i;/* * We must build a target containing all grouping columns , plus any other * Vars mentioned in the query ' s targetlist and HAVING qual . 0 ;if (sgref && root->processed_groupClause &&/* * It ' s a grouping column , so add it to the input target as - is . * * Note that the target is logically below the grouping step . So * with grouping sets we need to remove the RT index of the * grouping step if there is any from the target expression . if (parse->hasGroupRTE && parse->groupingSets != NIL)0 );else /* * Non - grouping column , so just remember the expression for later * call to pull_var_clause . /* * If there ' s a HAVING clause , we ' ll need the Vars it uses , too . if (parse->havingQual)/* * Pull out all the Vars mentioned in non - group cols ( plus HAVING ) , and * add them to the input target 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 and * WindowFuncs will be pulled out here , too . * * Note that the target is logically below the grouping step . So with * grouping sets we need to remove the RT index of the grouping step if * there is any from the non - group Vars . if (parse->hasGroupRTE && parse->groupingSets != NIL)0 );/* clean up cruft */ /* XXX this causes some redundant cost calculation ... */ return set_pathtarget_cost_width(root, input_target);/* * make_partial_grouping_target * Generate appropriate PathTarget for output of partial aggregate * ( or partial grouping , if there are no aggregates ) nodes . * * A partial aggregation node needs to emit all the same aggregates that * a regular aggregation node would , plus any aggregates used in HAVING ; * except that the Aggref nodes should be marked as partial aggregates . * * In addition , we ' d better emit any Vars and PlaceHolderVars that are * used outside of Aggrefs in the aggregation tlist and HAVING . ( Presumably , * these would be Vars that are grouped by or used in grouping expressions . ) * * grouping_target is the tlist to be emitted by the topmost aggregation step . * havingQual represents the HAVING clause . static PathTarget *int i;0 ;if (sgref && root->processed_groupClause &&/* * It ' s a grouping column , so add it to the partial_target as - is . * ( This allows the upper agg step to repeat the grouping calcs . ) else /* * Non - grouping column , so just remember the expression for later * call to pull_var_clause . /* * If there ' s a HAVING clause , we ' ll need the Vars / Aggrefs it uses , too . if (havingQual)/* * Pull out all the Vars , PlaceHolderVars , and Aggrefs mentioned in * non - group cols ( plus HAVING ) , and add them to the partial_target if not * already present . ( An expression 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 . /* * Adjust Aggrefs to put them in partial mode . At this point all Aggrefs * are at the top level of the target list , so we can just scan the list * rather than recursing through the expression trees . if (IsA(aggref, Aggref))/* * We shouldn ' t need to copy the substructure of the Aggref node , * but flat - copy the node itself to avoid damaging other trees . sizeof (Aggref));/* For now, assume serialization is required */ /* clean up cruft */ /* XXX this causes some redundant cost calculation ... */ return set_pathtarget_cost_width(root, partial_target);/* * mark_partial_aggref * Adjust an Aggref to make it represent a partial - aggregation step . * * The Aggref node is modified in - place ; caller must do any copying required . void /* aggtranstype should be computed by this point */ /* ... but aggsplit should still be as the parser left it */ /* Mark the Aggref with the intended partial-aggregation mode */ /* * Adjust result type if needed . Normally , a partial aggregate returns * the aggregate ' s transition type ; but if that ' s INTERNAL and we ' re * serializing , it returns BYTEA instead . if (DO_AGGSPLIT_SKIPFINAL(aggsplit))if (agg->aggtranstype == INTERNALOID && DO_AGGSPLIT_SERIALIZE(aggsplit))else /* * 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 */* ignore resjunk columns in setop result */ if (new_tle->resjunk)continue ;if (orig_tle->resjunk) /* should not happen */ "resjunk output columns are not implemented" );if (orig_tlist_item != NULL)"resjunk output columns are not implemented" );return new_tlist;/* * optimize_window_clauses * Call each WindowFunc ' s prosupport function to see if we ' re able to * make any adjustments to any of the WindowClause ' s so that the executor * can execute the window functions in a more optimal way . * * Currently we only allow adjustments to the WindowClause ' s frameOptions . We * may allow more things to be done here in the future . static void int optimizedFrameOptions = 0 ;/* skip any WindowClauses that have no WindowFuncs */ if (wflists->windowFuncs[wc->winref] == NIL)continue ;/* Check if there's a support function for 'wfunc' */ if (!OidIsValid(prosupport))break ; /* can't optimize this WindowClause */ /* call the support function */ /* * Skip to next WindowClause if the support function does not * support this request type . if (res == NULL)break ;/* * Save these frameOptions for the first WindowFunc for this * WindowClause . if (foreach_current_index(lc2) == 0 )/* * On subsequent WindowFuncs , if the frameOptions are not the same * then we ' re unable to optimize the frameOptions for this * WindowClause . else if (optimizedFrameOptions != res->frameOptions)break ; /* skip to the next WindowClause, if any */ /* adjust the frameOptions if all WindowFunc's agree that it's ok */ if (lc2 == NULL && wc->frameOptions != optimizedFrameOptions)/* apply the new frame options */ /* * We now check to see if changing the frameOptions has caused * this WindowClause to be a duplicate of some other WindowClause . * This can only happen if we have multiple WindowClauses , so * don ' t bother if there ' s only 1 . if (list_length(windowClause) == 1 )continue ;/* * Do the duplicate check and reuse the existing WindowClause if * we find a duplicate . /* skip over the WindowClause we're currently editing */ if (existing_wc == wc)continue ;/* * Perform the same duplicate check that is done in * transformWindowFuncCall . if (equal(wc->partitionClause, existing_wc->partitionClause) &&/* * Now move each WindowFunc in ' wc ' into ' existing_wc ' . * This required adjusting each WindowFunc ' s winref and * moving the WindowFuncs in ' wc ' to the list of * WindowFuncs in ' existing_wc ' . /* move list items */ _wc->winref],/* * transformWindowFuncCall ( ) should have made sure there * are no other duplicates , so we needn ' t bother looking * any further . break ;/* * XXX remove any duplicate WindowFuncs from each WindowClause . This has * been done only in the back branches . Previously , the deduplication was * done in find_window_functions ( ) , but that caused issues with the code * above when moving a WindowFunc to another WindowClause as any duplicate * WindowFuncs won ' t receive the adjusted winref when merging * WindowClauses . The deduplication below has been done only so that we * maintain the same cost calculations . As it turns out , the previous * deduplication code thought it was saving effort during execution by * getting rid of duplicates , but that was not true as the expression * evaluation code will evaluate each WindowFunc mentioned in the * targetlist . if (list == NIL)continue ;if (!list_member(newlist, lfirst(lc2)))else /* * 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 *int nActive = 0 ;sizeof (WindowClauseSortData)/* First, construct an array of the active windows */ /* It's only active if wflists shows some related WindowFuncs */ if (wflists->windowFuncs[wc->winref] == NIL)continue ;/* original clause */ /* * For sorting , we want the list of partition keys followed by the * list of sort keys . But pathkeys construction will remove duplicates * between the two , so we can as well ( even though we can ' t detect all * of the duplicates , since some may come from ECs - that might mean * we miss optimization chances here ) . We must , however , ensure that * the order of entries is preserved with respect to the ones we do * keep . * * partitionClause and orderClause had their own duplicates removed in * parse analysis , so we ' re only concerned here with removing * orderClause entries that also appear in partitionClause . /* * Sort active windows by their partitioning / ordering clauses , ignoring * any framing clauses , so that the windows that need the same sorting are * adjacent in the list . When we come to generate paths , this will avoid * inserting additional Sort nodes . * * This is how we implement a specific requirement from the SQL standard , * which says that when two or more windows are order - equivalent ( i . e . * have matching partition and order clauses , even if their names or * framing clauses differ ) , then all peer rows must be presented in the * same order in all of them . If we allowed multiple sort nodes for such * cases , we ' d risk having the peer rows end up in different orders in * equivalent windows due to sort instability . ( See General Rule 4 of * < window clause > in SQL2008 - SQL2016 . ) * * Additionally , if the entire list of clauses of one window is a prefix * of another , put first the window with stronger sorting requirements . * This way we will first sort for stronger window , and won ' t have to sort * again for the weaker one . sizeof (WindowClauseSortData), common_prefix_cmp);/* build ordered list of the original WindowClause nodes */ for (int i = 0 ; i < nActive; i++)return result;/* * name_active_windows * Ensure all active windows have unique names . * * The parser will have checked that user - assigned window names are unique * within the Query . Here we assign made - up names to any unnamed * WindowClauses for the benefit of EXPLAIN . ( We don ' t want to do this * at parse time , because it ' d mess up decompilation of views . ) * * activeWindows : result of select_active_windows static void int next_n = 1 ;char newname[16 ];/* Nothing to do if it has a name already. */ if (wc->name)continue ;/* Select a name not currently present in the list. */ for (;;)sizeof (newname), "w%d" , next_n++);if (wc2->name && strcmp(wc2->name, newname) == 0 )break ; /* matched */ if (lc2 == NULL)break ; /* reached the end with no match */ /* * common_prefix_cmp * QSort comparison function for WindowClauseSortData * * Sort the windows by the required sorting clauses . First , compare the sort * clauses themselves . Second , if one window ' s clauses are a prefix of another * one ' s clauses , put the window with more sort clauses first . * * We purposefully sort by the highest tleSortGroupRef first . Since * tleSortGroupRefs are assigned for the query ' s DISTINCT and ORDER BY first * and because here we sort the lowest tleSortGroupRefs last , if a * WindowClause is sharing a tleSortGroupRef with the query ' s DISTINCT or * ORDER BY clause , this makes it more likely that the final WindowAgg will * provide presorted input for the query ' s DISTINCT or ORDER BY clause , thus * reducing the total number of sorts required for the query . static int const void *a, const void *b)const WindowClauseSortData *wcsa = a;const WindowClauseSortData *wcsb = b;if (sca->tleSortGroupRef > scb->tleSortGroupRef)return -1 ;else if (sca->tleSortGroupRef < scb->tleSortGroupRef)return 1 ;else if (sca->sortop > scb->sortop)return -1 ;else if (sca->sortop < scb->sortop)return 1 ;else if (sca->nulls_first && !scb->nulls_first)return -1 ;else if (!sca->nulls_first && scb->nulls_first)return 1 ;/* no need to compare eqop, since it is fully determined by sortop */ if (list_length(wcsa->uniqueOrder) > list_length(wcsb->uniqueOrder))return -1 ;else if (list_length(wcsa->uniqueOrder) < list_length(wcsb->uniqueOrder))return 1 ;return 0 ;/* * make_window_input_target * Generate appropriate PathTarget for initial input to WindowAgg nodes . * * When the query has window functions , this function computes the desired * target to be computed by the node just below the first WindowAgg . * This tlist 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 base tlist ; only the topmost WindowAgg computes * the actual desired target list . * * This function is much like make_group_input_target , 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_group_input_target , because we may no longer have access to the * individual Vars in them . * * Another key difference from make_group_input_target 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 . * * ' final_target ' is the query ' s final target list ( in PathTarget form ) * ' activeWindows ' is the list of active windows previously identified by * select_active_windows . * * The result is the PathTarget to be computed by the plan node immediately * below the first WindowAgg node . static PathTarget *int i;/* * Collect the sortgroupref numbers of window PARTITION / ORDER BY clauses * into a bitmapset for convenient reference below . /* Add in sortgroupref numbers of GROUP BY clauses, too */ /* * Construct a target containing all the non - flattenable targetlist items , * and save aside the others for a moment . 0 ;/* * 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 (sgref != 0 && bms_is_member(sgref, sgrefs))/* * Don ' t want to deconstruct this value , so add it to the input * target as - is . else /* * Column is to be flattened , so just remember the expression for * later call to pull_var_clause . /* * Pull out all the Vars and Aggrefs mentioned in flattenable columns , and * add them to the input target 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 any * Aggrefs are placed in the Agg node ' s tlist and not left to be computed * at higher levels . On the other hand , we should recurse into * WindowFuncs to make sure their input expressions are available . /* clean up cruft */ /* XXX this causes some redundant cost calculation ... */ return set_pathtarget_cost_width(root, input_target);/* * make_pathkeys_for_window * Create a pathkeys list describing the required input ordering * for the given WindowClause . * * Modifies wc ' s partitionClause to remove any clauses which are deemed * redundant by the pathkey logic . * * 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 */* Throw error if can't sort */ if (!grouping_is_sortable(wc->partitionClause))"could not implement window PARTITION BY" ),"Window partitioning columns must be of sortable datatypes." )));if (!grouping_is_sortable(wc->orderClause))"could not implement window ORDER BY" ),"Window ordering columns must be of sortable datatypes." )));/* * First fetch the pathkeys for the PARTITION BY clause . We can safely * remove any clauses from the wc - > partitionClause for redundant pathkeys . if (wc->partitionClause != NIL)bool sortable;true ,false ,false );/* * In principle , we could also consider removing redundant ORDER BY items * too as doing so does not alter the result of peer row checks done by * the executor . However , we must * not * remove the ordering column for * RANGE OFFSET cases , as the executor needs that for in_range tests even * if it ' s known to be equal to some partitioning column . if (wc->orderClause != NIL)/* Okay, make the combined pathkeys */ if (window_pathkeys != NIL)else return window_pathkeys;/* * make_sort_input_target * Generate appropriate PathTarget for initial input to Sort step . * * If the query has ORDER BY , this function chooses the target to be computed * by the node just below the Sort ( and DISTINCT , if any , since Unique can ' t * project ) steps . This might or might not be identical to the query ' s final * output target . * * The main argument for keeping the sort - input tlist the same as the final * is that we avoid a separate projection node ( which will be needed if * they ' re different , because Sort can ' t project ) . However , there are also * advantages to postponing tlist evaluation till after the Sort : it ensures * a consistent order of evaluation for any volatile functions in the tlist , * and if there ' s also a LIMIT , we can stop the query without ever computing * tlist functions for later rows , which is beneficial for both volatile and * expensive functions . * * Our current policy is to postpone volatile expressions till after the sort * unconditionally ( assuming that that ' s possible , ie they are in plain tlist * columns and not ORDER BY / GROUP BY / DISTINCT columns ) . We also prefer to * postpone set - returning expressions , because running them beforehand would * bloat the sort dataset , and because it might cause unexpected output order * if the sort isn ' t stable . However there ' s a constraint on that : all SRFs * in the tlist should be evaluated at the same plan step , so that they can * run in sync in nodeProjectSet . So if any SRFs are in sort columns , we * mustn ' t postpone any SRFs . ( Note that in principle that policy should * probably get applied to the group / window input targetlists too , but we * have not done that historically . ) Lastly , expensive expressions are * postponed if there is a LIMIT , or if root - > tuple_fraction shows that * partial evaluation of the query is possible ( if neither is true , we expect * to have to evaluate the expressions for every row anyway ) , or if there are * any volatile or set - returning expressions ( since once we ' ve put in a * projection at all , it won ' t cost any more to postpone more stuff ) . * * Another issue that could potentially be considered here is that * evaluating tlist expressions could result in data that ' s either wider * or narrower than the input Vars , thus changing the volume of data that * has to go through the Sort . However , we usually have only a very bad * idea of the output width of any expression more complex than a Var , * so for now it seems too risky to try to optimize on that basis . * * Note that if we do produce a modified sort - input target , and then the * query ends up not using an explicit Sort , no particular harm is done : * we ' ll initially use the modified target for the preceding path nodes , * but then change them to the final target with apply_projection_to_path . * Moreover , in such a case the guarantees about evaluation order of * volatile functions still hold , since the rows are sorted already . * * This function has some things in common with make_group_input_target and * make_window_input_target , though the detailed rules for what to do are * different . We never flatten / postpone any grouping or ordering columns ; * those are needed before the sort . If we do flatten a particular * expression , we leave Aggref and WindowFunc nodes alone , since those were * computed earlier . * * ' final_target ' is the query ' s final target list ( in PathTarget form ) * ' have_postponed_srfs ' is an output argument , see below * * The result is the PathTarget to be computed by the plan node immediately * below the Sort step ( and the Distinct step , if any ) . This will be * exactly final_target if we decide a projection step wouldn ' t be helpful . * * In addition , * have_postponed_srfs is set to true if we choose to postpone * any set - returning functions to after the Sort . static PathTarget *bool *have_postponed_srfs)int ncols;bool *col_is_srf;bool *postpone_col;bool have_srf;bool have_volatile;bool have_expensive;bool have_srf_sortcols;bool postpone_srfs;int i;/* Shouldn't get here unless query has ORDER BY */ false ; /* default result */ /* Inspect tlist and collect per-column information */ bool *) palloc0(ncols * sizeof (bool ));bool *) palloc0(ncols * sizeof (bool ));false ;0 ;/* * If the column has a sortgroupref , assume it has to be evaluated * before sorting . Generally such columns would be ORDER BY , GROUP * BY , etc targets . One exception is columns that were removed from * GROUP BY by remove_useless_groupby_columns ( ) . . . but those would * only be Vars anyway . There don ' t seem to be any cases where it * would be worth the trouble to double - check . if (get_pathtarget_sortgroupref(final_target, i) == 0 )/* * Check for SRF or volatile functions . Check the SRF case first * because we must know whether we have any postponed SRFs . if (parse->hasTargetSRFs &&/* We'll decide below whether these are postponable */ true ;true ;else if (contain_volatile_functions((Node *) expr))/* Unconditionally postpone */ true ;true ;else /* * Else check the cost . XXX it ' s annoying to have to do this * when set_pathtarget_cost_width ( ) just did it . Refactor to * allow sharing the work ? /* * We arbitrarily define " expensive " as " more than 10 X * cpu_operator_cost " . Note this will take in any PL function * with default cost . if (cost.per_tuple > 10 * cpu_operator_cost)true ;true ;else /* For sortgroupref cols, just check if any contain SRFs */ if (!have_srf_sortcols &&true ;/* * We can postpone SRFs if we have some but none are in sortgroupref cols . /* * If we don ' t need a post - sort projection , just return final_target . if (!(postpone_srfs || have_volatile ||0 ))))return final_target;/* * Report whether the post - sort projection will contain set - returning * functions . This is important because it affects whether the Sort can * rely on the query ' s LIMIT ( if any ) to bound the number of rows it needs * to return . /* * Construct the sort - input target , taking all non - postponable columns and * then adding Vars , PlaceHolderVars , Aggrefs , and WindowFuncs found in * the postponable ones . 0 ;if (postpone_col[i] || (postpone_srfs && col_is_srf[i]))else /* * Pull out all the Vars , Aggrefs , and WindowFuncs mentioned in * postponable columns , and add them to the sort - input target if not * already present . ( Some might be there already . ) We mustn ' t * deconstruct Aggrefs or WindowFuncs here , since the projection node * would be unable to recompute them . /* clean up cruft */ /* XXX this represents even more redundant cost calculation ... */ return set_pathtarget_cost_width(root, input_target);/* * get_cheapest_fractional_path * Find the cheapest path for retrieving a specified fraction of all * the tuples expected to be returned by the given relation . * * Do not consider parameterized paths . If the caller needs a path for upper * rel , it can ' t have parameterized paths . If the caller needs an append * subpath , it could become limited by the treatment of similar * parameterization of all the subpaths . * * We interpret tuple_fraction the same way as grouping_planner . * * We assume set_cheapest ( ) has been run on the given rel . double tuple_fraction)/* If all tuples will be retrieved, just return the cheapest-total path */ if (tuple_fraction <= 0 .0 )return best_path;/* Convert absolute # of tuples to a fraction; no need to clamp to 0..1 */ if (tuple_fraction >= 1 .0 && best_path->rows > 0 )if (path->param_info)continue ;if (path == rel->cheapest_total_path ||0 )continue ;return best_path;/* * adjust_paths_for_srfs * Fix up the Paths of the given upperrel to handle tSRFs properly . * * The executor can only handle set - returning functions that appear at the * top level of the targetlist of a ProjectSet plan node . If we have any SRFs * that are not at top level , we need to split up the evaluation into multiple * plan levels in which each level satisfies this constraint . This function * modifies each Path of an upperrel that ( might ) compute any SRFs in its * output tlist to insert appropriate projection steps . * * The given targets and targets_contain_srfs lists are from * split_pathtarget_at_srfs ( ) . We assume the existing Paths emit the first * target in targets . static void /* If no SRFs appear at this plan level, nothing to do */ if (list_length(targets) == 1 )return ;/* * Stack SRF - evaluation nodes atop each path for the rel . * * In principle we should re - run set_cheapest ( ) here to identify the * cheapest path , but it seems unlikely that adding the same tlist eval * costs to all the paths would change that , so we don ' t bother . Instead , * just assume that the cheapest - startup and cheapest - total paths remain * so . ( There should be no parameterized paths anymore , so we needn ' t * worry about updating cheapest_parameterized_paths . ) bool contains_srfs = (bool ) lfirst_int(lc2);/* If this level doesn't contain SRFs, do regular projection */ if (contains_srfs)else if (subpath == rel->cheapest_startup_path)if (subpath == rel->cheapest_total_path)/* Likewise for partial paths, if any */ bool contains_srfs = (bool ) lfirst_int(lc2);/* If this level doesn't contain SRFs, do regular projection */ if (contains_srfs)else /* avoid apply_projection_to_path, in case of multiple refs */ /* * 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 . * * This does not return any information about dependencies of the expression . * Hence callers should use the results only for the duration of the current * query . Callers that would like to cache the results for longer should use * expression_planner_with_deps , probably via the plancache . * * 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 . ) The result is constructed in the current memory * context ; beware that this can leak a lot of additional stuff there , too . /* * Convert named - argument function calls , insert default arguments and * simplify constant subexprs /* Fill in opfuncid values if missing */ return (Expr *) result;/* * expression_planner_with_deps * Perform planner ' s transformations on a standalone expression , * returning expression dependency information along with the result . * * This is identical to expression_planner ( ) except that it also returns * information about possible dependencies of the expression , ie identities of * objects whose definitions affect the result . As in a PlannedStmt , these * are expressed as a list of relation Oids and a list of PlanInvalItems . /* Make up dummy planner state so we can use setrefs machinery */ 0 , sizeof (glob));0 , sizeof (root));/* * Convert named - argument function calls , insert default arguments and * simplify constant subexprs . Collect identities of inlined functions * and elided domains , too . /* Fill in opfuncid values if missing */ /* * Now walk the finished expression to find anything else we ought to * record as an expression dependency . void ) extract_query_dependencies_walker(result, &root);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 /* We can short-circuit the cost comparison if indexscans are disabled */ if (!enable_indexscan)return true ; /* use sort */ /* Set up mostly-dummy planner state */ 1 ;1 ;/* Build a minimal RTE for the rel */ /* Don't be too picky. */ false ;false ;true ;/* Set up RTE/RelOptInfo arrays */ /* Build RelOptInfo */ 1 , NULL);/* Locate IndexOptInfo for the target index */ 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 . /* * 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 . . . ) 2 .0 * (indexExprCost.startup + indexExprCost.per_tuple);/* Estimate the cost of seq scan + sort */ 0 );1 .0 );/* Estimate the cost of index scan */ false ,1 .0 , false );return (seqScanAndSortPath.total_cost < indexScanPath->path.total_cost);/* * plan_create_index_workers * Use the planner to decide how many parallel worker processes * CREATE INDEX should request for use * * tableOid is the table on which the index is to be built . indexOid is the * OID of an index to be created or reindexed ( which must be an index with * support for parallel builds - currently btree , GIN , or BRIN ) . * * Return value is the number of parallel worker processes to request . It * may be unsafe to proceed if this is 0 . Note that this does not include the * leader participating as a worker ( value is always a number of parallel * worker processes ) . * * Note : caller had better already hold some type of lock on the table and * index . int int parallel_workers;double reltuples;double allvisfrac;/* * We don ' t allow performing parallel operation in standalone backend or * when parallelism is disabled . if (!IsUnderPostmaster || max_parallel_maintenance_workers == 0 )return 0 ;/* Set up largely-dummy planner state */ 1 ;1 ;/* * Build a minimal RTE . * * Mark the RTE with inh = true . This is a kludge to prevent * get_relation_info ( ) from fetching index info , which is necessary * because it does not expect that any IndexOptInfo is currently * undergoing REINDEX . /* Don't be too picky. */ false ;true ;true ;/* Set up RTE/RelOptInfo arrays */ /* Build RelOptInfo */ 1 , NULL);/* Rels are assumed already locked by the caller */ /* * Determine if it ' s safe to proceed . * * Currently , parallel workers can ' t access the leader ' s temporary tables . * Furthermore , any index predicate or index expressions must be parallel * safe . if (heap->rd_rel->relpersistence == RELPERSISTENCE_TEMP ||0 ;goto done;/* * If parallel_workers storage parameter is set for the table , accept that * as the number of parallel worker processes to launch ( though still cap * at max_parallel_maintenance_workers ) . Note that we deliberately do not * consider any other factor when parallel_workers is set . ( e . g . , memory * use by workers . ) if (rel->rel_parallel_workers != -1 )goto done;/* * Estimate heap relation size ourselves , since rel - > pages cannot be * trusted ( heap RTE was marked as inheritance parent ) /* * Determine number of workers to scan the heap relation using generic * model 1 ,/* * Cap workers based on available maintenance_work_mem as needed . * * Note that each tuplesort participant receives an even share of the * total maintenance_work_mem budget . Aim to leave participants * ( including the leader as a participant ) with no less than 32 MB of * memory . This leaves cases where maintenance_work_mem is set to 64 MB * immediately past the threshold of being capable of launching a single * parallel worker to sort . while (parallel_workers > 0 &&1 ) < 32 * 1024 )return parallel_workers;/* * add_paths_to_grouping_rel * * Add non - partial paths to grouping relation . static void const AggClauseCosts *agg_costs,double dNumGroups,bool can_hash = (extra->flags & GROUPING_CAN_USE_HASH) != 0 ;bool can_sort = (extra->flags & GROUPING_CAN_USE_SORT) != 0 ;if (can_sort)/* * Use any available suitably - sorted path as input , and also consider * sorting the cheapest - total path and incremental sort on any paths * with presorted keys . /* generate alternative group orderings that might be useful */ 0 );/* restore the path (we replace it in the loop) */ 1 .0 );if (path == NULL)continue ;/* Now decide what to stick atop it */ if (parse->groupingSets)true , can_hash,else if (parse->hasAggs)/* * We have aggregation , possibly with plain GROUP BY . Make * an AggPath . else if (parse->groupClause)/* * We have GROUP BY without aggregation or grouping sets . * Make a GroupPath . else /* Other cases should have been handled above */ false );/* * Instead of operating directly on the input relation , we can * consider finalizing a partially aggregated path . if (partially_grouped_rel != NULL)/* generate alternative group orderings that might be useful */ 0 );/* process all potentially interesting grouping reorderings */ /* restore the path (we replace it in the loop) */ 1 .0 );if (path == NULL)continue ;if (parse->hasAggs)else if (can_hash)if (parse->groupingSets)/* * Try for a hash - only groupingsets path over unsorted input . false , true ,else /* * Generate a HashAgg Path . We just need an Agg over the * cheapest - total input path , since input order won ' t matter . /* * Generate a Finalize HashAgg Path atop of the cheapest partially * grouped path , assuming there is one if (partially_grouped_rel && partially_grouped_rel->pathlist)/* * When partitionwise aggregate is used , we might have fully aggregated * paths in the partial pathlist , because add_paths_to_append_rel ( ) will * consider a path for grouped_rel consisting of a Parallel Append of * non - partial paths from each child . if (grouped_rel->partial_pathlist != NIL)/* * create_partial_grouping_paths * * Create a new upper relation representing the result of partial aggregation * and populate it with appropriate paths . Note that we don ' t finalize the * lists of paths here , so the caller can add additional partial or non - partial * paths and must afterward call gather_grouping_paths and set_cheapest on * the returned upper relation . * * All paths for this new upper relation - - both partial and non - partial - - * have been partially aggregated but require a subsequent FinalizeAggregate * step . * * NB : This function is allowed to return NULL if it determines that there is * no real need to create a new RelOptInfo . static RelOptInfo *bool force_rel_creation)double dNumPartialGroups = 0 ;double dNumPartialPartialGroups = 0 ;bool can_hash = (extra->flags & GROUPING_CAN_USE_HASH) != 0 ;bool can_sort = (extra->flags & GROUPING_CAN_USE_SORT) != 0 ;/* * Consider whether we should generate partially aggregated non - partial * paths . We can only do this if we have a non - partial path , and only if * the parent of the input rel is performing partial partitionwise * aggregation . ( Note that extra - > patype is the type of partitionwise * aggregation being used at the parent level , not this level . ) if (input_rel->pathlist != NIL &&/* * If parallelism is possible for grouped_rel , then we should consider * generating partially - grouped partial paths . However , if the input rel * has no partial paths , then we can ' t . if (grouped_rel->consider_parallel && input_rel->partial_pathlist != NIL)/* * If we can ' t partially aggregate partial paths , and we can ' t partially * aggregate non - partial paths , then don ' t bother creating the new * RelOptInfo at all , unless the caller specified force_rel_creation . if (cheapest_total_path == NULL &&return NULL;/* * Build a new upper relation to represent the result of partially * aggregating the rows from the input relation . /* * Build target list for partial aggregate paths . These paths cannot just * emit the same tlist as regular aggregate paths , because ( 1 ) we must * include Vars and Aggrefs needed in HAVING , which might not appear in * the result tlist , and ( 2 ) the Aggrefs must be set in partial mode . if (!extra->partial_costs_set)/* * Collect statistics about aggregates for estimating costs of * performing aggregation in parallel . 0 , sizeof (AggClauseCosts));0 , sizeof (AggClauseCosts));if (parse->hasAggs)/* partial phase */ /* final phase */ true ;/* Estimate number of partial groups. */ if (cheapest_total_path != NULL)if (cheapest_partial_path != NULL)if (can_sort && cheapest_total_path != NULL)/* This should have been checked previously */ /* * Use any available suitably - sorted path as input , and also consider * sorting the cheapest partial path . /* generate alternative group orderings that might be useful */ 0 );/* process all potentially interesting grouping reorderings */ /* restore the path (we replace it in the loop) */ 1 .0 );if (path == NULL)continue ;if (parse->hasAggs)else if (can_sort && cheapest_partial_path != NULL)/* Similar to above logic, but for partial paths. */ /* generate alternative group orderings that might be useful */ 0 );/* process all potentially interesting grouping reorderings */ /* restore the path (we replace it in the loop) */ 1 .0 );if (path == NULL)continue ;if (parse->hasAggs)else /* * Add a partially - grouped HashAgg Path where possible if (can_hash && cheapest_total_path != NULL)/* Checked above */ /* * Now add a partially - grouped HashAgg partial Path where possible if (can_hash && cheapest_partial_path != NULL)/* * If there is an FDW that ' s responsible for all baserels of the query , * let it consider adding partially grouped ForeignPaths . if (partially_grouped_rel->fdwroutine &&return partially_grouped_rel;/* * make_ordered_path * Return a path ordered by ' pathkeys ' based on the given ' path ' . May * return NULL if it doesn ' t make sense to generate an ordered path in * this case . static Path *double limit_tuples)bool is_sorted;int presorted_keys;if (!is_sorted)/* * Try at least sorting the cheapest path and also try incrementally * sorting any path which is partially sorted already ( no need to deal * with paths which have presorted keys when incremental sort is * disabled unless it ' s the cheapest input path ) . if (path != cheapest_path &&0 || !enable_incremental_sort))return NULL;/* * We ' ve no need to consider both a sort and incremental sort . We ' ll * just do a sort if there are no presorted keys and an incremental * sort when there are presorted keys . if (presorted_keys == 0 || !enable_incremental_sort)else return path;/* * Generate Gather and Gather Merge paths for a grouping relation or partial * grouping relation . * * generate_useful_gather_paths does most of the work , but we also consider a * special case : we could try sorting the data by the group_pathkeys and then * applying Gather Merge . * * NB : This function shouldn ' t be used for anything other than a grouped or * partially grouped relation not only because of the fact that it explicitly * references group_pathkeys but we pass " true " as the third argument to * generate_useful_gather_paths ( ) . static void /* * This occurs after any partial aggregation has taken place , so trim off * any pathkeys added for ORDER BY / DISTINCT aggregates . if (list_length(root->group_pathkeys) > root->num_groupby_pathkeys)else /* Try Gather for unordered paths and Gather Merge for ordered ones. */ true );/* XXX Shouldn't this also consider the group-key-reordering? */ bool is_sorted;int presorted_keys;double total_groups;if (is_sorted)continue ;/* * Try at least sorting the cheapest path and also try incrementally * sorting any path which is partially sorted already ( no need to deal * with paths which have presorted keys when incremental sort is * disabled unless it ' s the cheapest input path ) . if (path != cheapest_partial_path &&0 || !enable_incremental_sort))continue ;/* * We ' ve no need to consider both a sort and incremental sort . We ' ll * just do a sort if there are no presorted keys and an incremental * sort when there are presorted keys . if (presorted_keys == 0 || !enable_incremental_sort)1 .0 );else 1 .0 );/* * can_partial_agg * * Determines whether or not partial grouping and / or aggregation is possible . * Returns true when possible , false otherwise . static bool if (!parse->hasAggs && parse->groupClause == NIL)/* * We don ' t know how to do parallel aggregation unless we have either * some aggregates or a grouping clause . return false ;else if (parse->groupingSets)/* We don't know how to do grouping sets in parallel. */ return false ;else if (root->hasNonPartialAggs || root->hasNonSerialAggs)/* Insufficient support for partial mode. */ return false ;/* Everything looks good. */ return true ;/* * apply_scanjoin_target_to_paths * * Adjust the final scan / join relation , and recursively all of its children , * to generate the final scan / join target . It would be more correct to model * this as a separate planning step with a new RelOptInfo at the toplevel and * for each child relation , but doing it this way is noticeably cheaper . * Maybe that problem can be solved at some point , but for now we do this . * * If tlist_same_exprs is true , then the scan / join target to be applied has * the same expressions as the existing reltarget , so we need only insert the * appropriate sortgroupref information . By avoiding the creation of * projection paths we save effort both immediately and at plan creation time . static void bool scanjoin_target_parallel_safe,bool tlist_same_exprs)bool rel_is_partitioned = IS_PARTITIONED_REL(rel);/* This recurses, so be paranoid. */ /* * If the rel is partitioned , we want to drop its existing paths and * generate new ones . This function would still be correct if we kept the * existing paths : we ' d modify them to generate the correct target above * the partitioning Append , and then they ' d compete on cost with paths * generating the target below the Append . However , in our current cost * model the latter way is always the same or cheaper cost , so modifying * the existing paths would just be useless work . Moreover , when the cost * is the same , varying roundoff errors might sometimes allow an existing * path to be picked , resulting in undesirable cross - platform plan * variations . So we drop old paths and thereby force the work to be done * below the Append , except in the case of a non - parallel - safe target . * * Some care is needed , because we have to allow * generate_useful_gather_paths to see the old partial paths in the next * stanza . Hence , zap the main pathlist here , then allow * generate_useful_gather_paths to add path ( s ) to the main list , and * finally zap the partial pathlist . if (rel_is_partitioned)/* * If the scan / join target is not parallel - safe , partial paths cannot * generate it . if (!scanjoin_target_parallel_safe)/* * Since we can ' t generate the final scan / join target in parallel * workers , this is our last opportunity to use any partial paths that * exist ; so build Gather path ( s ) that use them and emit whatever the * current reltarget is . We don ' t do this in the case where the * target is parallel - safe , since we will be able to generate superior * paths by doing it after the final scan / join target has been * applied . false );/* Can't use parallel query above this level. */ false ;/* Finish dropping old paths for a partitioned rel, per comment above */ if (rel_is_partitioned)/* Extract SRF-free scan/join target. */ /* * Apply the SRF - free scan / join target to each existing path . * * If the tlist exprs are the same , we can just inject the sortgroupref * information into the existing pathtargets . Otherwise , replace each * path with a projection path that generates the SRF - free scan / join * target . This can ' t change the ordering of paths within rel - > pathlist , * so we just modify the list in place . /* Shouldn't have any parameterized paths anymore */ if (tlist_same_exprs)else /* Likewise adjust the targets for any partial paths. */ /* Shouldn't have any parameterized paths anymore */ if (tlist_same_exprs)else /* * Now , if final scan / join target contains SRFs , insert ProjectSetPath ( s ) * atop each existing path . ( Note that this function doesn ' t look at the * cheapest - path fields , which is a good thing because they ' re bogus right * now . ) if (root->parse->hasTargetSRFs)/* * Update the rel ' s target to be the final ( with SRFs ) scan / join target . * This now matches the actual output of all the paths , and we might get * confused in createplan . c if they don ' t agree . We must do this now so * that any append paths made in the next part will use the correct * pathtarget ( cf . create_append_path ) . * * Note that this is also necessary if GetForeignUpperPaths ( ) gets called * on the final scan / join relation or on any of its children , since the * FDW might look at the rel ' s target to create ForeignPaths . /* * If the relation is partitioned , recursively apply the scan / join target * to all partitions , and generate brand - new Append paths in which the * scan / join target is computed below the Append rather than above it . * Since Append is not projection - capable , that might save a separate * Result node , and it also is important for partitionwise aggregate . if (rel_is_partitioned)int i;/* Adjust each partition. */ 1 ;while ((i = bms_next_member(rel->live_parts, i)) >= 0 )int nappinfos;/* Dummy children can be ignored. */ if (IS_DUMMY_REL(child_rel))continue ;/* Translate scan/join targets for this child. */ /* Recursion does the real work. */ /* Save non-dummy children for Append paths. */ if (!IS_DUMMY_REL(child_rel))/* Build new paths for this relation by appending child paths. */ /* * Consider generating Gather or Gather Merge paths . We must only do this * if the relation is parallel safe , and we don ' t do it for child rels to * avoid creating multiple Gather nodes within the same plan . We must do * this after all paths have been generated and before set_cheapest , since * one of the generated paths may turn out to be the cheapest one . if (rel->consider_parallel && !IS_OTHER_REL(rel))false );/* * Reassess which paths are the cheapest , now that we ' ve potentially added * new Gather ( or Gather Merge ) and / or Append ( or MergeAppend ) paths to * this relation . /* * create_partitionwise_grouping_paths * * If the partition keys of input relation are part of the GROUP BY clause , all * the rows belonging to a given group come from a single partition . This * allows aggregation / grouping over a partitioned relation to be broken down * into aggregation / grouping on each partition . This should be no worse , and * often better , than the normal approach . * * However , if the GROUP BY clause does not contain all the partition keys , * rows from a given group may be spread across multiple partitions . In that * case , we perform partial aggregation for each group , append the results , * and then finalize aggregation . This is less certain to win than the * previous case . It may win if the PartialAggregate stage greatly reduces * the number of groups , because fewer rows will pass through the Append node . * It may lose if we have lots of small groups . static void const AggClauseCosts *agg_costs,bool partial_grouping_valid = true ;int i;/* Add paths for partitionwise aggregation/grouping. */ 1 ;while ((i = bms_next_member(input_rel->live_parts, i)) >= 0 )int nappinfos;/* Dummy children can be ignored. */ if (IS_DUMMY_REL(child_input_rel))continue ;/* * Copy the given " extra " structure as is and then override the * members specific to this child . sizeof (child_extra));/* Translate havingQual and targetList. */ /* * extra - > patype was the value computed for our parent rel ; patype is * the value for this relation . For the child , our value is its * parent rel ' s value . /* * Create grouping relation to hold fully aggregated grouping and / or * aggregation paths for the child . /* Create grouping paths for this child relation. */ if (child_partially_grouped_rel)else false ;if (patype == PARTITIONWISE_AGGREGATE_FULL)/* * Try to create append paths for partially grouped children . For full * partitionwise aggregation , we might have paths in the partial_pathlist * if parallel aggregation is possible . For partial partitionwise * aggregation , we may have paths in both pathlist and partial_pathlist . * * NB : We must have a partially grouped path for every child in order to * generate a partially grouped path for this relation . if (partially_grouped_rel && partial_grouping_valid)/* * We need call set_cheapest , since the finalization step will use the * cheapest path from the rel . if (partially_grouped_rel->pathlist)/* If possible, create append paths for fully grouped children. */ if (patype == PARTITIONWISE_AGGREGATE_FULL)/* * group_by_has_partkey * * Returns true if all the partition keys of the given relation are part of * the GROUP BY clauses , including having matching collation , false otherwise . static bool int cnt = 0 ;int partnatts;/* Input relation should be partitioned. */ /* Rule out early, if there are no partition keys present. */ if (!input_rel->partexprs)return false ;for (cnt = 0 ; cnt < partnatts; cnt++)bool found = false ;/* * Note : we can assume there is at most one RelabelType node ; * eval_const_expressions ( ) will have simplified if more than * one . if (IsA(groupexpr, RelabelType))if (equal(groupexpr, partexpr))/* * Reject a match if the grouping collation does not match * the partitioning collation . if (OidIsValid(partcoll) && OidIsValid(groupcoll) &&return false ;true ;break ;if (found)break ;/* * If none of the partition key expressions match with any of the * GROUP BY expression , return false . if (!found)return false ;return true ;/* * generate_setop_child_grouplist * Build a SortGroupClause list defining the sort / grouping properties * of the child of a set operation . * * This is similar to generate_setop_grouplist ( ) but differs as the setop * child query ' s targetlist entries may already have a tleSortGroupRef * assigned for other purposes , such as GROUP BYs . Here we keep the * SortGroupClause list in the same order as ' op ' groupClauses and just adjust * the tleSortGroupRef to reference the TargetEntry ' s ' ressortgroupref ' . If * any of the columns in the targetlist don ' t match to the setop ' s colTypes * then we return an empty list . This may leave some TLEs with unreferenced * ressortgroupref markings , but that ' s harmless . static List */* resjunk columns could have sortgrouprefs. Leave these alone */ if (tle->resjunk)continue ;/* * We expect every non - resjunk target to have a SortGroupClause and * colTypes . /* reject if target type isn't the same as the setop target type */ if (coltype != exprType((Node *) tle->expr))return NIL;/* assign a tleSortGroupRef, or reuse the existing one */ return grouplist;
Messung V0.5 in Prozent C=93 H=95 G=93
¤ Dauer der Verarbeitung: 1.2 Sekunden
(vorverarbeitet am 2026-08-08)
¤ *© Formatika GbR, Deutschland
