以前的学习笔记

查询路径

下面是查询获得结果的各个必经阶段

  1. 应用程序和postgres服务器建立连接。应用程序提交查询到服务器然后等待服务器返回结果

  2. 解析阶段parse stage检查通过应用程序查询提交的查询,检查语法是否正确,然后创建查询树

  3. 重写系统rewrite system采用解析阶段创建的查询树,然后从存储在系统目录里查找可以应用的规则。它执行规则主题中给出的转换。

    重写系统中的一个应用是视图的实现。每当有一个针对视图的查询,重写系统会根据视图的定义将用户的查询修改为基本表的查询。

  4. 计划器/优化器planner/optimizer采用查询树去创建一个将要输入给执行器的查询计划。它先创建所有能达到查询目的的可能路径。例如,如果有一个关系上的索引被查询到,会有两条可以扫描的路径。一种是简单的顺序扫描,另外一种是使用索引的扫描。然后,会评估每条路径的花费去选择代价最小的那条路径。代价最小的那条路径就会被展开成一个完整的可供执行器执行计划。

  5. 执行器递归查询树上的步骤并以计划展示的方式来检索行。执行器使用存储系统storage system来扫描关系、执行排序、连接、评估质量并最终返回结果。

连接是怎么建立的

postgresql是使用一个简单的”process per user” 客户端/服务区模型的系统。在这个模型中,有一个客户端进程刚好被被连接到一个服务器进程上(即一个客户端进程都有一个对应的服务器进程)。由于我们无法知道会建立多少个客户端,因此,必须存在一个主进程,每一次有链接建立的时候,主进程都会创建一个对应的服务器进程。这个主进程叫做postgres,负责监听TCP/IP端口来接受连接。每当postgres检测到一个新连接的时候,就会生成一个新的服务器进程。服务器任务在并发执行期间互相通过信号量(sempahore)和共享内存(shared memory)来确保数据的完整性。

客户端进程可以是任何一个使用标准postgres协议的程序。许多客户端都是基于C语言的libpq库,也有一些独立实现的协议,例如jdbc驱动。

一旦连接建立,客户端进程就可以发送查询到后端。查询使用纯文本被发送,客户端也不做解析。服务端解析查询、创建执行计划、执行执行计划和通过建立的连接向客户端返回结果。

解析阶段

解析阶段包含两个部分

  1. 在gram.y 和 scan.l中定义的解析器是使用unix工具bison和flex创建的
  2. 转换过程transformation process对解析器解析的数据结构进行了修改和填充

解析器

解析器必须检查纯文本的查询语句的语法是否正确。如果语法是正确的,那么解析树就会被建立和向后传递,否则就返回一个错误。解析器和词法分析器lexer使用了众所周知的unix工具bison和flex。

lexer在scan.l中被定义,负责去识别标记符(例如SQL关键字)。对于每一个被发现关键字和标识符,都会产生一个token传递给解析器

解析器在gram.y中被定义,由一系列的语法规则和每当触发规则时执行的动作组成。这些动作所对应的代码被使用来构建解析树。

scan.l用程序flex转换成C源码文件,gram.y用bison转换成gram.c文件。在执行完转换以后,可以使用普通的C编译器来创建解析器。不要对生成的C文件进行任何修改,因为它们会在下一次调用flex和bison时被覆盖。

gram.y中的内容超出了这个文档的内容。如果想要了解里面的语法规则,有许多书和文档可以参考。

转换过程

解析阶段创建的解析树仅仅使用关于SQL语法结构的固定规则。它没有去查询系统目录,因此无法了解要求的操作具体语义。在解析完成后,转换过程采用parser返回的树作为输入,并进行必要的语义解释来了解那些表、函数、操作符被引用。然后建立一个存储了这些信息的查询树。

一个关于将原始解析(即创建解析树)和 语义分析分来的理由是系统目录查询只能在一个事务里去做,我们不希望接收一个查询字符串后就立即开启一个事务。原始解析阶段足以识别事务控制命令(例如BEGIN,ROLLBACK等),然后不需要进一步的解析就可以被正确的执行。一旦知道的是处理的是一个实际的查询(例如SELECT或者UPDATE),如果不在事务中就可以开启一个事务了。只有这样,才能调用转换过程。

