#### 3.3创建单表查询的计划树 Postgresql中的计划器会执行三个处理步骤： 1. 执行预处理 2. 在所有可能的访问路径中，找出代价最小的访问路径 3. 按照代价最小的路径，创建计划树 访问路径是估算代价时的处理单元。比如顺序扫描、索引扫描、排序，以及各种连接操作都有其对应的路径。访问路径只在计划器创建查询计划树的时候使用。最基本的访问路径数据结构就是relation.h定义的Path结构体，相当于顺序扫描。所有其他的访问路径都基于该结构。 计划器为了处理上述步骤，会在内部创建一个PlannerInfo数据结构，该数据结构中包含查询树，可以查询锁涉及的关系信息，访问路径等。 ``` #/pgdata/pgsql/include/postgresql/server/nodes/relation.h /* * PathKeys * * The sort ordering of a path is represented by a list of PathKey nodes. * An empty list implies no known ordering. Otherwise the first item * represents the primary sort key, the second the first secondary sort key, * etc. The value being sorted is represented by linking to an * EquivalenceClass containing that value and including pk_opfamily among its * ec_opfamilies. The EquivalenceClass tells which collation to use, too. * This is a convenient method because it makes it trivial to detect * equivalent and closely-related orderings. (See optimizer/README for more * information.) * * Note: pk_strategy is either BTLessStrategyNumber (for ASC) or * BTGreaterStrategyNumber (for DESC). We assume that all ordering-capable * index types will use btree-compatible strategy numbers. */ typedef struct PathKey { NodeTag type; EquivalenceClass *pk_eclass; /* the value that is ordered */ Oid pk_opfamily; /* btree opfamily defining the ordering */ int pk_strategy; /* sort direction (ASC or DESC) */ bool pk_nulls_first; /* do NULLs come before normal values? */ } PathKey; typedef struct Path { NodeTag type; NodeTag pathtype; /* tag identifying scan/join method */ RelOptInfo *parent; /* the relation this path can build */ PathTarget *pathtarget; /* list of Vars/Exprs, cost, width */ ParamPathInfo *param_info; /* parameterization info, or NULL if none */ bool parallel_aware; /* engage parallel-aware logic? */ bool parallel_safe; /* OK to use as part of parallel plan? */ int parallel_workers; /* desired # of workers; 0 = not parallel */ /* estimated size/costs for path (see costsize.c for more info) */ double rows; /* estimated number of result tuples */ Cost startup_cost; /* cost expended before fetching any tuples */ Cost total_cost; /* total cost (assuming all tuples fetched) */ List *pathkeys; /* sort ordering of path's output */ /* pathkeys is a List of PathKey nodes; see above */ } Path; /*---------- * PlannerInfo * Per-query information for planning/optimization * * This struct is conventionally called "root" in all the planner routines. * It holds links to all of the planner's working state, in addition to the * original Query. Note that at present the planner extensively modifies * the passed-in Query data structure; someday that should stop. *---------- */ typedef struct PlannerInfo { NodeTag type; Query *parse; /* the Query being planned */ PlannerGlobal *glob; /* global info for current planner run */ Index query_level; /* 1 at the outermost Query */ struct PlannerInfo *parent_root; /* NULL at outermost Query */ /* * plan_params contains the expressions that this query level needs to * make available to a lower query level that is currently being planned. * outer_params contains the paramIds of PARAM_EXEC Params that outer * query levels will make available to this query level. */ List *plan_params; /* list of PlannerParamItems, see below */ Bitmapset *outer_params; /* * simple_rel_array holds pointers to "base rels" and "other rels" (see * comments for RelOptInfo for more info). It is indexed by rangetable * index (so entry 0 is always wasted). Entries can be NULL when an RTE * does not correspond to a base relation, such as a join RTE or an * unreferenced view RTE; or if the RelOptInfo hasn't been made yet. */ struct RelOptInfo **simple_rel_array; /* All 1-rel RelOptInfos */ int simple_rel_array_size; /* allocated size of array */ /* * simple_rte_array is the same length as simple_rel_array and holds * pointers to the associated rangetable entries. This lets us avoid * rt_fetch(), which can be a bit slow once large inheritance sets have * been expanded. */ RangeTblEntry **simple_rte_array; /* rangetable as an array */ /* * all_baserels is a Relids set of all base relids (but not "other" * relids) in the query; that is, the Relids identifier of the final join * we need to form. This is computed in make_one_rel, just before we * start making Paths. */ Relids all_baserels; /* * nullable_baserels is a Relids set of base relids that are nullable by * some outer join in the jointree; these are rels that are potentially * nullable below the WHERE clause, SELECT targetlist, etc. This is * computed in deconstruct_jointree. */ Relids nullable_baserels; /* * join_rel_list is a list of all join-relation RelOptInfos we have * considered in this planning run. For small problems we just scan the * list to do lookups, but when there are many join relations we build a * hash table for faster lookups. The hash table is present and valid * when join_rel_hash is not NULL. Note that we still maintain the list * even when using the hash table for lookups; this simplifies life for * GEQO. */ List *join_rel_list; /* list of join-relation RelOptInfos */ struct HTAB *join_rel_hash; /* optional hashtable for join relations */ /* * When doing a dynamic-programming-style join search, join_rel_level[k] * is a list of all join-relation RelOptInfos of level k, and * join_cur_level is the current level. New join-relation RelOptInfos are * automatically added to the join_rel_level[join_cur_level] list. * join_rel_level is NULL if not in use. */ List **join_rel_level; /* lists of join-relation RelOptInfos */ int join_cur_level; /* index of list being extended */ List *init_plans; /* init SubPlans for query */ List *cte_plan_ids; /* per-CTE-item list of subplan IDs */ List *multiexpr_params; /* List of Lists of Params for MULTIEXPR * subquery outputs */ List *eq_classes; /* list of active EquivalenceClasses */ List *canon_pathkeys; /* list of "canonical" PathKeys */ List *left_join_clauses; /* list of RestrictInfos for mergejoinable * outer join clauses w/nonnullable var on * left */ List *right_join_clauses; /* list of RestrictInfos for mergejoinable * outer join clauses w/nonnullable var on * right */ List *full_join_clauses; /* list of RestrictInfos for mergejoinable * full join clauses */ List *join_info_list; /* list of SpecialJoinInfos */ List *append_rel_list; /* list of AppendRelInfos */ List *pcinfo_list; /* list of PartitionedChildRelInfos */ List *rowMarks; /* list of PlanRowMarks */ List *placeholder_list; /* list of PlaceHolderInfos */ List *fkey_list; /* list of ForeignKeyOptInfos */ List *query_pathkeys; /* desired pathkeys for query_planner() */ List *group_pathkeys; /* groupClause pathkeys, if any */ List *window_pathkeys; /* pathkeys of bottom window, if any */ List *distinct_pathkeys; /* distinctClause pathkeys, if any */ List *sort_pathkeys; /* sortClause pathkeys, if any */ List *initial_rels; /* RelOptInfos we are now trying to join */ /* Use fetch_upper_rel() to get any particular upper rel */ List *upper_rels[UPPERREL_FINAL + 1]; /* upper-rel RelOptInfos */ /* Result tlists chosen by grouping_planner for upper-stage processing */ struct PathTarget *upper_targets[UPPERREL_FINAL + 1]; /* * grouping_planner passes back its final processed targetlist here, for * use in relabeling the topmost tlist of the finished Plan. */ List *processed_tlist; /* Fields filled during create_plan() for use in setrefs.c */ AttrNumber *grouping_map; /* for GroupingFunc fixup */ List *minmax_aggs; /* List of MinMaxAggInfos */ MemoryContext planner_cxt; /* context holding PlannerInfo */ double total_table_pages; /* # of pages in all tables of query */ double tuple_fraction; /* tuple_fraction passed to query_planner */ double limit_tuples; /* limit_tuples passed to query_planner */ Index qual_security_level; /* minimum security_level for quals */ /* Note: qual_security_level is zero if there are no securityQuals */ bool hasInheritedTarget; /* true if parse->resultRelation is an * inheritance child rel */ bool hasJoinRTEs; /* true if any RTEs are RTE_JOIN kind */ bool hasLateralRTEs; /* true if any RTEs are marked LATERAL */ bool hasDeletedRTEs; /* true if any RTE was deleted from jointree */ bool hasHavingQual; /* true if havingQual was non-null */ bool hasPseudoConstantQuals; /* true if any RestrictInfo has * pseudoconstant = true */ bool hasRecursion; /* true if planning a recursive WITH item */ /* These fields are used only when hasRecursion is true: */ int wt_param_id; /* PARAM_EXEC ID for the work table */ struct Path *non_recursive_path; /* a path for non-recursive term */ /* These fields are workspace for createplan.c */ Relids curOuterRels; /* outer rels above current node */ List *curOuterParams; /* not-yet-assigned NestLoopParams */ /* optional private data for join_search_hook, e.g., GEQO */ void *join_search_private; } PlannerInfo; ``` ##### 预处理 在创建计划树之前，计划器将先对PlannerInfo中的查询树进行一些预处理 1. 计简化目标列表，limit子句等。eg：表达式2+2 会被重写为4，由clauses.c中eval_cons_expressions()函数负责 2. 布尔表示的规范化：not(not a) 会被重写为a 3. 压平与/或表达式：SQL表准中的是而元操作符，pg内部是多元，计划器总是会假设所有嵌套AND/OR都应当被压平 ##### 找出代价最小的访问路径 计划器对所有可能的访问路径进行代价估算，然后选择代价最小的那个。具体会执行以下几个步骤： 1. 创建一个RelOptInfo数据结构，存储访问路径及其代价 RelOptInfo结构体是通过make_one_rel()函数创建的，并存储于PlannerInfo结构体的simple_rel_array字段中。在初始状态时，RelOptInfo持有着baserestrictinfo变量，如果存在相应的索引，还会持有indexlist变量。baserestrictinfo存储着查询的where子句，而indexlist存储着目标表上相关的索引。 ``` typedef enum RelOptKind { RELOPT_BASEREL, RELOPT_JOINREL, RELOPT_OTHER_MEMBER_REL, RELOPT_UPPER_REL, RELOPT_DEADREL } RelOptKind; typedef struct RelOptInfo { NodeTag type; RelOptKind reloptkind; /* all relations included in this RelOptInfo */ Relids relids; /* set of base relids (rangetable indexes) */ /* size estimates generated by planner */ double rows; /* estimated number of result tuples */ /* per-relation planner control flags */ bool consider_startup; /* keep cheap-startup-cost paths? */ bool consider_param_startup; /* ditto, for parameterized paths? */ bool consider_parallel; /* consider parallel paths? */ /* default result targetlist for Paths scanning this relation */ struct PathTarget *reltarget; /* list of Vars/Exprs, cost, width */ /* materialization information */ List *pathlist; /* Path structures */ List *ppilist; /* ParamPathInfos used in pathlist */ List *partial_pathlist; /* partial Paths */ struct Path *cheapest_startup_path; struct Path *cheapest_total_path; struct Path *cheapest_unique_path; List *cheapest_parameterized_paths; /* parameterization information needed for both base rels and join rels */ /* (see also lateral_vars and lateral_referencers) */ Relids direct_lateral_relids; /* rels directly laterally referenced */ Relids lateral_relids; /* minimum parameterization of rel */ /* information about a base rel (not set for join rels!) */ Index relid; Oid reltablespace; /* containing tablespace */ RTEKind rtekind; /* RELATION, SUBQUERY, or FUNCTION */ AttrNumber min_attr; /* smallest attrno of rel (often <0) */ AttrNumber max_attr; /* largest attrno of rel */ Relids *attr_needed; /* array indexed [min_attr .. max_attr] */ int32 *attr_widths; /* array indexed [min_attr .. max_attr] */ List *lateral_vars; /* LATERAL Vars and PHVs referenced by rel */ Relids lateral_referencers; /* rels that reference me laterally */ List *indexlist; /* list of IndexOptInfo */ List *statlist; /* list of StatisticExtInfo */ BlockNumber pages; /* size estimates derived from pg_class */ double tuples; double allvisfrac; PlannerInfo *subroot; /* if subquery */ List *subplan_params; /* if subquery */ int rel_parallel_workers; /* wanted number of parallel workers */ /* Information about foreign tables and foreign joins */ Oid serverid; /* identifies server for the table or join */ Oid userid; /* identifies user to check access as */ bool useridiscurrent; /* join is only valid for current user */ /* use "struct FdwRoutine" to avoid including fdwapi.h here */ struct FdwRoutine *fdwroutine; void *fdw_private; /* cache space for remembering if we have proven this relation unique */ List *unique_for_rels; /* known unique for these other relid * set(s) */ List *non_unique_for_rels; /* known not unique for these set(s) */ /* used by various scans and joins: */ List *baserestrictinfo; /* RestrictInfo structures (if base rel) */ QualCost baserestrictcost; /* cost of evaluating the above */ Index baserestrict_min_security; /* min security_level found in * baserestrictinfo */ List *joininfo; /* RestrictInfo structures for join clauses * involving this rel */ bool has_eclass_joins; /* T means joininfo is incomplete */ /* used by "other" relations */ Relids top_parent_relids; /* Relids of topmost parents */ } RelOptInfo; ``` 2. 估计所有可能访问路径的代价，并将访问路径添加至RelOptInfo结构中。具体细节： - 创建一条路径，估计改路径中顺序扫描的代价，并将其写入路径中。将该路径添加到RelOptInfo结构的pathlist变量中。 - 如果目标表上存在相关索引，则为每个索引创建相应的索引访问路径。估计所有索引扫描的代价，并将代价写入相应的路径中。然后将索引访问路径添加到pathlist变量中。 - 如果可以进行位图扫描，则创建一条位图扫描的访问路径，估计所有位图扫描的代价，并将代价写入到路径中，然后将位图扫描路径添加到pathlist变量中。 3. 从RelOptInfo的pathlist中，找出代价最小的访问路径 4. 如果有必要，估计limit,order by 和aggregate操作的代价 ###### eg.1 一个不带索引的简单单表查询，该查询同时包含where和order by子句 ``` select * from tbl_1 where id<300 order by data; ``` > 图例参考45页，3.10 3.11  1. 创建一个RelOptInfo结构，将其报错在PlannerInfo结构的simple_rel_array字段中 2. 在RelOptInfo结构的baserestrictinfo字段中，添加一条where子句 > where子句id<30会经由initsplan.c中定义的distribute_restrictinfo_to_rels()函数，添加至列表变量baserestrictinfo中。另外由于目标表上没有相关索引，RelOptInfo的indexlist字段为空。 3. 为了满足排序要求，planner.c中的standard_qp_callback()函数会在PlannerInfo的sor_pathkeys字段中添加一个pathkey. > Pathkey是表示路径排序顺序的数据结构。本例因为查询包含一条ORDER BY子句，且该子句中的列为data，故data会被包装为pathkey，放入列表变量sort_pathkeys中。 4. 创建一个Path结构，并使用cost_seqscan函数估计顺序扫描的代价，并将代价写入Path中。然后使用pathnode.c中定义的add_path()函数，将该路径添加至RelOptInfo中。 >如前所述，Path 中同时包含启动代价和总代价，两者都是由cost_seqscan 函数所估计的。在本例中，因为目标表上没有索引，计划器只估计了顺序扫描的代价，因此最小代价是自动确定的。 5. 创建一个新的RelOptInfo结构，用于处理Order by子句 > 注意，新的RelOptInfo没有baserestrictinfo字段，该信息已经被WHERE子句所持有。 6. 创建一个排序路径，并添加到新的RelOptInfo中，然后让SotPath的subpath字段指向顺序扫描的路径。 ``` typedef struct SortPath { Path path; Path *subpath; /* path representing input source (代表输入来源的子路径)*/ } SortPath; ``` SortPath结构包含path与subpath两个Path结构，path中存储了排序算子本身的相关信息，subpath则指向之前得到的代价最小的路径。 注意顺序扫描路径中的parent字段，该字段指向之前的RelOptInfo结构体（也就是在baserestrictinfo中存储着WHERE子句的那个RelOptInfo）。因此在下一步创建计划树的过程中，尽管新的RelOptInfo结构并未包含baserestrictinfo，但是计划器可以创建一个包含Filter的顺序扫描节点，将WHERE子句作为过滤条件。 这里已经获得了代价最小的访问路径，然后就可以基于此生成一棵计划树。第3.3.3节描述了相关的细节 ###### eg.2 > pg内幕探索，3.3.2.2 ``` --两个查询，且带where子句 mydb=# \d tb1 Table "public.tb1" Column | Type | Collation | Nullable | Default --------+---------+-----------+----------+--------- id | integer | | not null | data | integer | | | Indexes: "tb1_pkey" PRIMARY KEY, btree (id) "tb1_data_idx" btree (data) mydb=# select * from tb1 where id<240; ``` 1. 创建一个RelOptInfo结构体 2. 在baserestrictinfo中添加一个where子句，将目标索引加到indexlist中。 3. 创建一条路径，估算顺序扫描的代价，并添加到pathlist中 4. 创建一个IndexPath，估计索引扫描代价，并通过add_path()函数将IndexPath添加到pathlist中 5. 创建另一个IndexPath，估算另一种索引代价 6. 创建一个新的RelOptInfo结构 7. 将代价最小的路径添加到新的RelOptInfo的pathlist中 > 图例参考3.12-3.14    ##### 创建计划树 计划树的根节点定义在plannodes.h中的PlannedStmt结构，包含19个字段，其中有4个代表性字段： - commandType存储操作的类型，诸如select、update和insert - rtable存储范围表的列表（RangeTblEntry的列表） - relationOids存储与查询相关表的oid - plantree存储一颗由计划节点组成的计划树，每个计划节点对应着一种特定操作，诸如顺序扫描、排序和索引扫描 ``` /* * PlannedStmt节点计划器的输出是一颗计划树，PlannedStmt是计划树的根节点 PlannedStmt存储着执行器所需的“一次性”信息 */ typedef struct PlannedStmt { NodeTag type; CmdType commandType; /* select|insert|update|delete|utility */ uint32 queryId; /* query identifier (copied from Query) */ bool hasReturning; /* is it insert|update|delete RETURNING? */ bool hasModifyingCTE; /* has insert|update|delete in WITH? */ bool canSetTag; /* do I set the command result tag? */ bool transientPlan; /* redo plan when TransactionXmin changes? */ bool dependsOnRole; /* is plan specific to current role? */ bool parallelModeNeeded; /* parallel mode required to execute? */ struct Plan *planTree; /* tree of Plan nodes */ List *rtable; /* list of RangeTblEntry nodes */ /* rtable indexes of target relations for INSERT/UPDATE/DELETE */ List *resultRelations; /* integer list of RT indexes, or NIL */ /* * rtable indexes of non-leaf target relations for UPDATE/DELETE on all * the partitioned tables mentioned in the query. */ List *nonleafResultRelations; /* * rtable indexes of root target relations for UPDATE/DELETE; this list * maintains a subset of the RT indexes in nonleafResultRelations, * indicating the roots of the respective partition hierarchies. */ List *rootResultRelations; List *subplans; /* Plan trees for SubPlan expressions; note * that some could be NULL */ Bitmapset *rewindPlanIDs; /* indices of subplans that require REWIND */ List *rowMarks; /* a list of PlanRowMark's */ List *relationOids; /* OIDs of relations the plan depends on */ List *invalItems; /* other dependencies, as PlanInvalItems */ int nParamExec; /* number of PARAM_EXEC Params used */ Node *utilityStmt; /* non-null if this is utility stmt */ /* statement location in source string (copied from Query) */ int stmt_location; /* start location, or -1 if unknown */ int stmt_len; /* length in bytes; 0 means "rest of string" */ } PlannedStmt; ``` 如上所述，计划树包含各式各样的计划节点。PlanNode 是所有计划节点的基类，其他计划节点都会包含PlanNode结构。比如顺序扫描节点SeqScanNode包含一个PlanNode和一个整型变量scanrelid。PlanNode包含14个字段，下面是7个代表性字段： - startup_cost和total_cost是该节点对应操作的预估代价。 - rows是计划器预计扫描的行数。 - targetlist保存了该查询树中目标项的列表。 - qual储存了限定条件的列表。 - lefttree和righttree用于添加子节点。 ``` /* * 计划节点(plan node) * 所有的计划节点都“派生”自plan结构，将其作为自己的第一个字段。这样确保了当其强制转换为plan结构时所有内容都能正常工作。（当作为通用参数传入执行器时，节点指针会很频繁地转换为plan） 我们从来不会真的去实例化任何plan节点，它只是所有plan类型节点的公共抽象父类。 */ typedef struct Plan { NodeTag type; /* * estimated execution costs for plan (see costsize.c for more info) */ Cost startup_cost; /* cost expended before fetching any tuples */ Cost total_cost; /* total cost (assuming all tuples fetched) */ /* * planner's estimate of result size of this plan step */ double plan_rows; /* number of rows plan is expected to emit */ int plan_width; /* average row width in bytes */ /* * information needed for parallel query */ bool parallel_aware; /* engage parallel-aware logic? */ bool parallel_safe; /* OK to use as part of parallel plan? */ /* * Common structural data for all Plan types. */ int plan_node_id; /* unique across entire final plan tree */ List *targetlist; /* target list to be computed at this node */ List *qual; /* implicitly-ANDed qual conditions */ struct Plan *lefttree; /* input plan tree(s) */ struct Plan *righttree; List *initPlan; /* Init Plan nodes (un-correlated expr * subselects) */ /* * Information for management of parameter-change-driven rescanning * * extParam includes the paramIDs of all external PARAM_EXEC params * affecting this plan node or its children. setParam params from the * node's initPlans are not included, but their extParams are. * * allParam includes all the extParam paramIDs, plus the IDs of local * params that affect the node (i.e., the setParams of its initplans). * These are _all_ the PARAM_EXEC params that affect this node. */ Bitmapset *extParam; Bitmapset *allParam; } Plan; ``` 例子1：计划树由一个排序路径和一个顺序扫描路径组合而成，如图3.15-1。 ``` typedef struct Sort { Plan plan; int numCols; /* number of sort-key columns */ AttrNumber *sortColIdx; /* their indexes in the target list */ Oid *sortOperators; /* OIDs of operators to sort them by */ Oid *collations; /* OIDs of collations */ bool *nullsFirst; /* NULLS FIRST/LAST directions */ } Sort; ``` 例子2：计划树由单个IndexScanNode独立组成，如图3.15-2 ``` typedef struct Scan { Plan plan; Index scanrelid; /* relid is index into the range table */ } Scan; typedef struct IndexScan { Scan scan; Oid indexid; /* OID of index to scan */ List *indexqual; /* list of index quals (usually OpExprs) */ List *indexqualorig; /* the same in original form */ List *indexorderby; /* list of index ORDER BY exprs */ List *indexorderbyorig; /* the same in original form */ List *indexorderbyops; /* OIDs of sort ops for ORDER BY exprs */ ScanDirection indexorderdir; /* forward or backward or don't care */ } IndexScan ```