本文共 7056 字，大约阅读时间需要 23 分钟。

通过大明和小明的对话，相信读者朋友对逻辑优化的部分已经有了一个简单的了解，逻辑优化也叫基于规则的优化，这种优化方式比较呆板、不够灵活，就是按照定义好的规则硬性地进行等价变换，于是就催生了新的优化方法——物理优化，物理优化又叫基于代价的优化，今天我们再次跟着小明、大明和牛二哥一起来探讨一下 PostgreSQL 优化器是怎么计算路径代价的，又是怎么筛选路径的。对这些内容已经了如指掌的朋友可以跳过这个导读，直接开始后面的内容学习。

统计信息和选择率

“咚咚咚……”门外传来了敲门声，大明打开门一看，原来是同事牛二哥，牛二哥是专门从事数据库查询优化开发的码农，也有十几年从业经验了。大明感到非常 Happy，因为这两天给小明讲查询优化器讲得有些吃力，今天牛二哥来了正好可以帮上忙：“牛二同志，我弟弟小明最近学校要做数据库原理实践，总来问我优化器的问题，可我对优化器也是一知半解，这下你来了可以帮帮忙不？”

牛二哥痛快地说：“这难不倒我，随时都可以讲。”

小明对牛二哥早有耳闻，接到大明电话后速速赶到，见面不久便吐起了苦水：“我最近正在查看基于代价的优化，感觉付出了很多代价，但收获甚微，期望今天能得到牛二哥的指导。”

牛二哥说：“说到代价，我觉得有个东西是绕不过去的，就是统计信息和选择率。PostgreSQL 的物理优化需要计算各种物理路径的代价，而代价估算的过程严重依赖于数据库的统计信息。统计信息是否能准确地描述表中的数据分布情况是决定代价准确性的重要条件之一。”

小明说：“大明和我说过，数据库有很多物理路径，这些物理路径也叫物理算子。和逻辑算子不同，物理算子是查询执行器的执行方法，我们只需要计算物理算子每个步骤的代价，汇总起来就是路径的代价了，那要统计信息有什么用呢？”

牛二哥说：“是的，我们就是要计算一个物理算子的代价，但是物理算子的计算量并不是一成不变的。”说着他从旁边的书桌上拿来纸和笔，写了两个 SQL 语句。

SELECT A+B FROM TEST_A WHERE A > 1;SELECT A+B FROM TEST_A WHERE A > 100000000;

然后说：“你看，这两个语句可以用同样的物理算子来完成，但是它们的计算量一样吗？”

小明心想：A > 1 和 A > 1000000000 都是过滤条件，经过过滤之后，它们产生的数据量就不同了，这样投影中的 A + B 的计算次数就不同了，所以它们的代价应该是不同的，那它和统计信息有什么关系呢？小明灵光一闪，马上说：“我知道了，我在计算物理算子的代价的时候，要知道 A > 1 之后还剩下多少数据或者 A > 1000000000 之后还剩下多少数据，如果我们提前对表上的数据内容做了统计，剩下多少数据就不难计算了，所以必须要有统计信息。”

牛二哥点了点头说：“嗯，通过统计信息，代价估算系统就可以了解一个表有多少行数据、用了多少个数据页面、某个值出现的频率等，然后就能根据这些信息计算出一个约束条件能过滤掉多少数据，这种约束条件过滤出的数据占总数据量的比例称为选择率。”

统计信息是什么形式

小明追问道：“那么统计信息是什么形式的呢？”

牛二哥挠挠头说：“这个还真是有点麻烦，我们说常用的统计信息的形式就是 distinct 率、NULL 值率、高频值、直方图、相关系数这些，它们分别有不同的作用。比如说 distinct 率，你可以获知某一列有多少个独立值，这种信息对于像性别这种列就显得特别有用。NULL 值率呢，在统计的过程中，NULL 值是不好处理的，因此把它独立出来，形成 NULL 值率，这样在高频值、直方图这些形式中就不用考虑 NULL 值的情况了。高频值属于奇异值，顾名思义，就是出现得比较多的一些列值。去掉了 NULL 值，再去掉高频值，剩下的值可以用来做一个等频的直方图。”

大明看小明有点跟不上，过来说：“统计信息嘛，主要的还是高频值、直方图和相关系数，实际上我建议还是不要纠结于统计信息有哪些形式，只要知道它是用来算代价的就可以了。”

牛二哥对大明说：“这怎么可以，我还没有说统计信息是如何生成的呢！比如它通过了两阶段采样，然后对样本进行统计时使用的统计方法，哪些值可以作为高频值，直方图有几个桶，相关系数是怎么计算的，相关系数在计算索引扫描路径代价的时候怎么用的……而且我和你说，PostgreSQL 还出了基于多列的扩展统计信息，多列统计信息分成了哪些类型，分别是什么含义，各自是怎么计算的，还有选择率是怎么结合统计信息计算的，这些我还没说呢……”

