PostgreSQL技能内幕7：PostgreSQL查询编译

0.简介

一次完备的SQL实验包罗两大部门，一个是查询编译涉及到的内容较多，团体分为查询分析，查询重写和查询优化。竣事后交给实验器其举行编译的实验，本节将团体先容一次查询的流程以及具体分析PG查询编译的三个步调。
1.团体过程

先看一次通例的查询流程，收到查询语句后颠末剖析器和转换器，得到相应的关系代数表达式，然后颠末优化器得到末了的实验操持，末了实验后输出结果。

对于PG，配景的backend收到下令后，起首会调用查询分析模块，然后根据下令范例来做处理处罚，假如是创建表，创建用户这种会直接发送给功能性下令处理处罚模块处理处罚，假如是select，insert等，则必要构建查询树，然后举行查询重写和查询优化，然后交给实验器实验。

代码调用流程如下：

2. exec_simple_query
3.     ->pg_parse_query
4.         ->raw_parser
5.     ->pg_analyze_and_rewrite
6.         ->parse_analyze
7.         ->pg_rewrite_query
8.     ->pg_plan_querie

复制代码

代码目次结构如下：

2.查询分析

查询分析包罗词法分析，语法分析以及语义分析三部门。PG利用Lex与Yacc实现词法分析和语法分析。一条SQL语句在函数pg_parse_query中颠末词法分析和语法分析得到剖析树（PG中的Query结构）。
2.1 Lex

Lex 即为 Lexical Analyzar，是一种天生扫描器的工具。扫描器是一种辨认文本中的词汇模式的步伐。这些词汇模式（大概通例表达式）在一种特别的句子结构中界说。界说了正则表达式匹配规则的Lex文件(后缀名为".l")可以转换为为C语言源代码文件。一个Lex文件分为三段，各段之间利用"%%"分隔：
1）界说段：包罗恣意的C语言头文件、符号分析等，这部门会被直接拷贝到天生文件当中；
2）规则段：正则表达式的匹配规则，每当乐成匹配一个模式，就对应厥后"{}"中的代码；
3）代码段：可以是恣意的C语言代码，但是必须要调用Lex提供的函数，由于这里是Lex的入口函数，完成实际的分析功能。
一个例子：

