PostgreSQL7.0手册-开发者手册 -61. PostgreSQL 内部概貌

第六十一章.　PostgreSQL　内部概貌
内容　
查询的过程　
联接是如何建立起来的　
分析器阶段　
Postgres　规则系统　
规划器/优化器　
执行器　
作者：本章最初是做为　Simkovics,　1998　的一部分出现的，它是　Stefan　Simkovics　在　维也纳理工大学准备的硕士论文，是由　O.Univ.Prof.Dr.　Georg　Gottlob　和　Univ.Ass.　Mag.　Katrin　Seyr　指导的。
本章给出了　Postgres　后端服务器的内部情况的一个概貌。在阅读完毕下面的章节后，你应该对如何处理查询有一个概念了。不过别指望我们在这里有详细的描述（我想，要对Postgres　里面所有的数据结构和函数都做这样的详细描述可能要超过　1000　页的内容！）。本章只是试图帮助我们了解在后端里面从受到查询到发出结果之间的通常的控制和数据的流动。　
查询的过程
下面是一个简短的描述一个查询从开始到得到结果要经过的阶段。　
首先必须先建立起从应用程序到　Postgres　服务器的联接。应用程序想服务器发送查询然后接收从服务器收到的结果。　
分析阶段（parser　stage）检查从应用程序（客户端）发送过来的查询，核对语法并创建一个查询树（query　tree）。　

重写系统（rewrite　system）接收分析阶段来的查询树并且搜索任意应用到查询树上的规则（rules）（存储在系统表里）并根据给出的规则体（rule　bodies）进行转换。重写系统的一个应用在视图（views）的实现里给出了。　

当一个查询访问一个视图时（也就是说，一个虚拟表（virtual　table）），重写系统改写用户的查询，使之成为一个访问带有视图定义（view　definition）的基本表（base　tables）的查询。　

规划器/优化器（planner/optimizer）接收（改写的）查询树然后创建一个查询规划（queryplan），这个查询规划是执行器（executor）的输入。　

它（规划器/优化器）首先创建所有得出相同结果的可能的　路径（paths）。例如，如果待扫描的关系上有一个索引，那么扫描的路径就有两个。一个可能是简单的顺序查找，而另一个可能就是使用索引的那个。下一步是计算出每个索引执行的开销，并且选择和返回开销最少的那个。　

执行器递归地走过规划树（plan　tree）并且在这个过程中检索规划所代表的记录。执行器在对关系进行扫描时使用存储系统（storage　system），进行排序（sorts）和联接（joins），计算条件（qualifications）并且最终交回生成的记录。

在随后的章节里，我们将对上面的每一个步骤进行更详细的讨论，以便让我们对Postgres　的内部控制和数据结构有一个更准确的理解。

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

联接是如何建立起来的
Postgres　是用一个简单的"每用户一进程"的client/server　模型实现的。在这种模式里一个客户端进程只是与一个服务器进程联接。因为我们不知道具体要建立多少个联接，所以我们不得不利用一个主进程　在每次联接请求时派生出一个新的服务器进程来。这个主进程叫做　postmaster，它监听着一个特定的　TCP/IP　端口等待进来的联接。每当检测到一个联接请求时，postmaster　进程派生出一个新的叫　postgres　的服务器进程。服务器任务（postgres　进程）相互之间使用信号灯和共享内存进行通讯，以确保在并行的数据访问过程中的数据完整性。图　\ref{connection}　显示了主进程　postmaster，服务器进程　postgres　和客户端应用之间的相互关系。　
客户端进程要么是　psql　前端（用于交互的　SQL　查询）或者是任意用　libpg　库实现的用户应用。请注意用　ecpg（Postgres　用于　C　的嵌入　SQL　预处理器）实现的应用同样也使用这个库。　

一旦建立起来一个联接，客户端进程就可以向后端服务器进程发送查询了。查询是通过纯文本传输的，也就是说在前端（客户端）不做任何分析处理。服务器分析查询，创建执行规划，执行该规划并且通过已经建立起来的联接把检索出来的记录返回给客户端。


--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

分析器阶段
分析器阶段（　parser　stage　）包含两个部分：　
在　gram.y　和　scan.l　里定义的分析器是使用　Unix　工具　yacc　和　lex　制作的。　
转换处理对分析器返回的数据结构进行修改和增补。