大明忍不住说：“像你这样讲优化器，岂不是要出一本书了？”

牛二哥做痛苦状：“那好吧，统计信息我们就说到这里，但是它确实是代价计算的基石。小明同学，你理解了它的作用就可以了。”

大明继续神秘地说：“实际上统计信息往往也不准，你想想本来就是采样的结果嘛，样本是否显著压根就不好说，而且随着应用程序对表的更新，统计信息可能更新不及时，那就更会出现偏差。更严重的是，如果我们遇到 a > b 这样的约束条件，使用统计信息计算选择率也很不好计算，即使算出来，也可能不准。”

牛二哥说：“是的，统计信息确实也有不准确的问题。我听说有个数据库用户，他家后院出了一口泉水，他爸爸觉得是吉兆，去找风水大师看。风水大师掐指一算说：你儿子每次遇到数据库性能慢就知道更新统计信息，可是统计信息太水了，都从你家后院冒出来了。”

三个人顿时笑做一团。

关于物理路径

玩笑过后，小明说：“不如给我说说物理路径吧，代价算来算去，最终还是为了物理路径计算代价嘛。大明和我说过它大体分成扫描路径和连接路径，我查过一些说明，知道扫描路径有顺序扫描路径、索引扫描路径、位图扫描路径等；而连接路径通常有嵌套循环连接路径、哈希连接路径、归并连接路径，另外还有一些其他的路径，比如排序路径、物化路径等。”

牛二哥说：“是的，我们就来说说这些路径的含义吧。如果要获得一个表中的数据，最基础的方法就是将表中的所有的数据都遍历一遍，从中挑选出符合条件的数据，这种方式就是顺序扫描路径。顺序扫描路径的优点是具有广泛的适用性，各种表都可以用这种方法，缺点自然是代价通常比较高，因为要把所有的数据都遍历一遍。”大明同时在纸上画了个图，说：“这个图大概就是顺序扫描路径。”

牛二哥则继续说：“将数据做一些预处理，比如建立一个索引，如果要想获得一个表的数据，可以通过扫描索引获得所需数据的‘地址’，然后通过地址将需要的数据获取出来。尤其是在选择操作带有约束条件的情况下，在索引和约束条件共同的作用下，表中有些数据就不用再遍历了，因为通过索引就很容易知道这些数据是不符合约束条件的。更有甚者，因为索引上也保存了数据，它的数据和关系中的数据是一致的，因此如果索引上的数据就能满足要求，只需要扫描索引就可以获得所需数据了。也就是说在扫描路径中还可以有索引扫描路径和快速索引扫描路径两种方式。”

大明则继续为牛二哥“捧哏”，在纸上画出了索引扫描和快速索引扫描的图。

索引扫描随机读的问题

小明看到图上写了“随机读”三个字，问道：“我看这个索引扫描有随机读的问题，这个问题能否解决掉呢？也就是说既利用了索引，还避免了随机读的问题，有这样的办法吗？”

牛二哥说：“索引扫描路径确实带来随机读的问题，原因是索引中记录的是数据元组的地址，索引扫描是通过扫描索引获得元组地址，然后通过元组地址访问数据，索引中保存的“有序”的地址，到数据中就可能是随机的了。位图扫描就能解决这个问题，它通过位图将地址保存起来，把地址收集起来之后，然后让地址变得有序，这样就通过中间的位图把随机读消解掉了。”大明则继续在纸上画出了位图扫描的示意图。

大明补充说道：“扫描过程中还会结合一些特殊的情况，有一些非常高效的扫描路径，比如 TID 扫描路径。TID 实际上是元组在磁盘上的存储地址，我们能够根据 TID 直接就获得元组，这样查询效率就非常高了。”

牛二哥点了点头继续说：“扫描路径通常是执行计划中的叶子结点，也就是在最底层对表进行扫描的结点。扫描路径就是为连接路径做准备的，扫描出来的数据就可以给连接路径来实现连接操作了。”

大明一边在纸上画一边说：“要对两个关系做连接，受笛卡尔积的启发，可以用一个算法复杂度是 O(mn) 的方法来实现，我们叫它嵌套循环连接（Nested Loop Join） 方法。这种方法虽然复杂度比较高，但是和顺序扫描一样，胜在具有普适性。”

牛二哥说：“嵌套循环连接这种方法的复杂度比较高，看上去没什么意义，但是如果嵌套循环连接的内表的路径是一个索引扫描路径，那么算法的复杂度就会降下来。索引扫描的算法复杂度是 O(logn)，因此如果嵌套循环连接的内表是一个索引扫描，它整体的算法复杂度就变成了 O(mlogn)，看上去这样也是可以接受的。”

