PostgreSQL概述

1.概述

图1-1数据库的整体架构

1.1查询优化的简介 数据库应用开发人员很难面面俱到地写出“极好的”语句，而查询优化器相对于数据库应用开发人员而言，具有一些独特的优势：

因此，查询优化器是提升查询效率非常重要的一个手段,通常数据库的查询优化方法分为两个层次：

逻辑优化是建立在关系代数基础上的优化，关系代数中有一些等价的逻辑变换规则，通过对关系代数表达式进行逻辑上的等价变换，可能会获得执行性能比较好的等式，这样就能提高查询的性能；而物理优化则是在建立物理执行路径的过程中进行优化，关系代数中虽然指定了两个关系如何进行连接操作，但是这时的连接操作符属于逻辑运算符，它没有指定以何种方式实现这种逻辑连接操作，而查询执行器是不“认识”关系代数中的逻辑连接操作的，我们需要生成多个物理连接路径来实现关系代数中的逻辑连接操作，并且根据查询执行器的执行步骤，建立代价计算模型，通过计算所有的物理连接路径的代价，从中选择出“最优”的路径。

1.2逻辑优化 1.2.1关系模型 关系数据库采用关系模型来描述数据，每个数据库是一个“关系”的集合，这个“关系”就是我们通常所谓的表，其形态类似于一个二维数组，我们称其中的一行为一个“N-元组”，通常简称为“元组”，其中的一列代表的是一个“属性”，所有属性的值最终组成了“域”。

在关系模型中，为了对关系、元组、属性等进行操作，定义了两种形式化的语言，分别是关系代数和关系演算。关系代数从逻辑的角度定义了对数据进行操作的方法，而关系演算则是描述性的，它准确地刻画需要获得的结果而不关心获得结果的过程。

关系代数的操作主要包含5个基本操作符，分别是选择（σ）、投影（Π）、笛卡儿积（×）、并集（∪）、差集（－），其中并集操作、差集操作、笛卡儿积操作来自集合论，选择和投影操作则是关系代数所特有的操作，这些基本操作是关系代数的基石，缺一不可，通过这些基本操作还可以衍生出一些其他比较重要的操作（可以用上述的5个基本操作将其表达出来），其中最重要的是交集操作（∩）和连接操作（⨝）。

另外，结合数据库的实际使用情况，通常数据库会对关系代数的逻辑运算符做一些扩展，例如外连接操作（左外连接⟕、右外连接⟖、全外连接⟗、半连接⋉、反半连接▷）、聚集和分组操作（γ）等，这些都不符合经典的关系代数理论，但是它们在数据库应用开发的过程中却经常被用到。

关系演算和关系代数不同，它从更高的层次来描述计算结果，完全不关心计算的过程，其中基于元组的关系演算可以称为元组关系演算，基于属性的关系演算称为域关系演算，元组关系演算包含的操作符如下：

关系演算的表达能力和关系代数是等价的，我们用元组关系演算的方式来实现选择、投影等几个关系代数表达式

SQL作为数据库的标准查询语言，它吸取了一些关系代数的逻辑操作符，但是放弃了关系代数中“过程化”的特点，同时它更多地采用了关系演算的方法，一个SQL语句通常是对执行结果的描述，因此我们说SQL语言是一种介于关系代数和关系演算之间的描述性语言。

SQL语言是描述性语言这种特性导致了查询优化“大有可为”，因为它只规定了“WHAT”，而没有规定“HOW”，不同的获取结果的方法代价相差可能极大，因此数据库的查询优化就变得极为重要了。

1.3物理优化 基于代价的查询优化（Cost-based Optimizer，简称CBO）也可以称为代价优化、物理优化，其主要流程是枚举各种待选的物理查询路径，并且根据上下文信息计算这些待选路径的代价，进而选择出代价最小的路径。我们在关系代数表达式中已经指定了两个表要做连接，这种连接操作是逻辑操作符，它包括内连接、外连接、半连接等，而查询执行器并无法直接执行这些逻辑操作符，查询执行器只能认识物理连接路径，物理连接路径的作用就是指示查询执行器以何种方式实现逻辑操作符。