分析器
分析器必须检查（以纯　ASCII　文本方式到来的）查询字串的语法。如果语法正确，则创建一个分析树并将之传回，否则，返回一个错误。在这个实现里我们使用了著名的　Unix　工具　lex　和　yacc。　
lexer　（词法）在文件　scan.l　里定义，负责识别标识符，SQL　关键字等。对于发现的每个关键字或者标识符都会生成一个记号并且传递给分析器。　

分析器在文件　gram.y　里定义并且包含一套语法规则和触发规则时执行的动作。动作代码（实际上是　C　代码）用语建立分析树。　

文件　scan.l　用　lex　转换成　C　源文件而　gram.y　用　yacc　转换成　gram.c。在完成这些转换后，一个通用的　C　编译器可以用于创建分析器。千万不要对生成的　C　源文件做修改，因为下一次调用　lex　或　yacc　会把它们覆盖。　

注意：上面提到的转换和编译是使用跟随Postgres　发布的　makefiles　自动完成的。
对　yacc　或者　gram.y　里的语法规则的详细描述超出本文的范围。有很多关于lex　和　yacc　的书籍和文档。你在开始研究　gram.y　里给出的语法之前，你应该对　yacc　很熟悉，否则你是看不懂那里面的内容，理解不了发生了什么事情的。　
为了更好地理解处理一个查询时　Postgres　里使用的数据结构，我们用一个简单的例子演示在每个阶段数据结构所做的改变。　

例　54-1.　一个简单的选择（Select）　

这个例子包含下面的简单的查询，这个例子将会在本章剩余各节的所有描述和图示里出现。该查询假设在Supplier　Database　数据库里的表已经定义了。　

select　s.sname,　se.pno
　　　　from　supplier　s,　sells　se
　　　　where　s.sno　>　2　and　s.sno　=　se.sno;
图　\ref{parsetree}　显示了　gram.y　里的语法规则和动作为查询　一个简单的　Select　这个例子包含下面的简单查询，该查询将被用于随后各个阶段的各种描述和图片．这个查询假设在供应商数据库里的表已经定义了．　select　s.sname,　se.pno　from　supplier　s,　sells　se　where　s.sno　>　2　and　s.sno　=　se.sno;　构建的分析树（不带用于　where　子句的操作符树，它在图\ref{where_clause}里显示，因为在一幅图里没有足够的位置把两部分的数据结构都放进去）。　
树的顶端节点是　SelectStmt　节点。对每个在　SQL　查询的　from子句里出现的元素创建一个　RangeVar　节点，存放　alias（别名）的名称和一个指向一个存放关系名称的RelExpr　节点的指针。所有　RangeVar　节点都收集到一个列表里，然后附加到　SelectStmt　节点的　fromClause　字段上。　

对于　SQL　查询里面的　select列表　里出现的每个元素都创建一个　ResTarget　节点，存放一个指向　Attr　节点的指针。Attr　节点存放元素的关系名称和一个指向存放着字段名称的　Value　节点的指针。所有　ResTarget　节点都收集到一个列表里，然后链接到　SelectStmt　节点的　targetList　字段里。　

图　\ref{where_clause}　显示了为例子　　select　s.sname,　se.pno　from　supplier　s,　sells　se　where　s.sno　>　2　and　s.sno　=　se.sno;　里　SQL　查询的　where　子句构建的操作符树，这个操作符树附加到了　SelectStmt　节点的字段　qual　上。操作符树的顶端节点是一个代表　AND　操作的　A_Expr　节点。这个节点有两个后继节点，　lexpr　和　rexpr　分别指向两个子树。附加到　lexpr　的子树代表条件　s.sno　>　2　而附加到　rexpr　的子树代表　s.sno　=　se.sno。为每个字段创建一个　Attr　节点，存放关系名和一个指向存放着字段名的　Value　节点的指针。为在查询里出现的常量条款创建一个　Const　节点，存放常量值。

转换处理
转换处理把分析器传递过来的分析树作为输入，然后递归地处理它。如果碰到一个　SelectStmt　节点，就把它转换成一个　Query　节点，这个节点将是新数据结构的最顶端节点。图　\ref{transformed}　显示了转换过后的数据结构（转换过后的　where　子句在图　\ref{transformed_where}　里给出，因为一幅图里放不下所有的部分）。　
现在进行一个检查，看看　FROM　子句里面的关系名是否被系统所知。为每个系统表里面出现的关系名创建一个RTE　节点，该节点包含关系名，别名和关系　id。从现在开始，关系　id　（标识）用于指代查询里出现的关系。所有RTE　节点都收集到范围表项目列表（range　table　entry　list）里，然后该列表在链接到　Query　节点的　rtable　字段上。如果查询里面有一个不为系统所知的关系被检测到，那么将返回一个错误然后查询处理将退出。　