哈希连接

小明点了点头说：“嗯，索引实际上是对数据做了一些预处理，我想如果哈希连接（Hash Join）方法就是将内表做一个哈希表，这样也等于将内表的数据做了预处理，也能方便外表的元组在里面探测吧？”

牛二哥点了点头说：“假设哈希表有 N 个桶，内表数据均匀地分布在各个桶中，那么哈希连接的时间复杂度就是 O(m * n /N)，当然，这里我们没有考虑上建立哈希表的代价。”

大明则在纸上画出了哈希连接的示意图，并补充道：“哈希连接通常只能用来做等值判断。”

归并连接

牛二哥继续说：“如果将两个表先排序，那么就可以引入第三种连接方式：归并连接（Merge Join）。这种连接方式的代价主要浪费在排序上。如果两个关系的数据量都比较小，那么排序的代价是可控的，归并连接就是适用的。另外如果关系上有有序的索引，那就可以不用单独排序了，这样也比较适用归并连接。你看我画的这个归并连接的示意图，外表是需要排序的，而内表则借用了原有的索引的顺序，消除了排序的时间，降低了物理路径的代价。”

“这些路径属于 SPJ 路径，在 PostgreSQL 的优化器中，通常会先生成 SPJ 的路径，然后在这基础上再叠加 Non-SPJ 的路径，比如说聚集操作、排序操作、limit 操作、分组操作……”牛二哥继续补充道。

关于代价的计算

小明说：“可是算来算去，物理路径的代价还是有选不准的时候啊。”

牛二哥说：“最优路径选得不准是谁的原因？那就是代价模型不行啊。代价模型不行赖谁？那就是程序员没建好啊，所以要怪就怪到程序员自己头上。”

小明问道：“可是我看 PostgreSQL 的代价计算已经很复杂了啊。”

“但数据库的周边环境更复杂啊。你想想，在实际应用中，数据库用户的配置硬件环境千差万别，CPU 的频率、主存的大小和磁盘介质的性质都会影响执行计划在实际执行时的效率。”牛二哥说。

大明接过来继续说道：“虽然在代价估算的过程中，我们无法获得‘绝对真实’的代价，但是‘绝对真实’的代价也是不必要的。因为我们只是想从多个路径（Path）中找到一个代价最小的路径，只要这些路径的代价是可以‘相互比较’的就可以了。因此可以设定一个‘相对’的代价的单位 1，同一个查询中所有的物理路径都基于这个‘相对’的单位 1 来计算的代价，这样计算出来的代价就是可以比较的，也就能用来对路径进行挑选了。”

牛二哥接着说：“PostgreSQL 采用顺序读写一个页面的 IO 代价作为单位 1，而把随机 IO 定为了顺序 IO 的 4 倍。”

小明说：“我知道，这个我查过相关的书。首先，目前的存储介质很大部分仍然是机械硬盘，机械硬盘的磁头在获得数据库的时候需要付出寻道时间。如果要读写的是一串在磁盘上连续的数据，就可以节省寻道时间，提高 IO 性能。而如果随机读写磁盘上任意扇区的数据，那么会有大量的时间浪费在寻道上。其次，大部分磁盘本身带有缓存，这就形成了主存→磁盘缓存→磁盘的三级结构。在将磁盘的内容加载到内存的时候，考虑到磁盘的 IO 性能，磁盘会进行数据的预读，把预读到的数据保存在磁盘的缓存中。也就是说如果用户只打算从磁盘读取 100 个字节的数据，那么磁盘可能会连续地读取磁盘中的 512 字节（不同的磁盘预读的数量可能不同）并将其保存到磁盘缓存。如果下一次是顺序读取 100 个字节之后的内容，那么预读的 512 字节的数据就会发挥作用，性能会大大增加。而如果读取的内容超出了 512 字节的范围，那么预读的数据就没有发挥作用，磁盘的 IO 性能就会下降。”说完小明得意地说：“怎么样，我说得对吧？”

牛二哥说：“你说得对，目前 PostgreSQL 的查询优化大量考虑了随机 IO 和顺序 IO 所带来的性能差别，在这方面做了不少优化。但是现在的磁盘技术越来越发达了，以后随机 IO 和顺序 IO 是不是还差这么多，就值得商榷了。”

代价基准单位

“那到底还有哪些代价基准单位呢？”小明继续问道。

大明回答：“基于磁盘 IO 的代价单位当然就是和 Page 有关的了，也就是说我们刚才说的顺序 IO 和随机 IO 都属于 IO 方面的基准代价。让牛二哥给你介绍一下 CPU 方面的代价基准单位吧。”

