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

0.简介

一次完整的SQL执行包含两大部分，一个是查询编译涉及到的内容较多，整体分为查询分析，查询重写和查询优化。结束后交给执行器其进行编译的执行，本节将整体介绍一次查询的流程以及详细分析PG查询编译的三个步骤。

1.整体过程

先看一次常规的查询流程，收到查询语句后经过解析器和转换器，得到相应的关系代数表达式，然后经过优化器得到最后的执行计划，最后执行后输出结果。

对于PG，后台的backend收到命令后，首先会调用查询分析模块，然后根据命令类型来做处理，如果是创建表，创建用户这种会直接发送给功能性命令处理模块处理，如果是select，insert等，则需要构建查询树，然后进行查询重写和查询优化，然后交给执行器执行。

代码调用流程如下：

exec_simple_query
    ->pg_parse_query
        ->raw_parser
    ->pg_analyze_and_rewrite
        ->parse_analyze
        ->pg_rewrite_query
    ->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的入口函数，完成实际的分析功能。
一个例子：

//字数统计
%{
        int wordCount = 0;
        %}
        chars [A-za-z\_\'\.\"]
        numbers ([0-9])+
        delim [" "\n\t]
        whitespace {delim}+
        words {chars}+
        %%

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的变量。
一个例子：

%
        typedef char* string;
        #define YYSTYPE string
        %}
        %token NAME EQ AGE
        %%
        file : record file
        | record
        ;
        record : NAME EQ AGE {
        printf("%s is %s years old!!!\n", $1, $3); }
        ;
        %%
        int main()
        {
        yyparse();
        return 0;
        }
        int yyerror(char *msg)
        {
        printf("Error
        encountered: %s \n", msg);
        }

2.3 PG词法分析和语法分析介绍

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

PG_KEYWORD("copy", COPY, UNRESERVED_KEYWORD)
PG_KEYWORD("cost", COST, UNRESERVED_KEYWORD)
PG_KEYWORD("create", CREATE, RESERVED_KEYWORD)
PG_KEYWORD("cross", CROSS, TYPE_FUNC_NAME_KEYWORD)
PG_KEYWORD("csv", CSV, UNRESERVED_KEYWORD)

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

const ScanKeyword *
ScanKeywordLookup(const char *text,
          const ScanKeyword *keywords,
          int num_keywords)
{
  int      len,
        i;
  char    word[NAMEDATALEN];
  const ScanKeyword *low;
  const ScanKeyword *high;

  len = strlen(text);
  /* We assume all keywords are shorter than NAMEDATALEN. */
  if (len >= NAMEDATALEN)
    return NULL;

  /*
   * Apply an ASCII-only downcasing.  We must not use tolower() since it may
   * produce the wrong translation in some locales (eg, Turkish).
   */
  for (i = 0; i < len; i++)
  {
    char    ch = text[i];

    if (ch >= 'A' && ch <= 'Z')
      ch += 'a' - 'A';
    word[i] = ch;
  }
  word[len] = '\0';

  /*
   * Now do a binary search using plain strcmp() comparison.
   */
  low = keywords;
  high = keywords + (num_keywords - 1);
  while (low <= high)
  {
    const ScanKeyword *middle;
    int      difference;

    middle = low + (high - low) / 2;
    difference = strcmp(middle->name, word);
    if (difference == 0)
      return middle;
    else if (difference < 0)
      low = middle + 1;
    else
      high = middle - 1;
  }

  return NULL;
}

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。

typedef struct Query
{
  NodeTag    type;

  CmdType    commandType;  /* select|insert|update|delete|utility */

  QuerySource querySource;  /* where did I come from? */

  uint64    queryId;    /* query identifier (can be set by plugins) */

  bool    canSetTag;    /* do I set the command result tag? */

  Node     *utilityStmt;  /* non-null if commandType == CMD_UTILITY */

  int      resultRelation; /* rtable index of target relation for
                 * INSERT/UPDATE/DELETE; 0 for SELECT */
  ..........             /* other */
  int      stmt_location;  /* start location, or -1 if unknown */
  int      stmt_len;    /* length in bytes; 0 means "rest of string" */
} Query;

struct ParseState
{
  struct ParseState *parentParseState;  /* stack link */
  const char *p_sourcetext;  /* source text, or NULL if not available */
  List     *p_rtable;    /* range table so far */
  List     *p_joinexprs;  /* JoinExprs for RTE_JOIN p_rtable entries */
  List     *p_joinlist;    /* join items so far (will become FromExpr
                 * node's fromlist) */
  List     *p_namespace;  /* currently-referenceable RTEs (List of
                 * ParseNamespaceItem) */
  bool    p_lateral_active;  /* p_lateral_only items visible? */
  ......                     /* other*/
}

3.查询重写

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

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，调用关系如下：

exec_simple_query
    ->pg_plan_queries
        ->pg_plan_query
            ->planner
                ->standard_planner
                    ->subquery_planner
                        // 预处理
                        ->preprocess_xxx
                        ->pull_up_sublinks
                        ->pull_up_subqueries
                        // 生成计划树
                        ->grouping_planner
                            ->query_planner
                ->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扫描等计划的生成。