第三章 查询处理
2021-10-11 15:10:14 0 举报AI智能生成
postgreSQL查询处理
作者其他创作
大纲/内容
3.1 概览
3.1.1 解析器（Parser）
语法解析树结构体
typedef struct SelectStmt
{
NodeTag type;
/* 这些字段只会在SelectStmts“叶节点”中使用 */
List *distinctClause; /* NULL, DISTINCT ON表达式列表, 或
对所有的(SELECT DISTINCT)为lcons(NIL,NIL) */
IntoClause *intoClause; /* SELECT INTO 的目标 */
List *targetList; /* 结果目标列表 (ResTarget) */
List *fromClause; /* FROM 子句 */
Node *whereClause; /* WHERE 限定条件 */
List *groupClause; /* GROUP BY 子句 */
Node *havingClause; /* HAVING 条件表达式 */
List *windowClause; /* WINDOW window_name AS (...), ... */
/* 在一个表示值列表的叶节点中，上面的字段全都为空，而这个字段会被设置。
* 注意这个子列表中的元素仅仅是表达式，没有ResTarget的修饰，还需要注意列表元素可能为
* DEFAULT (表示一个 SetToDefault 节点)，而无论值列表的上下文。
* 由分析阶段决定否合法并拒绝。 */
List *valuesLists; /* 未转换的表达式列表 */
/* 这些字段会同时在SelectStmts叶节点与SelectStmts上层节点中使用 */
List *sortClause; /* 排序子句 (排序依据的列表) */
Node *limitOffset; /* 需要跳过的元组数目 */
Node *limitCount; /* 需要返回的元组数目 */
List *lockingClause; /* FOR UPDATE (锁子句的列表) */
WithClause *withClause; /* WITH 子句 */
/* 这些字段只会在上层的 SelectStmts 中出现 */
SetOperation op; /* set 操作的类型 */
bool all; /* 是否指明了 ALL 选项? */
struct SelectStmt *larg; /* 左子节点 */
struct SelectStmt *rarg; /* 右子节点 */
} SelectStmt;
{
NodeTag type;
/* 这些字段只会在SelectStmts“叶节点”中使用 */
List *distinctClause; /* NULL, DISTINCT ON表达式列表, 或
对所有的(SELECT DISTINCT)为lcons(NIL,NIL) */
IntoClause *intoClause; /* SELECT INTO 的目标 */
List *targetList; /* 结果目标列表 (ResTarget) */
List *fromClause; /* FROM 子句 */
Node *whereClause; /* WHERE 限定条件 */
List *groupClause; /* GROUP BY 子句 */
Node *havingClause; /* HAVING 条件表达式 */
List *windowClause; /* WINDOW window_name AS (...), ... */
/* 在一个表示值列表的叶节点中，上面的字段全都为空，而这个字段会被设置。
* 注意这个子列表中的元素仅仅是表达式，没有ResTarget的修饰，还需要注意列表元素可能为
* DEFAULT (表示一个 SetToDefault 节点)，而无论值列表的上下文。
* 由分析阶段决定否合法并拒绝。 */
List *valuesLists; /* 未转换的表达式列表 */
/* 这些字段会同时在SelectStmts叶节点与SelectStmts上层节点中使用 */
List *sortClause; /* 排序子句 (排序依据的列表) */
Node *limitOffset; /* 需要跳过的元组数目 */
Node *limitCount; /* 需要返回的元组数目 */
List *lockingClause; /* FOR UPDATE (锁子句的列表) */
WithClause *withClause; /* WITH 子句 */
/* 这些字段只会在上层的 SelectStmts 中出现 */
SetOperation op; /* set 操作的类型 */
bool all; /* 是否指明了 ALL 选项? */
struct SelectStmt *larg; /* 左子节点 */
struct SelectStmt *rarg; /* 右子节点 */
} SelectStmt;
解析器根据SQL语句生成一颗语法解析树（parse tree）
3.1.2 分析器（Analyzer）
分析器数据结构
/*
* Query -
* 解析与分析过程会将所有的语句转换为一颗查询树，供重写器与计划器用于进一步的处理。
* 功能语句（即不可优化的语句）会设置utilityStmt字段，而Query结构本身基本上是空的。
* DECLARE CURSOR 是一个特例：它的形式与SELECT类似，但原始的DeclareCursorStmt会
* 被放在 utilityStmt 字段中。
* 计划过程会将查询树转换为一颗计划树，计划树的根节点是一个PlannedStmt结构
* 执行器不会用到查询树结构
*/
typedef struct Query
{
NodeTag type;
CmdType commandType; /* select|insert|update|delete|utility */
QuerySource querySource; /* 我来自哪里? */
uint32 queryId; /* 查询标识符 (可由插件配置) */
bool canSetTag; /* 我设置了命令结果标签吗? */
Node *utilityStmt; /* 如果这是一条DECLARE CURSOR或不可优化的语句 */
int resultRelation; /* 对增删改语句而言是目标关系的索引; SELECT为0 */
bool hasAggs; /* 是否在目标列表或having表达式中指定了聚合函数 */
bool hasWindowFuncs; /* tlist是否包含窗口函数 */
bool hasSubLinks; /* 是否包含子查询SubLink */
bool hasDistinctOn; /* 是否包含来自DISTINCT ON的distinct子句 */
bool hasRecursive; /* 是否制定了WITH RECURSIVE */
bool hasModifyingCTE; /* 是否在WITH子句中包含了INSERT/UPDATE/DELETE */
bool hasForUpdate; /* 是否指定了FOR [KEY] UPDATE/SHARE*/
bool hasRowSecurity; /* 是否应用了行安全策略 */
List *cteList; /* CTE列表 */
List *rtable; /* 范围表项目列表 */
FromExpr *jointree; /* 表连接树 (FROM 与 WHERE 子句) */
List *targetList; /* 目标列表 (TargetEntry的列表) */
List *withCheckOptions; /* WithCheckOption的列表 */
OnConflictExpr *onConflict; /* ON CONFLICT DO [NOTHING | UPDATE] */
List *returningList; /* 返回值列表(TargetEntry的列表) */
List *groupClause; /* SortGroupClause的列表 */
List *groupingSets; /* 如果有，GroupingSet的列表 */
Node *havingQual; /* 分组的Having条件列表 */
List *windowClause; /* 窗口子句列表 */
List *distinctClause; /* SortGroupClause列表 */
List *sortClause; /* SortGroupClause列表 */
Node *limitOffset; /* Offset跳过元组数目 (int8 表达式) */
Node *limitCount; /* Limit返回元组数目 (int8 表达式) */
List *rowMarks; /* RowMarkClause列表 */
Node *setOperations; /* 如果是UNION/INTERSECT/EXCEPT的顶层查询，
则为集合操作列表 */
List *constraintDeps; /* 确认查询语义是否合法时，所依赖约束对象的OID列表 */
} Query;
* Query -
* 解析与分析过程会将所有的语句转换为一颗查询树，供重写器与计划器用于进一步的处理。
* 功能语句（即不可优化的语句）会设置utilityStmt字段，而Query结构本身基本上是空的。
* DECLARE CURSOR 是一个特例：它的形式与SELECT类似，但原始的DeclareCursorStmt会
* 被放在 utilityStmt 字段中。
* 计划过程会将查询树转换为一颗计划树，计划树的根节点是一个PlannedStmt结构
* 执行器不会用到查询树结构
*/
typedef struct Query
{
NodeTag type;
CmdType commandType; /* select|insert|update|delete|utility */
QuerySource querySource; /* 我来自哪里? */
uint32 queryId; /* 查询标识符 (可由插件配置) */
bool canSetTag; /* 我设置了命令结果标签吗? */
Node *utilityStmt; /* 如果这是一条DECLARE CURSOR或不可优化的语句 */
int resultRelation; /* 对增删改语句而言是目标关系的索引; SELECT为0 */
bool hasAggs; /* 是否在目标列表或having表达式中指定了聚合函数 */
bool hasWindowFuncs; /* tlist是否包含窗口函数 */
bool hasSubLinks; /* 是否包含子查询SubLink */
bool hasDistinctOn; /* 是否包含来自DISTINCT ON的distinct子句 */
bool hasRecursive; /* 是否制定了WITH RECURSIVE */
bool hasModifyingCTE; /* 是否在WITH子句中包含了INSERT/UPDATE/DELETE */
bool hasForUpdate; /* 是否指定了FOR [KEY] UPDATE/SHARE*/
bool hasRowSecurity; /* 是否应用了行安全策略 */
List *cteList; /* CTE列表 */
List *rtable; /* 范围表项目列表 */
FromExpr *jointree; /* 表连接树 (FROM 与 WHERE 子句) */
List *targetList; /* 目标列表 (TargetEntry的列表) */
List *withCheckOptions; /* WithCheckOption的列表 */
OnConflictExpr *onConflict; /* ON CONFLICT DO [NOTHING | UPDATE] */
List *returningList; /* 返回值列表(TargetEntry的列表) */
List *groupClause; /* SortGroupClause的列表 */
List *groupingSets; /* 如果有，GroupingSet的列表 */
Node *havingQual; /* 分组的Having条件列表 */
List *windowClause; /* 窗口子句列表 */
List *distinctClause; /* SortGroupClause列表 */
List *sortClause; /* SortGroupClause列表 */
Node *limitOffset; /* Offset跳过元组数目 (int8 表达式) */
Node *limitCount; /* Limit返回元组数目 (int8 表达式) */
List *rowMarks; /* RowMarkClause列表 */
Node *setOperations; /* 如果是UNION/INTERSECT/EXCEPT的顶层查询，
则为集合操作列表 */
List *constraintDeps; /* 确认查询语义是否合法时，所依赖约束对象的OID列表 */
} Query;
分析器对语法解析树进行语义分析，生成一颗查询树（query tree）
3.1.3 重写器（Rewriter）
重写器按照规则系统中存在的规则，对查询树进行改写。
重写器结构体
子主题
3.1.4 计划器与执行器
计划器基于查询树，生成一颗执行效率最高的计划树（plan tree）
执行器按照计划树中的顺序访问表和索引，执行相应查询。
计划器结构体
执行器结构体
3.2 单表查询的代价估计
3.2.1 顺序扫描
顺序扫描的代价是通过函数cost_seqscan()估计的。
3.2.2 索引扫描
尽管PostgreSQL支持很多索引方法，比如B树，GiST，GIN和BRIN，不过索引扫描的代价估计都使用一个共用的代价函数：cost_index()。
3.2.3 排序
排序路径（sort path） 会在排序操作中被使用。排序操作包括ORDER BY，归并连接的预处理操作，以及其他函数。函数cost_sort()用于估计排序操作的代价。
代价
PostgreSQL的查询优化是基于代价（Cost）的。代价是一个无量纲的值，它并不是一种绝对的性能指标，但可以作为比较各种操作代价时的相对性能指标。
costsize.c中的函数用于估算各种操作的代价。所有被执行器执行的操作都有着相应的代价函数。例如，函数cost_seqscan() 和 cost_index()分别用于估算顺序扫描和索引扫描的代价。
在PostgreSQL中有三种代价：启动（start-up） ， 运行（run）和总和（total）。总代价是启动代价和运行代价的和；因此只有启动代价和运行代价是单独估计的。
启动代价（start-up）：在读取到第一条元组前花费的代价，比如索引扫描节点的启动代价就是读取目标表的索引页，取到第一个元组的代价
运行代价（run）： 获取全部元组的代价
总代价（total）：前两者之和
costsize.c中的函数用于估算各种操作的代价。所有被执行器执行的操作都有着相应的代价函数。例如，函数cost_seqscan() 和 cost_index()分别用于估算顺序扫描和索引扫描的代价。
在PostgreSQL中有三种代价：启动（start-up） ， 运行（run）和总和（total）。总代价是启动代价和运行代价的和；因此只有启动代价和运行代价是单独估计的。
启动代价（start-up）：在读取到第一条元组前花费的代价，比如索引扫描节点的启动代价就是读取目标表的索引页，取到第一个元组的代价
运行代价（run）： 获取全部元组的代价
总代价（total）：前两者之和
3.3 创建单表查询的计划树
3.3.1 预处理
简化目标列表（target list），LIMIT子句等；
例如，表达式2+2会被重写为4，这是由clauses.c中eval_const_expressions()函数负责的。
布尔表达式的规范化
例如，NOT(NOT a)会被重写为a
压平与/或表达式
SQL标准中的AND/OR是二元操作符；但在PostgreSQL内部它们是多元操作符。而计划器总是会假设所有的嵌套AND/OR都应当被压平。
例如，表达式2+2会被重写为4，这是由clauses.c中eval_const_expressions()函数负责的。
布尔表达式的规范化
例如，NOT(NOT a)会被重写为a
压平与/或表达式
SQL标准中的AND/OR是二元操作符；但在PostgreSQL内部它们是多元操作符。而计划器总是会假设所有的嵌套AND/OR都应当被压平。
3.3.2 找出代价最小的访问路径
创建一个RelOptInfo数据结构，存储访问路径及其代价。
RelOptInfo结构体是通过make_one_rel()函数创建的，并存储于PlannerInfo结构体的simple_rel_array字段中，如图3.10所示。在初始状态时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;
/* 本RelOptInfo包含的所有关系 */
Relids relids; /* 基本关系的ID集合 (范围表索引) */
/* 由计划器生成的预估尺寸 */
double rows; /* 预估结果元组数目 */
/* 计划器标记位，每个关系一份 */
bool consider_startup; /* 保留启动代价最低的路径？ */
bool consider_param_startup; /* 同上, 针对参数化路径？ */
bool consider_parallel; /* 考虑并行路径？ */
/* 扫描当前关系的默认结果目标列表 */
struct PathTarget *reltarget; /* Vars/Exprs, 代价, 宽度的列表 */
/* 物化相关信息 */
List *pathlist; /* Path 结构体列表 */
List *ppilist; /* pathlist中使用的ParamPathInfos */
List *partial_pathlist; /* 部分路径 */
struct Path *cheapest_startup_path;
struct Path *cheapest_total_path;
struct Path *cheapest_unique_path;
List *cheapest_parameterized_paths;
/* 基础关系与连接关系都需要的 参数化信息 */
/* (参见 lateral_vars 与 lateral_referencers) */
Relids direct_lateral_relids; /* 直接以LATERAL方式引用的关系 */
Relids lateral_relids;
/* 关于基础关系的信息 (连接关系不会设置这些字段！) */
Index relid;
Oid reltablespace; /* 表空间 */
RTEKind rtekind; /* RELATION, SUBQUERY, 或 FUNCTION */
AttrNumber min_attr; /* 关系属性的最小值 (通常<0) */
AttrNumber max_attr; /* 关系属性的最大值 */
Relids *attr_needed; /* 被索引的数组 [min_attr .. max_attr] */
int32 *attr_widths; /* 被索引的数组 [min_attr .. max_attr] */
List *lateral_vars; /* 关系所引用的LATERAL Vars 与 PHVs */
Relids lateral_referencers;/* 侧面引用本表的关系 */
List *indexlist; /* IndexOptInfo列表 */
BlockNumber pages; /* 来自pg_class的页面数估计值 */
double tuples;
double allvisfrac;
PlannerInfo *subroot; /* 如有子查询 */
List *subplan_params; /* 如有子查询 */
int rel_parallel_workers; /* 期望的并行工作进程数量 */
/* 有关外部表与外部表连接的相关信息 */
Oid serverid; /* 外部表与外部表连接相应的服务器ID */
Oid userid; /* 用于检查访问权限的用户标识 */
bool useridiscurrent;/* 当前用户是否能合法进行JOIN */
struct FdwRoutine *fdwroutine;
void *fdw_private;
/* 被各种扫描与连接所使用 */
List *baserestrictinfo; /* RestrictInfo结构体列表 (如果存在基础关系) */
QualCost baserestrictcost; /* 求值上述限制条件的代价 */
List *joininfo; /* RestrictInfo 结构体列表，涉及到本表的连接会用到 */
bool has_eclass_joins; /* T 意味着joininfo不完整 */
} RelOptInfo;
估计所有可能访问路径的代价，并将访问路径添加至RelOptInfo结构中。
这一处理过程的细节如下：
创建一条路径，估计该路径中顺序扫描的代价，并将其写入路径中。将该路径添加到RelOptInfo结构的pathlist变量中。
如果目标表上存在相关的索引，则为每个索引创建相应的索引访问路径。估计所有索引扫描的代价，并将代价写入相应路径中。然后将索引访问路径添加到pathlist变量中。
如果可以进行位图扫描，则创建一条位图扫描访问路径。估计所有的位图扫描的代价，并将代价写入到路径中。然后将位图扫描路径添加到pathlist变量中。
从RelOptInfo的pathlist中，找出代价最小的访问路径。
如有必要，估计LIMIT，ORDER BY和AGGREGATE操作的代价。
RelOptInfo结构体是通过make_one_rel()函数创建的，并存储于PlannerInfo结构体的simple_rel_array字段中，如图3.10所示。在初始状态时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;
/* 本RelOptInfo包含的所有关系 */
Relids relids; /* 基本关系的ID集合 (范围表索引) */
/* 由计划器生成的预估尺寸 */
double rows; /* 预估结果元组数目 */
/* 计划器标记位，每个关系一份 */
bool consider_startup; /* 保留启动代价最低的路径？ */
bool consider_param_startup; /* 同上, 针对参数化路径？ */
bool consider_parallel; /* 考虑并行路径？ */
/* 扫描当前关系的默认结果目标列表 */
struct PathTarget *reltarget; /* Vars/Exprs, 代价, 宽度的列表 */
/* 物化相关信息 */
List *pathlist; /* Path 结构体列表 */
List *ppilist; /* pathlist中使用的ParamPathInfos */
List *partial_pathlist; /* 部分路径 */
struct Path *cheapest_startup_path;
struct Path *cheapest_total_path;
struct Path *cheapest_unique_path;
List *cheapest_parameterized_paths;
/* 基础关系与连接关系都需要的 参数化信息 */
/* (参见 lateral_vars 与 lateral_referencers) */
Relids direct_lateral_relids; /* 直接以LATERAL方式引用的关系 */
Relids lateral_relids;
/* 关于基础关系的信息 (连接关系不会设置这些字段！) */
Index relid;
Oid reltablespace; /* 表空间 */
RTEKind rtekind; /* RELATION, SUBQUERY, 或 FUNCTION */
AttrNumber min_attr; /* 关系属性的最小值 (通常<0) */
AttrNumber max_attr; /* 关系属性的最大值 */
Relids *attr_needed; /* 被索引的数组 [min_attr .. max_attr] */
int32 *attr_widths; /* 被索引的数组 [min_attr .. max_attr] */
List *lateral_vars; /* 关系所引用的LATERAL Vars 与 PHVs */
Relids lateral_referencers;/* 侧面引用本表的关系 */
List *indexlist; /* IndexOptInfo列表 */
BlockNumber pages; /* 来自pg_class的页面数估计值 */
double tuples;
double allvisfrac;
PlannerInfo *subroot; /* 如有子查询 */
List *subplan_params; /* 如有子查询 */
int rel_parallel_workers; /* 期望的并行工作进程数量 */
/* 有关外部表与外部表连接的相关信息 */
Oid serverid; /* 外部表与外部表连接相应的服务器ID */
Oid userid; /* 用于检查访问权限的用户标识 */
bool useridiscurrent;/* 当前用户是否能合法进行JOIN */
struct FdwRoutine *fdwroutine;
void *fdw_private;
/* 被各种扫描与连接所使用 */
List *baserestrictinfo; /* RestrictInfo结构体列表 (如果存在基础关系) */
QualCost baserestrictcost; /* 求值上述限制条件的代价 */
List *joininfo; /* RestrictInfo 结构体列表，涉及到本表的连接会用到 */
bool has_eclass_joins; /* T 意味着joininfo不完整 */
} RelOptInfo;
估计所有可能访问路径的代价，并将访问路径添加至RelOptInfo结构中。
这一处理过程的细节如下：
创建一条路径，估计该路径中顺序扫描的代价，并将其写入路径中。将该路径添加到RelOptInfo结构的pathlist变量中。
如果目标表上存在相关的索引，则为每个索引创建相应的索引访问路径。估计所有索引扫描的代价，并将代价写入相应路径中。然后将索引访问路径添加到pathlist变量中。
如果可以进行位图扫描，则创建一条位图扫描访问路径。估计所有的位图扫描的代价，并将代价写入到路径中。然后将位图扫描路径添加到pathlist变量中。
从RelOptInfo的pathlist中，找出代价最小的访问路径。
如有必要，估计LIMIT，ORDER BY和AGGREGATE操作的代价。
3.3.3 创建计划树
在最后一步中，计划器按照代价最小的路径生成一颗计划树。
计划树的根节点是定义在plannodes.h中的PlannedStmt结构，包含19个字段，其中有4个代表性字段：
**commandType**存储操作的类型，诸如SELECT，UPDATE和INSERT。
**rtable**存储范围表的列表（RangeTblEntry的列表）。
**relationOids**存储与查询相关表的oid。
**plantree**存储着一颗由计划节点组成的计划树，每个计划节点对应着一种特定操作，诸如顺序扫描，排序和索引扫描。
计划树的根节点是定义在plannodes.h中的PlannedStmt结构，包含19个字段，其中有4个代表性字段：
**commandType**存储操作的类型，诸如SELECT，UPDATE和INSERT。
**rtable**存储范围表的列表（RangeTblEntry的列表）。
**relationOids**存储与查询相关表的oid。
**plantree**存储着一颗由计划节点组成的计划树，每个计划节点对应着一种特定操作，诸如顺序扫描，排序和索引扫描。
PlanNode是所有计划节点的基类，其他计划节点都会包含PlanNode结构。比如顺序扫描节点SeqScanNode，包含一个PlanNode和一个整型变量scanrelid。PlanNode包含14个字段。下面是7个代表性字段：
startup_cost和total_cost是该节点对应操作的预估代价。
rows是计划器预计扫描的行数。
targetlist保存了该查询树中目标项的列表。
qual储存了限定条件的列表。
lefttree和righttree用于添加子节点。
startup_cost和total_cost是该节点对应操作的预估代价。
rows是计划器预计扫描的行数。
targetlist保存了该查询树中目标项的列表。
qual储存了限定条件的列表。
lefttree和righttree用于添加子节点。
3.4 执行器如何工作
临时文件
执行器在处理查询时会使用工作内存（work_mem）和临时缓冲区（temp_buffers），两者都于内存中分配。如果查询无法在内存中完成，就会用到临时文件。
3.5 连接
3.5.1 嵌套循环连接
3.5.2 归并连接
3.5.3 散列连接
3.5.4 连接访问路径与连接节点
3.6 创建多表查询计划树
3.6.1 预处理
3.6.2 获取代价最小的路径
3.6.3 获取三表查询代价最小的路径
0 条评论
下一页
