第三章查询处理思维导图模板_ProcessOn思维导图、流程图

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;

解析器根据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 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）：前两者之和

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都应当被压平。

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操作的代价。

3.3.3 创建计划树

在最后一步中，计划器按照代价最小的路径生成一颗计划树。  计划树的根节点是定义在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用于添加子节点。

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 获取三表查询代价最小的路径