个人理解,由于查询系统目录必须要开启一个事务,开启事务又需要有对应的开销。但是不是所有的查询都需要去查询系统目录,例如,如果是一个BEGIN或者ROLLBACK这样的语句,转换过程也就不需要去查询系统目录了。一旦返现执行的语句是SELECL或者UPDATE这些实际的查询,那么就需要查询系统目录来找到对应的表、函数、操作符的引用,此时再开启事务也不迟。综上,将两者分开来,可以减小事务的粒度。

被转换过程创建的查询树大部分和原始解析树很相似,但是有很多细节上的不同。例如,一个FuncCall节点在解析树上代表一个从语法上看起来像一个函数调用的东西。它或许被转换为一个FuncExpr节点或者Aggref节点取决于引用的名字对应的是一个普通的函数或者是一个聚合函数。此外,关于字段和表达式结果对应的实际数据类型的信息也会被添加到查询树上。

规则系统

PostreSQL支持一个强大的规则系统rule system来规范视图和模糊视图更新。通常PostreSQL的规则系统有两个实现组成

  1. 第一个使用row level处理工作,并在执行程序中深入实现。每当访问一个单独的行时,规则系统就被调用。这个实现在1995年被移除。
  2. 第二个实现是一种叫做查询重写的技术。重写系统是一个存在于解析阶段和计划/优化阶段之间的模块。这个技术仍在实施。

查询重写在第40章有一些细节的讨论,这个地方就不再详细讲。我们将会仅指出重写系统的输入和输出都是查询树,也就是说,树中语义细节的表示形式和级别没有变化。重写可以被认为是宏拓展的一种形式。

计划器/优化器

计划器/优化器的任务是创建一个最佳的执行计划。一个给出的SQL查询(进一步的,一个查询树)可以用很多种方式被执行,每一个都能得到相同的结果。如果在计算上可行,查询优化器将会评估这些可能的执行计划,最终被选择出一个被期待运行最快的计划。

在一些情况中,检查每一个可能的计划将会花费大量的时间和内存空间。尤其是一个查询包含了大量的连接操作符。为了在一个合理的时间内去判断一个合适(不一定最优)的查询计划,当连接符的数量超过阈值的时候,PostgreSQL会使用Genetic Query Optimizer

计划器的搜索程序实际上工作时候的数据结构叫做路径paths,是一个计划的缩减表示,里面仅包含一个计划器需要做出决定的信息。在决定了代价最小的路径后,一个完整的计划树被构建然后被传递给执行系统。这代表期待的执行计划已经有了足够的信息让执行器去运行它。本章的剩下部分将会忽略路径和计划的不同。

生成可能的计划

计划/优化器通过扫描每一个查询中使用的每一个独立的关系来生成计划。可能的计划取决于每一个关系中可用的索引。总有一个可能是在一个关系上进行顺序扫描,因此,一个顺序扫描的计划总是被建立。假设一个关系上定义了一个索引,然后查询包含了限制关系relation.attribute OPR constant(即属性 操作符 常量值,例如 where a = 1),如果relation.attribute匹配一个B-tree索引的一个key,OPR是索引的操作符列表中的一个的话,另一个使用索引来扫描关系的计划也会被创建。如果有更多的索引存在而且查询中的限制也匹配索引中的key的话,更多的计划会被考虑。索引扫描计划也为那些具有ORDER BY条件相匹配的查询或者可能对合并连接有用的书讯生成计划。

如果一个查询要求连接一个或更多的关系,在找到所有扫描单个关系的计划之后,将会考虑连接关系的计划。有三个可用的策略

  1. nested loop join 对于左边扫面出的关系的每一行,都去扫描一次右边的关系。这个策略很容易实现但是非常耗时。(然而,如果右边的关系可以被用一个索引来扫描,这会是一个好的策略。可以将左侧关系中当前行的值作为右侧索引的扫描键)
  2. merge join 在连接关系开始时,将每一个连接关系按照连接的属性进行排序。然后,两个关系并行被扫描,匹配行被合并成一个连接行的形式。这种类型的连接是最优雅的,因为每一个关系只需要扫描一次。要求的排序可以被明确的指定一个排序步骤来实现,或者通过使用连接键上的索引以适当的顺序来扫描关系。
  3. hash join 右侧的关系第一次被扫描然后被加载到一个哈希表中,使用连接的属性作为一个hash值。然后左侧的关系被扫描,每一行对应的值用来生成哈希值,用来匹配表中的行。