下一步是检查所用的字段名是否包含在查询给出的关系里。为找到的每个字段创建一个TLE　节点，保存一个指向　Resdom　节点的（该节点里保存列名称）的指针和一个指向　VAR　节点的指针。在　VAR　节点里有两个重要的数字。数据域　varno　包含当前字段的关系在上面创建的范围表项目列表里面的位置。数据域　varattno　给出该字段在关系里的位置。如果无法找到一个字段的名称，则返回一个错误而且这个正在处理的查询将退出。　


--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

Postgres　规则系统
Postgres　维持一个强大的规则系统，用以阐述视图和不明确的视图更新。最初Postgres规则系统包含两个实现：　
第一个能用的规则系统采用记录级别处理，是在执行器深层实现的。每次访问一条独立的记录时都调用规则系统。这个实现在1995年被删除了，那时Postgres　项目的最后一个官方版本正转换成　Postgres95。　
第二个规则系统的实现从技术角度来说叫查询重写。重写系统是一个存在于分析器阶段和规划器/优化器之间的一个模块。这个技术实现仍然存在。
要获取关于　Postgres　系统里规则的创建和语法的信息，请参考　PostgreSQL　用户手册。　
重写系统
重写系统是一个存在于分析器阶段和规划器/优化器之间的一个模块。它处理分析器阶段传回的分析树（该分析树代表用户查询），如果存在一条必须应用的规则的话，这个模块把分析树重写成一个变化了的形式。　
实现视图的技巧
现在我们勾画一下查询重写系统的算法。为了更好的说明问题，我们把用规则系统实现视图作为一个例子。　
先给出下面规则：　

　　create　rule　view_rule
　　as　on　select　
　　to　test_view
　　do　instead
　　　　　select　s.sname,　p.pname
　　　　　from　supplier　s,　sells　se,　part　p
　　　　　where　s.sno　=　se.sno　and
　　　　　　　　　　　p.pno　=　se.pno;
当检测到对关系　test_view　的　select　时，就会触发上面给出的规则。这时这句选择语句将执行规则里的动作部分，而不是从　test_view　里选择记录。　
给出下面的用户对　test_view　的查询：　

　　select　sname　
　　from　test_view
　　where　sname　<>　'Smith';
这里是当一个用户查询作用于　test_view　时，查询重写系统执行的一系列步骤。（下面的列表只是一个非常不正式的关于查询重写的算法的描述，只是用于了解基础。更多的详细描述请参考　Stonebraker　et　al,　1989）。　
　　
test_view　重写　
获取在规则的动作部分给出的查询。
调整其目标列表以便与用户查询给出的字段的数目和顺序相匹配。　
把用户查询的　where　子句里的条件部分追加到规则动作部分的查询的条件上。

给出上面定义的规则后，用户查询将被重写为下面的形式（请注意：重写动作是对从分析器阶段传回的用户查询的内部形式操作的，不过所产生的新的数据结构将代表下面的查询）：　
　　select　s.sname
　　from　supplier　s,　sells　se,　part　p
　　where　s.sno　=　se.sno　and
　　　　　　　　p.pno　=　se.pno　and
　　　　　　　　s.sname　<>　'Smith';

--------------------------------------------------------------------------------

--------------------------------------------------------------------------------

规划器/优化器
规划器/优化器的任务是创建一个优化了的执行规划。它首先合并所有对出现在查询里的关系的扫描和联合的方法。这样创建的所有的路径都导致相同的结果，而优化器的任务就是计算每个路径的开销并且找出开销最小的那条路径。　
生成可能的规划
规划器/优化器以查询里出现的关系上定义的索引的类型为基础，判断应该生成哪些规划。对一个关系总是可以进行一次顺序查找，所以总是会创建只使用顺序查找的规划。假设一个关系上定义着一个索引（例如　B-tree　索引），并且一条查询包含约束　relation.attribute　OPR　constant。如果　relation.attribute　碰巧匹配　B-tree　索引的关键字并且　OPR　又不是　'<>'，则将会创建另一个使用　B-tree　索引扫描该关系的规划。如果还有别的索引，而且查询里面的约束又和那个索引的关键字匹配，则还会生成更多的规划。　
在找完扫描一个关系的所有可能的规划后，接着创建联接各个关系的规划。规划器/优化器认为只有在每两个关系之间存在联接，对应地在　where　条件里存在一条　join　子句（也就是说，存在象　where　rel1.attr1=rel2.attr2　这样的约束）。规划器/优化器为它们认为可能的所有的联接关系对生成一个规划。有三种可能的联接策略：　