数据库无法从感性的角度来衡量哪条物理路径的代价低，因此它需要构建一个量化的模型，这个代价模型需要从两个方面来衡量路径的代价：

执行代价=IO代价+CPU代价

产生IO代价的原因是因为数据是保存在磁盘上的，要对数据进行处理，需要将数据从磁盘加载到主存，另外在数据需要排序、建立hash表、物化的时候还可能需要将处理后的数据写入磁盘，这些都是IO代价，数据库要计算一个查询的IO代价存在一些困难：

产生CPU代价的原因是选择、投影、连接都需要进行大量的运算，尤其是像聚集函数这样CPU密集型的操作符，而CPU代价的计算和IO代价一样也面临一些问题：

要想计算物理路径的代价，数据库还需要对数据的分布情况有一个了解，因为无论是IO代价还是CPU代价，都是建立在对数据处理的基础之上的，数据的分布情况也会从很大程度上对代价产生影响：

总之，数据库很难给出一个“准确”的代价模型来描述所有的情况，计算代价的目的是在物理路径之间进行挑选，它只需要能够用于比较物理路径的优劣就够了，虽然大部分数据库都采用了IO代价和CPU代价来衡量物理路径的代价，但具体的实现细节则千差万别，一个数据库的代价模型需要不断地“修炼”才能接近完美。

1.3.1物理优化的四个法宝 关系的本身可以视为一个集合或者包，这种数据结构对数据的分布没有设定，为了提升计算的性能，我们需要借助一些数据结构或算法来对数据的分布做一些预处理，在物理优化的过程中有4个非常重要的数据结构或算法贯穿其中，下面简单介绍一下这些方法。

1.3.2物理路径的生成过程 数据库中的物理路径大体上可以分为扫描路径和连接路径，扫描路径是针对单个关系的，它可以用来实现关系代数中的选择和投影，而连接路径对应的是两个表做连接操作，因此它可以用来实现关系代数中的笛卡儿积。

1.3.2.1物理路径的分类

扫描路径通常是执行计划中的叶子节点，也就是在最底层对表进行扫描的节点（也可能扫描节点的下层又是一个子执行计划），扫描路径就是为连接路径做准备的，扫描出来的数据就可以给连接路径来实现连接操作了。

综上所述，我们对物理路径有了基本的了解，物理扫描路径主要有顺序扫描路径、（快速）索引扫描路径、位图扫描路径、TID扫描路径等，而物理连接路径主要有Nestlooped Join、Hash Join和Merge Join，这些路径的生成都会或多或少地使用到物理优化的4个“法宝”，因此读者可以将它们结合在一起来理解物理优化路径生成的过程。

1.3.2.2路径搜索的方法 物理路径的种类越多，挑选最优路径的难度就越大，例如有3个表要做连接操作，每个表上有3个扫描路径，那么扫描路径的组合就有27种可能，由于表之间的连接顺序可以交换，3个表可能产生的连接顺序有12种情况，每个连接路径可能的物理连接路径是9种情况，那么最终要生成3个表的连接路径“树”，共需要计算27×12×9=2916种情况。然后从中选出最优的那个路径“树”，如果再增加新的表参与连接操作，那么物理执行计划的解空间就会以几何级数的方式不断地增长，因此物理路径的搜索方法就非常重要了，通常物理路径的搜索有以下几种方法：

PostgreSQL数据库采用了其中的两种方法，一种是在表的数量比较少的情况下采用基于System-R系统的动态规划方法，另一种是在表的数量比较多的情况下启用遗传算法。对自顶向下的方法感兴趣的读者可以参考Pivotal公司开源的查询优化器ORCA的实现方法。

1.4小结 关系数据库的查询优化通常分为逻辑优化和物理优化。逻辑优化是基于关系代数的等价的逻辑变换，关系代数中有大量的逻辑等价规则，可以利用这些规则尝试将选择操作和投影操作尽量下推，缩小查询中的中间结果以提高执行效率；物理优化则是通过代价估算的方式挑选代价比较低的物理路径，根据物理路径的性质又可以分成扫描路径和连接路径，在生成物理路径的过程中通常可以选择动态规划方法等最优路径算法来获得对物理路径进行搜索。

​