当查询涉及两个以上的关系时,最终结果必须由一个树状的连接步骤建立,每个步骤有两个输入。计划器测试不同的可能的连接序列去发现代价最小的一个。

如果一个查询使用了比geqo_threshold少的关系,就会使用穷尽的搜索来找到最好的连接序列。计划器会优先考虑在where存在的对应关系的连接(比如 where rel1.attr1 = rel2.attr2)。没有其它任何选择的情况下,才考虑没有连接条件的连接组,就是指两个没有任何连接条件的关系。计划器为每个联接对生成所有可能的计划,并选择(估计)代价最小的一个

放超过geqo_threshold的值以后,连接序列通过启发式heuristics被决定。

最终的计划树由基本关系上的顺序或者索引扫描组成,加上所需的嵌套循环、合并、哈希连接节点,以及辅助的步骤,例如排序节点和聚合函数计算节点。大部分的计划节点类型有额外的能力去做选择(丢弃不符合条件的行)和投影(根据给定的列值计算出一个派生的列集,即在需要时对标量表达式进行评估)。计划器的一个责任是将FROM上的选择条件和计算要求的输出表达式附加到计划树的最合适的节点

执行器

执行器采用被计划器/优化器创建的计划,递归的处理并提取出要求的行的结果。这本质上是一种需求拉管道机制。每一次计划节点被调用,它必须传递一到多行,或者报告已经传递完行。

为了提供一个实际的例子,考虑顶部节点是MergeJoin节点。在进行任何合并之前,必须先获取两行(每个子计划一个)。所以执行器递归的调用它自己去处理子计划(从左树附加的子计划开始)。新的顶部节点(左侧子计划的顶部节点)假如是一个排序节点,需要再次递归以获取一个新的输入行。Sort的子节点获取是一个seqScan节点,代表从表中的实际读取。这个节点的执行导致执行器从表中读取一行数据返回给调用节点。Sort节点将会重复调用它的子节点直到获取所有需要排序的行。当所有的行被获取完后,Sort节点开始执行排序,最终返回它的第一条输出行,即按顺序排列的第一个。它保留剩下的行,以便在相应后续的请求时可以按排列顺序交付他们

MergeJoin以相同的方法从右计划中取出第一行。然后比较两行来看是否可以连接。如果可以的话,它就会给调用者返回一个连接行。在下一次调用(如果当前的两行不能够连接,那就立即),它进行到当前表的下一行或者另外一个表的下一行(取决于比较的结果),再次检查匹配。最终,其中的一个子计划执行完毕,MergeJoin节点返回NULL去指示不能再形成更多的连接行了

复杂的查询可以涉及到多个层次的计划节点,但是基本方法时一样的。每一个节点在被调用的时候,计算和返回它的下一个输出行。每一个节点也负责执行任何被附加在计划器上的选择或者投影表达式。

执行器机制被使用来计算四个基本的SQL查询:SELECT … INSERT、UPDATE和DELETE。对于SELECT,顶级的执行器只需要把计划树返回的每一行数据发送到客户端。INSERT … SELECT,UPDATE和DELETE是一种在特殊的叫做ModifyTable的顶级计划节点之下的SELECT。

SELECT … INSERT输出结果给ModifyTable去插入。对于UPDATE,计划器安排每一个计算出的包括所有更新的字段的值的行,加上原始目标行的TIP(tuple ID或者行ID),这个数据被传递给ModifyTable被使用来创建一个新的被更新的行,然后标记旧的行被删除。对于DELETE,计划实际只返回TID,然后ModifyTable简单的使用TID去查找每一个目标行,然后标记删除。

一个简单的INSERT…VALUES命令创建一个由单个Result节点组成的简单计划树,该树仅计算一个结果行,并将结果行发给ModifyResult去插入数据。