嵌套的反复联接（nested　iteration　join）：对左边的关系里面找到的每条记录都对右边关系进行一次扫描。这个策略容易实现，但是可能会很耗费时间。　
融合排序联接（merge　sort　join）：在联接开始之前，每个关系都对联接字段进行排序。然后两个关系融合到一起，认为两个关系都对联接字段进行了排序。这种联合更有吸引力，因为每个关系都只用扫描一次。　

哈希联接（hash　join）：右边的关系首先对它的联接字段进行哈希运算。然后扫描左边的关系，并将找到的每条记录的合适的值作为哈希键字用以定位右边关系里的记录。

规划的数据结构
我们在这里对规划里出现的节点做一些简单描述。图　\ref{plan}　显示了为例子　\ref{simple_select}　里的查询生成的规划。　
规划的顶端节点是一个　MergeJoin　节点，它有两个下级节点，一个附加在域　lefttree　上，而另一个附加在域　righttree　上。每个子节点代表一个联接的关系。如上面所述，一个融合联接要求每个关系先被排序。这就是为什么我们在每个子规划里有一个　Sort　节点的原因。查询里附加的条件（s.sno　>　2）被尽可能地向下推，并且附加在对应的子规划的叶节点　SeqScan　的　qpqual　域上。　

附加在节点　MergeJoin　的域　mergeclauses　的列表包含关于联接属性的信息。　mergeclauses　列表里（还有　targetlist　里）出现的　VAR　节点的数据域　varno　的值　65000　和　65001　意味着不考虑当前节点的记录，而是使用下一"更深"节点（也就是说，子规划的顶端节点）的记录。　

请注意图　\ref{plan}　里的每个　Sort　和　SeqScan　节点都有一个　targetlist，但因为空间不够，只有　MergeJoin　节点的画出来了。　

规划器/优化器执行的另一个任务是填补　Expr　和　Oper　节点里的操作符id。如上所述，Postgres　支持广范围的不同的数据类型，甚至可以使用用户定义类型。为了能够维护这些数目巨大的函数和操作符，有必要把它们存放在系统表里。每个函数和操作符有一个唯一的操作符　id。根据在资格条件等地方使用的字段的类型，必须选用合适的操作符　id。


--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

执行器
执行器接收由规划器/优化器传递过来的规划，然后开始处理顶端节点。在我们给出的例子里面（在例子　\ref{simple_select}　里给出的查询），顶端节点是一个　MergeJoin　节点。　
在进行任何融合之前，首先要抓取两条记录（从每个子规划里抓一条）。所以执行器递归地调用它自己以处理子规划（它从附加在　lefttree　上的子规划开始）。新的顶端节点（左边子规划的顶端节点）是一个　SeqScan　节点，同样必须先抓取一条记录然后才能处理节点本身。执行器再次递归地调用自身，处理附加在　lefttree　的　SeqScan　节点上的子规划。　

现在新的顶端节点是一个　Sort　节点。因此，要对整个关系进行排序。当第一次访问　Sort　节点时，执行器开始从　Sort　节点的子查询里抓取记录并把它们在一个临时关系里面（在内存或文件中）排序。（对　Sort　节点的进一步检查将总是从排好序的临时关系里返回一条记录。）　

每当处理　Sort　节点需要新的记录时，都会为作为子规划附加上来的　SeqScan　节点递归地调用执行器。然后对该关系（在内部通过数据域　scanrelid　给出的值引用）进行扫描，检索下一条记录。如果记录满足附加在　qpqual　上的条件树则将其返回，否则抓取下一条记录知道条件被满足。如果处理到了关系的最后一条记录，则返回一个　NULL　指针。　

在　MergeJoin　的　lefttree　返回一条记录后，用同样方法处理　righttree。如果两条记录都存在了，执行器就处理　MergeJoin　节点。每当有一个子规划需要一条新的记录时，都进行一次执行器的递归调用以获取记录。如果可以创建一条联合的记录，那么就把这条记录返回并且完成一次完整的规划树的处理。　

现在，上面描述的步骤对每条记录执行一次，直到对　MergeJoin　节点的处理返回一个　NULL　指针，表示我们已经处理完毕时为止。


------------------------------------------------------------------------------