3.3创建单表查询的计划树
Postgresql中的计划器会执行三个处理步骤：
- 执行预处理
- 在所有可能的访问路径中，找出代价最小的访问路径
- 按照代价最小的路径，创建计划树
访问路径是估算代价时的处理单元。比如顺序扫描、索引扫描、排序，以及各种连接操作都有其对应的路径。访问路径只在计划器创建查询计划树的时候使用。最基本的访问路径数据结构就是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中的查询树进行一些预处理
- 计简化目标列表，limit子句等。eg：表达式2+2 会被重写为4，由clauses.c中eval_cons_expressions()函数负责
- 布尔表示的规范化：not(not a) 会被重写为a
- 压平与/或表达式：SQL表准中的是而元操作符，pg内部是多元，计划器总是会假设所有嵌套AND/OR都应当被压平
找出代价最小的访问路径
计划器对所有可能的访问路径进行代价估算，然后选择代价最小的那个。具体会执行以下几个步骤：
- 创建一个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;
- 估计所有可能访问路径的代价，并将访问路径添加至RelOptInfo结构中。具体细节：
- 创建一条路径，估计改路径中顺序扫描的代价，并将其写入路径中。将该路径添加到RelOptInfo结构的pathlist变量中。
- 如果目标表上存在相关索引，则为每个索引创建相应的索引访问路径。估计所有索引扫描的代价，并将代价写入相应的路径中。然后将索引访问路径添加到pathlist变量中。
- 如果可以进行位图扫描，则创建一条位图扫描的访问路径，估计所有位图扫描的代价，并将代价写入到路径中，然后将位图扫描路径添加到pathlist变量中。
- 从RelOptInfo的pathlist中，找出代价最小的访问路径
- 如果有必要，估计limit,order by 和aggregate操作的代价
eg.1
一个不带索引的简单单表查询，该查询同时包含where和order by子句
select * from tbl_1 where id<300 order by data;
图例参考45页，3.10 3.11
- 创建一个RelOptInfo结构，将其报错在PlannerInfo结构的simple_rel_array字段中
- 在RelOptInfo结构的baserestrictinfo字段中，添加一条where子句
where子句id<30会经由initsplan.c中定义的distribute_restrictinfo_to_rels()函数，添加至列表变量baserestrictinfo中。另外由于目标表上没有相关索引，RelOptInfo的indexlist字段为空。
- 为了满足排序要求，planner.c中的standard_qp_callback()函数会在PlannerInfo的sor_pathkeys字段中添加一个pathkey.
Pathkey是表示路径排序顺序的数据结构。本例因为查询包含一条ORDER BY子句，且该子句中的列为data，故data会被包装为pathkey，放入列表变量sort_pathkeys中。
- 创建一个Path结构，并使用cost_seqscan函数估计顺序扫描的代价，并将代价写入Path中。然后使用pathnode.c中定义的add_path()函数，将该路径添加至RelOptInfo中。
如前所述，Path 中同时包含启动代价和总代价，两者都是由cost_seqscan 函数所估计的。在本例中，因为目标表上没有索引，计划器只估计了顺序扫描的代价，因此最小代价是自动确定的。
- 创建一个新的RelOptInfo结构，用于处理Order by子句
注意，新的RelOptInfo没有baserestrictinfo字段，该信息已经被WHERE子句所持有。
- 创建一个排序路径，并添加到新的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;
- 创建一个RelOptInfo结构体
- 在baserestrictinfo中添加一个where子句，将目标索引加到indexlist中。
- 创建一条路径，估算顺序扫描的代价，并添加到pathlist中
- 创建一个IndexPath，估计索引扫描代价，并通过add_path()函数将IndexPath添加到pathlist中
- 创建另一个IndexPath，估算另一种索引代价
- 创建一个新的RelOptInfo结构
- 将代价最小的路径添加到新的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