2. //字数统计
3. %{
4.         int wordCount = 0;
5.         %}
6.         chars [A-za-z\_\'\."]
7.         numbers ([0-9])+
8.         delim [" "\n\t]
9.         whitespace {delim}+
10.         words {chars}+
11.         %%

复制代码

2.2 Yacc

Yacc 即为 Yet Another Compiler Compiler。其 GNU 版叫做 Bison。它是一种工具，将任何一种编程语言的全部语法翻译成针对此种语言的 Yacc 语 法剖析器。它用巴科斯范式(BNF, Backus Naur Form)来誊写。Yacc 文件一样寻常带有 .y 后缀。其也分为三个段，段之间利用%%分隔。
1）界说段：可以是C代码，包罗头文件以及函数声明，同时也可以界说Yacc的内部标记等；
2）规则段：语法规则，每当乐成匹配一个语法后，就对应其反面"{}“中的代码。此中”$$“标识语法表达式中左边结构的值(类似左值)，而”$1"表现语法表达式右边结构第一个标识符对应的值，以此类推；
3）代码段：包罗C代码，同样地也必须包罗一些Yacc函数和Lex通报给Yacc的变量。
一个例子：

2. %
3.         typedef char* string;
4.         #define YYSTYPE string
5.         %}
6.         %token NAME EQ AGE
7.         %%
8.         file : record file
9.         | record
10.         ;
11.         record : NAME EQ AGE {
12.         printf("%s is %s years old!!!\n", $1, $3); }
13.         ;
14.         %%
15.         int main()
16.         {
17.         yyparse();
18.         return 0;
19.         }
20.         int yyerror(char *msg)
21.         {
22.         printf("Error
23.         encountered: %s \n", msg);
24.         }

复制代码

2.3 PG词法分析和语法分析先容

• kwlist.h: 声明keyword列表。可以简朴看几个
  

2. PG_KEYWORD("copy", COPY, UNRESERVED_KEYWORD)
3. PG_KEYWORD("cost", COST, UNRESERVED_KEYWORD)
4. PG_KEYWORD("create", CREATE, RESERVED_KEYWORD)
5. PG_KEYWORD("cross", CROSS, TYPE_FUNC_NAME_KEYWORD)
6. PG_KEYWORD("csv", CSV, UNRESERVED_KEYWORD)

复制代码

2）keywords.c: 界说ScanKeywordLookup函数实现，通过二分查找输入是否为关键字，假如为关键字，返回指针，不是则返回NULL（这依靠于上面的kwlist中声明是有序的）。

2. const ScanKeyword *
3. ScanKeywordLookup(const char *text,
4.           const ScanKeyword *keywords,
5.           int num_keywords)
6. {
7.   int      len,
8.         i;
9.   char    word[NAMEDATALEN];
10.   const ScanKeyword *low;
11.   const ScanKeyword *high;
13.   len = strlen(text);
14.   /* We assume all keywords are shorter than NAMEDATALEN. */
15.   if (len >= NAMEDATALEN)
16.     return NULL;
18.   /*
19.    * Apply an ASCII-only downcasing.  We must not use tolower() since it may
20.    * produce the wrong translation in some locales (eg, Turkish).
21.    */
22.   for (i = 0; i < len; i++)
23.   {
24.     char    ch = text[i];
26.     if (ch >= 'A' && ch <= 'Z')
27.       ch += 'a' - 'A';
28.     word[i] = ch;
29.   }
30.   word[len] = '\0';
32.   /*
33.    * Now do a binary search using plain strcmp() comparison.
34.    */
35.   low = keywords;
36.   high = keywords + (num_keywords - 1);
37.   while (low <= high)
38.   {
39.     const ScanKeyword *middle;
40.     int      difference;
42.     middle = low + (high - low) / 2;
43.     difference = strcmp(middle->name, word);
44.     if (difference == 0)
45.       return middle;
46.     else if (difference < 0)
47.       low = middle + 1;
48.     else
49.       high = middle - 1;
50.   }
52.   return NULL;
53. }

复制代码

3）scansup.c：实现词法分析时常见的函数。
4） scan.l：Lex文件，通过编译编译天生scan.c。
5） gram.y：Yacc文件，通过编译天生gram.c。
6）check_keywords.pl: 查抄在gram.y和kwlist.h中界说的关键字列表划一性
7）parser.c: 剖析的入口，界说raw_parser函数
通过以上文件处理处罚raw_parser会返回一个List ，也就是为每个SQL下令都返回一个剖析树。
2.4 PG语义分析

语义分析会查抄下令中是否包罗不符合语义规定的元素，如表和字段是否存在，函数是否可用。因此语义分析必要访问到数据库中的体系表，从而得到查询表的OID以及查询字段的属性等。
语义分析的入口函数是pg_analyze_and_rewrite，其将词法分析与语法分析处理处罚后得到的parsetree_list中的每棵树都举行语义分析与重写。此中负责语义分析的函数为parse_analyze，该函数对parse_tree举行语法分析并转换为一棵查询树(以Query结点的情势存在)。parse_tree函数中涉及的两个告急的结构体分别为Query和ParseState，此中Query用于存储查询树而ParseState则用于存储语义分析的中心信息，比如是否是子查询，查询涉及的表等，结构如下。Query的天生可以参考transformSelectStmt()的流程，剖析SelectStmt结构天生一个查询树，将其各部门挨个分析填入Query。

2. typedef struct Query
3. {
4.   NodeTag    type;
6.   CmdType    commandType;  /* select|insert|update|delete|utility */
8.   QuerySource querySource;  /* where did I come from? */
10.   uint64    queryId;    /* query identifier (can be set by plugins) */
12.   bool    canSetTag;    /* do I set the command result tag? */
14.   Node     *utilityStmt;  /* non-null if commandType == CMD_UTILITY */
16.   int      resultRelation; /* rtable index of target relation for
17.                  * INSERT/UPDATE/DELETE; 0 for SELECT */
18.   ..........             /* other */
19.   int      stmt_location;  /* start location, or -1 if unknown */
20.   int      stmt_len;    /* length in bytes; 0 means "rest of string" */
21. } Query;
23. struct ParseState
24. {
25.   struct ParseState *parentParseState;  /* stack link */
26.   const char *p_sourcetext;  /* source text, or NULL if not available */
27.   List     *p_rtable;    /* range table so far */
28.   List     *p_joinexprs;  /* JoinExprs for RTE_JOIN p_rtable entries */
29.   List     *p_joinlist;    /* join items so far (will become FromExpr
30.                  * node's fromlist) */
31.   List     *p_namespace;  /* currently-referenceable RTEs (List of
32.                  * ParseNamespaceItem) */
33.   bool    p_lateral_active;  /* p_lateral_only items visible? */
34.   ......                     /* other*/
35. }

复制代码

3.查询重写
从团体流程中我们已经知道，PG会对完成查询分析的非功能性的语句举行查询重写。查询重写是根据规则来举行的，其规则存储在pg_rewrite表中。

2. select rulename,ev_enabled,ev_type from pg_rewrite;

复制代码

各个字段寄义先容：

可以以为一条规则(pg_rewrite的一个元组)是在目标表(ev_class)上实验符合条件(ev_qual)的特定动作(ev_type)时，将用规则动作(ev_action)取代原始的动作大概将规则的动作附加在原始下令之前或之后。
PG中规则分为两类：
1）ev_type：可以分为SELECT，UPDATE，INSERT，DELETE；
2）is_instead：INSTEAD(true)或ALSO(false)
根据必要来举行差别元组的创建就可以创建差别的重写规则，这也表现了PG的扩展性。
4.查询优化

查询优化分为三个步调：1.预处理处罚，处理处罚查询树，告急是提拔子链接和子查询以及having子句等；2.根据改进的查询树，利用特定算法来天生最优毗连路径和候选路径列表；3.根据最优路径，天赋生根本查询操持，然后group by和having等子句的操持节点，天生末了的操持。
查询操持的入口函数是pg_plan_queries，调用关系如下：

1. exec_simple_query
2.     ->pg_plan_queries
3.         ->pg_plan_query
4.             ->planner
5.                 ->standard_planner
6.                     ->subquery_planner
7.                         // 预处理
8.                         ->preprocess_xxx
9.                         ->pull_up_sublinks
10.                         ->pull_up_subqueries
11.                         // 生成计划树
12.                         ->grouping_planner
13.                             ->query_planner
14.                 ->SS_finalize_plan

复制代码

4.1 预处理处罚

预处理处罚阶段时告急负责消除冗余条件，镌汰递归层数(通过提拔子链接与子查询实现)以及简化路径天生等。
4.1.1 提拔子链接和子查询

子链接和子查询的区别：子查询是一条完备的查询语句，而子链接是一条表达式，但是表达式内部也可以包罗查询语句。也就是说，子查询是放在FROM子句里的而子链接则出现在WHERE子句大概HAVING子句中。PG支持嵌套查询的SQL写法，即FROM子句中可以包罗一个SELECT查询语句。原始实验下，会先实验子查询(内部)，再实验父查询。但将子查询提拔后，可以与父查询共同优化，从而进步查询的服从。
提拔子链接的入口函数是pull_up_sublinks，其内部会调用pull_up_sublinks_jointree_recurse函数递归地处理处罚jointree，然后调用pull_up_sublinks_qual_recurse处理处罚束缚条件。
提拔子查询的入口函数是pull_up_subqueries，其内部会调用pull_up_subqueries_recurse函数递归地处理处罚子查询。提拔子查询分为三种环境处理处罚：
1）范围表存在子查询。假如是简朴的子查询，那么调用函数pull_up_simple_subquery直接提拔，而假如是简朴的UNION ALL子查询，那么调用pull_up_simple_union_all直接提拔；
2）FROM表达式存在子查询。调用pull_up_subqueries_recurse举行递归处理处罚；
3）毗连表达式中的子查询。调用pull_up_subqueries_recurse举行递归处理处罚。
4.1.2 预处理处罚表达式

表达式可以是一个目标链表，一个WHERE语句，一个HAVING谓语大概一些别的的东西。在PG中表达式的预处理处罚由函数preprocess_expression完成，其告急作用是：
1）毗连别名利用根本关系变量更换；
2）简化常量表达式；
3）规范表达式内容；
4）将子链接转化为子操持，该转换通过函数make_subplan实现。
4.1.3 处理处罚HAVING子句

对于HAVING子句来说，除了举行前面所提到的预处理处罚外，还必要处理处罚此中的每个条件。假如HAVING子句中没有聚集函数的话，那么它完全可以退化到WHERE子句中去，否则的话它将被写到查询树的HavingQual字段内里。
4.2 改进查询树

4.2.1 路径天生

天生路径工作由函数query_planner来完成，团体流程如下：

由于单表有多种访问方式（索引访问，次序访问等）、表和表直接有着多种毗连方式和毗连次序，以是就算根本表划一，但末了访问终极表的路径大概有着多种，以是优化器思量了全部大概的路径，并选择最优路径来天生查询实验操持。PG中天生实验操持的算法是动态规划（小规模优化）与遗传算法（大规模优化）：
1）动态规划：在PG中，利用动态规划得到最优路径，告急分为三步：1. 初始化，为每个根本表天生访问路径；2. 状态通报，从根本表开始向宿世成毗连表与盘算该毗连表路径必要的代价，并生存此中代价评估最优的路径；3. 通报到末了表时，选出此中最优的路径。生存的路径必要满足以下条件：启动代价最小；总实验代价最小；路径的输出排序键。
2）遗传算法：当表格的数量过多时，遍历全部的表必要斲丧大量的时间和内存空间。因此，PG提供了遗传算法来镌汰必要遍历的路径，从而进步查找路径的服从。不外遗传算法只能找到一个准最优的路径。
4.2.2 代价估计

路径的服从与其在实验过程中必要的CPU时间以及磁盘存取非常干系，因此PG在文件"src/backend/optimizer/path/costsize.c"中界说了一些关于磁盘I/O以及CPU的估算代价：
seq_page_cost:顺寻存取页的代价，值为1.0。
random_page_cost：非次序存取页的代价，值为4.0。
cpu_tuple_cost：典范的CPU处理处罚一个元组的代价，值为0.01。
cpu_index_tuple_cost：典范的CPU处理处罚一个索引元组的代价，值为0.005。
cpu_operator_cost：CPU处理处罚一个典范的WHERE操纵的代价，值为0.0025。
effective_cache_size：用来度量PG和OS缓存的磁盘页的数量，值为16384
一条路径的代价与磁盘中存储的元组数量及元组占用的页数干系，其估计路径代价的步调告急如下：1. 根据统计信息与查询条件估算本次查询必要的I/O次数以及获取的元组个数，并得到估算的磁盘代价；2. 根据元组数量盘算必要的CPU代价；3. 综合思量磁盘代价与CPU代价。
4.3 操持天生

在得到最优路径后，规划器会根据该路径天生对应的操持。PG中天生操持的代码文件是"backend/optimizer/plan/createplan.c"，其提供的入口函数是create_plan，内里包罗了次序扫描，采样扫描，索引扫描，TID扫描等操持的天生。