牛二哥说：“CPU 方面的基准单位有哪些呢？比如说我们通过 IO 把磁盘页面读到了缓存，但我们要处理的是元组啊，所以还需要把元组从页面里解出来，还要处理元组，这部分主要消耗的是 CPU，所以会有一个元组处理的代价基准单位。另外，我们在投影、约束条件里有大量的表达式，这些表达式求解也主要消耗 CPU 资源，所以还有一个表达式代价的基准单位。”

牛二哥继续说道：“现在 PostgreSQL 增加了很多并行路径，因此它也产生了通信代价，这个也需要计算的。”

小明听后说：“那我们就能得到一个这样的公式。”说着在纸上写了一个公式：

总代价 = CPU 代价 + IO 代价 + 通信代价

牛二哥笑道：“总结得不错，这样就可以计算每种物理路径的代价，就可以对路径进行筛选了，最后挑选出来的路径就是最优路径。”

关于最优路径

小明、大明和牛二哥在外卖 App 里搜索附近的饭店，大明突然感叹道：“看，这就是蓝海，我们可以创业搞一个 AI 点评，只推荐最优的饭店，我准确地找到了吃货们的痛点，这里面隐含着很大的商机啊！”

牛二哥瞥了他一眼说：“AI 推荐当然好，可是要推荐得准才行啊。一个人一个口味，你这个需求太‘智能’了，我估计不好弄。”

小明突然说：“我最近在算法课上学过一些最优解问题的解决方法，应该能用得上。”

牛二哥叹口气说：“可是这些方法用到优化器里都不一定够用，何况用到一个更加智能的项目上呢？”

“嗯？优化器里也用到最优解问题的方法了吗？我们学过动态规划、贪心算法……”小明如数家珍地说起来。

大明说：“用到了啊， 虽然物理路径看上去也不多，但实际上枚举起来，它的搜索空间也不小。例如，在扫描路径中，我们就可以有顺序扫描、索引扫描和位图扫描。假如一个表上有多个索引，就可能产生多个不同的索引扫描，那么哪个索引扫描路径好呢？还有，索引扫描和顺序扫描、位图扫描相比，哪个好呢？”

数据库路径的搜索方法

大明看着小明迷离的眼神后继续说：“数据库路径的搜索方法通常有 3 种类型：自底向上方法、自顶向下方法、随机方法，而 PostgreSQL 采用了其中的两种方法。”

“采用了哪两种方法？”牛二哥明知故问。

“采用了自底向上和随机方法，其中自底向上的方法是采用动态规划方法，而随机方法采用的是遗传算法。”

“那有谁使用了自顶向下的方法呢？”牛二哥继续“捧哏”道。

“嗯……这个嘛，Pivotal 公司的开源优化器 ORCA 用的就是自顶向下的方法。可以让牛二哥先给你说说怎样用动态规划方法搜索最优物理路径。”

最优物理路径

牛二哥拿出纸来画了几个圈，然后说：“这代表四个表，自底向上嘛，所以是从底下向上堆积，这是最底层，我们叫它第一层。”

“动态规划方法首先考虑两个表的连接，其中优先考虑有连接关系的表进行连接。两个表的连接可以建立一个新的表，我们把这些新表叫做第二层。”牛二哥通过连线，产生了一些新的“表”。

“第二层的表和第一层的表再连接，可以生成基于三个表连接的新的‘表’，这样就又向前推进了一层，产生了第三层。”

“然后再用第三层的表和第一层的表进行连接，最终生成整个问题的最优路径。”

“可是，这不就是穷举吗？”小明问道。

牛二哥解释说：“动态规划有两个特点，一个是要重复地利用子问题的解，这样能减少计算量，降低复杂度；另外一点就是通过子问题的最优解能够构造出最终的最优解，也就是说需要具有最优子结构的性质，所以动态规划的复杂度和穷举是不一样的。”

大明继续解释说：“还有，虽然你看图里的连线比较多，但在实际情况里，并不是所有的圈圈之间都能产生连线，连接关系也有个合法性的问题嘛，所以复杂度是可以控制住的。”

小明感觉好像明白了一点，然后赶紧追问：“那遗传算法呢？”

大明突然意识到了什么，说：“哎哎哎，我们不是在搜索饭店吗，怎么就说起最优路径了？先点餐吧，再晚饭都没得吃了。”

于是三个人又热火朝天地搜起饭店来……

小结

随着小明、大明和牛二哥的对话结束，我们也要开始进入本次课程的主要内容了……欢迎各位走进 PostgreSQL 优化器的大门，这次我们就没完了。

转载地址：http://ioyni.baihongyu.com/