继《PostgreSQL查询优化器详解（逻辑优化篇）》之后，本文将从物理优化的角度继续深入探讨PostgreSQL数据库查询优化器的细节。为了让大家能够通俗易懂地更好地理解和消化晦涩难懂的概念，作者别出心裁地写出了有趣的故事。虽然篇幅有点长，但仔细阅读一定会收获不少。关于统计信息和选择率“咚咚咚……”敲门声响起。大明打开门一看，是同事牛二哥。牛哥是一名专门从事数据库查询优化开发的码农，拥有十余年的行业经验。大明觉得很开心，因为这两天跟小明解释查询优化器有点难。今天牛哥正好来帮忙：“牛二同志，我弟弟小明最近要在学校练习数据库原理，他总是问我关于优化器的问题，而我对优化器了解不多。现在你来了，能帮忙吗？””牛二哥乐呵呵地说：“我不介意，随时可以说。小明早就听说了牛哥的事，接到大明的电话就赶紧去找他。基于成本优化，我觉得自己付出了很多，收获却很少，希望今天能得到牛二哥的指点。”牛二哥说：“说到成本，我觉得有有一个东西是绕不开的，那就是统计。信息性和选择性，PostgreSQL的物理优化需要计算各种物理路径的代价，而代价估算的过程严重依赖于数据库的统计信息。统计信息能否准确描述表中的数据分布，是决定成本准确性的重要条件之一。”小明说：“大明告诉我，数据库中有很多物理路径，这些物理路径是也称为物理运算符。与逻辑运算符不同，物理运算符是查询执行器的执行方式。我们只需要计算物理算子每一步的成本，加起来就是路径的成本，那么统计信息有什么用呢？”牛哥说：“对，我们就是想计算一个物理算子的成本，但是物理算子的计算量并不是恒定的。”他从旁边的办公桌上拿了笔和纸，写了两条SQL语句。SELECTA+BFROMTEST_AWHEREA>1;SELECTA+BFROMTEST_AWHEREA>100000000;然后说：“你看，这两条语句可以用同一个物理运算符完成，但它们的计算量是否相同？”小明想：A>1和A>1000000000是过滤条件。经过过滤，他们产生的数据量不同，所以A+B在投影中的计算次数不同，所以他们的代价应该不同。那么它与统计信息有什么关系呢？小明灵光一闪，连忙说道：“原来如此，我在计算一个物理算子的成本时，需要知道A>1之后还剩多少数据，或者A>1000000000之后还剩多少数据。表格上的数据内容已经统计过了，剩下多少数据不难计算，所以一定要有统计信息。”牛哥点点头说道：“嗯，通过统计信息，成本估算系统可以了解一张表的价值。有多少行数据，使用了多少数据页，某个值出现的频率等等，然后就可以根据这些信息计算出一个约束条件可以过滤掉多少数据，这个约束条件过滤掉的数据占数据总量的选择率的比值，就叫做‘选择率’，所谓选择率是一个比率，其公式如下。”牛二哥一边说着，一边继续在纸上记下选择率的公式：“不过上面的例子有点简单，在实际应用中，通常会有很多约束，而且比较复杂。通常我们会计算选择性每个子约束，然后我们可以根据AND运算符和OR运算符来计算它们的综合选择性。AND运算符和OR运算符的选择率的计算是基于概率的，可以在这里看到概率公式”然后，牛哥继续在纸上写。P(A+B)=P(A)+P(B)-P(AB)P(AB)=P(A)×P(B)”有了这些，我们可以解决很多类型的约束选择率是更高，比如……”牛哥继续写：P(ssexISNOTNULLORsno>5)=P(ssexISNOTNULL)+P(sno>5)–P(ssexISNOTNULLORsno>5)=P(ssexISNOTNULLORsno>5)+P(sno>5)–P(ssexISNOTNULL)×P(no>5)小明觉得牛哥解释的有点太快了，连忙问道：“那统计信息的形式是什么？””牛哥挠了挠头道：“这还是有点麻烦。我们说的统计信息常用的形式有独特率、NULL值率、高频值、直方图、相关系数等，它们有不同的作用。比如distinctrate，你可以知道有多少列，这种信息对于像gender这样的列特别有用。NULL值率，在统计的过程中，NULL值不好处理，所以分离出来形成NULL值率，所以在高频值和直方图中不需要考虑NULL值.高频值是奇异值。数值可以用来做等频直方图。”大明见小明有点落后，就走过来说，“统计，主要是高频数值，直方图和相关系数。其实我建议不要纠结统计信息有哪些形式，只要知道是用来计算成本的就可以了。牛哥对大明说：“这怎么可能？我还没说统计信息是怎么产生的呢，比如经过了两阶段抽样，然后用统计的方法对样本进行统计，有哪些值可以作为高频数据吗？”值，直方图中有多少个桶，相关系数是怎么计算的，在计算索引扫描路径的成本时，相关系数是如何使用的……还有我告诉你，PostgreSQL还提供了基于多列。列统计分为哪些类型，每个列的含义是什么，它们是如何计算的，选择率是如何结合统计计算的，这些我还没说呢……”大明忍不住道但说：“像你说的优化器，不是要出书吗？”牛哥苦着脸道：“好了，统计信息就到这里了，不过它确实是成本计算的基石，小明同学，只要了解它的作用就可以了。”大明继续神神??秘秘的说道：“其实，统计信息往往是不准确的。想一想，是抽样的结果。假以时日，偏差会更多。更何况，如果遇到a>b这样的约束条件，用统计信息计算选择率是非常困难的，即使计算出来也不准确。”牛哥道：“是啊，统计信息确实不准确。听说有个DBA，他家后院有个泉水。他父亲觉得是吉兆，就去找风水师看。风水大师捏了捏手指说：你儿子是DBA。每次数据库性能慢的时候，他都知道更新统计信息，但是统计信息太水了，而且是从你后院出来的。三人一起笑了起来。物理路径的玩笑结束后，小明说：“你为什么不告诉我物理路径呢？我们计算成本，最后计算物理路径的成本。”大明告诉我，大致分为扫描路径和连接路径。查了一些说明，知道扫描路径包括顺序扫描路径、索引扫描路径、位图扫描路径等；而连接路径通常有嵌套循环连接路径、Hashjoin路径、mergejoin路径，还有一些其他的路径，比如排序路径、物化路径等。如果要获取表中的数据，最基本的方法就是遍历表中的所有数据，选择满足条件的数据。这种方法是顺序扫描路径。顺序扫描路径的优点是适用性广，各种表都可以使用这种方式。缺点是成本通常比较高，因为所有的数据都要遍历一次。与此同时，大明在纸上画了一张图，说道：“这张图大概就是顺序扫描路径。””牛二哥继续说道：“如果对数据做一些预处理，比如建立索引，如果要获取一个表的数据，可以扫描索引，获取需要数据的‘地址’，然后使用地址获取所需数据的“地址”。获得数据。特别是在有约束的选择操作的情况下，在索引和约束的共同作用下，表中的一些数据是不需要遍历的，因为通过索引很容易知道这些数据不满足约束，并且更何况，因为数据也保存在索引上，它的数据和关系中的数据是一致的，所以如果索引上的数据能满足要求，只需要扫描索引就可以得到需要的数据，也就是说在扫描路径中，还可以有索引扫描路径和快速索引扫描路径两种模式。”大明继续“表扬”牛二哥，并在纸上画了索引扫描和快速索引扫描的图。小明看到图上写着“随机阅读”四个字，问道：“我看这个索引扫描有一个随机读取问题，这个问题能解决吗？也就是说使用了索引，避免了乱读的问题。有这样的方法吗？”牛二哥说：“索引扫描路径确实会带来随机读的问题，因为索引记录的是数据元组的地址，索引扫描是通过扫描索引得到元组地址，然后通过元组地址。数据中保存的“有序”地址在数据中可能是随机的。位图扫描可以解决这个问题。它通过位图保存地址，收集地址，然后对地址进行排序，从而通过中间位图消除随机读取。大明继续在纸上画了位图扫描的示意图。大明补充道：“在扫描过程中，也有一些非常高效的扫描路径结合一些特殊情况，比如TID扫描路径。TID其实就是一个元组，对于磁盘上的存储地址，我们可以直接根据元组获取到TID，这样查询效率就很高了。牛哥点点头继续说：“扫描路径一般是执行计划中的叶子节点，也就是最底层扫描表的节点。扫描路径是为连接路径做准备。扫描的数据你可以给出连接路径来实现连接操作。”大明一边在纸上作画一边说：“连接两个关系，受笛卡尔积的启发，可以用算法复杂度为O(mn)的方法来实现。我们称之为NestloopedJoin方法。这种方法虽然比较复杂，但是和顺序扫描一样通用。牛二哥说：“nestlooploopjoin方式的复杂度比较高，看起来没什么意义，但是如果NestloopedJoin的内表路径是索引扫描路径，那么算法的复杂度会降低。“indexscan的算法复杂度是O(logn)，所以如果NestloopedJoin的内表是indexscan的话，它的整体算法复杂度变成了O(mlogn)，似乎可以接受。”小明点点头说道：“嗯，索引其实是对数据做了一些预处理。我觉得如果hashjoin的方式是把内表做成hash表，这也相当于对内表的数据进行了预处理。处理也可以方便检测外部的元组，对吧？”牛哥点点头说：“假设Hash表有N个桶，内表的数据均匀分布在每个桶中，那么HashJoin的时间复杂度就是O(m*n/N)。当然，这里我们没有考虑构建哈希表的成本。”大明在纸上画了一张哈希连接的示意图，补充道：“哈希连接通常只能用于等价判断。”牛二哥继续说道：“如果先把两张表排序，那么就可以引入第三种连接方式，MergeJoin。这种连接方式的开销主要浪费在了排序上。如果两个关系的数据量都比较小，那么排序的代价是可控的，适用MergeJoin。另外，如果关系上有有序索引，则不需要单独排序，更适合MergeJoin。看我画的合并连接示意图。外表需要排序，而内表则借用了原来索引的顺序，省去了排序的时间，降低了物理路径的开销。""这些路径属于SPJ路径。在PostgreSQL优化器中，通常会先生成SPJ路径，然后在此基础上叠加Non-SPJ路径，比如聚合操作、排序操作、限制操作、分组操作……”牛哥继续说道补充。关于成本的计算，小明说：“但是经过计算，物理路径的成本还是有的时候不准确。”牛二哥说：“最优路径选择不准确的原因是谁？好好搭建，所以要怪程序员自己。”小明问道：“但是我觉得PostgreSQL的成本计算已经很复杂了。”“但是数据库的周边环境更复杂。想想它，在实际应用中，数据库用户的配置硬件环境千差万别，CPU的频率、主存的大小、磁盘介质的性质等都会影响实际执行时执行计划的效率。”牛二哥说道。大明接过继续说；“虽然在成本估算的过程中，我们无法得到‘绝对真理’的代价，但是‘绝对真理’的代价是没有必要的。因为我们只是想从多条路径中找出一条成本最小的路径（Path),只要这些路径的代价能够‘相互比较’即可。因此，可以设置一个“相对”的代价单元1，同一个查询中的所有物理路径都基于这个“相对”的单元1进行计算,这样计算出来的cost就可以进行比较，可以用来选择路径。牛哥接着说：“PostgreSQL以顺序读写一个page的IOcost为1为单位，随机IO设置为4倍顺序IO的。”小明说：“我知道，我查过相关书籍。首先，现在的存储介质很大一部分还是机械硬盘，机械硬盘的磁头需要获取数据库时要花费寻道时间，如果要在磁盘上读写一系列连续的数据，您可以节省寻道时间并提高IO性能。但是，如果随机读写磁盘任意一个扇区的数据，就会浪费大量的时间在寻道上。其次，大部分磁盘本身都有缓存，形成了主存→磁盘缓存→磁盘的三级结构。当将磁盘的内容加载到内存中时，考虑到磁盘的IO性能，磁盘会预读数据，并将预读的数据保存在磁盘缓存中。也就是说，如果用户只打算从磁盘读取100字节的数据，那么磁盘可能会连续从磁盘读取512字节（不同的磁盘预读量可能不同）并保存到磁盘缓存中。如果下一次是顺序读取100字节后的内容，那么预读的512字节数据就会发挥作用，性能会大大提高。而如果读取的内容超过512字节的范围，预读的数据将无法发挥作用，磁盘的IO性能会下降。”说完，小明得意道：“怎么样，我说的对吗？”牛哥道：“你说得对。目前PostgreSQL的查询优化，大量考虑了随机IO和顺序IO的性能差异，在这方面做了很多优化。但是现在磁盘技术越来越发达，以后的随机IO和顺序IO会不会有这么大的区别还是值得商榷的。”“那什么是价格基准单位呢？小明继续问道。大明回答：“基于磁盘IO的成本单位当然是和Page相关的，也就是说我们刚才说的顺序IO和随机IO都属于IO的benchmarkcost。让牛二哥给大家介绍下page的基本单位CPU方面的价格。”牛哥说：“CPU的benchmark单位是多少？比如我们通过IO读取磁盘页到缓存，但是我们需要处理元组，所以我们需要从中提取元组page和处理tuples，这部分主要是消耗CPU，所以会有一个costbenchmarkunits的tuple来处理，另外我们在projections和constraints中有大量的表达式，求解这些表达式主要是消耗CPU资源，所以表达式的成本也有一个基准单位。”牛哥继续说道：“现在PostgreSQL增加了很多并行路径，所以也会产生通信成本，这也是需要计算的。小明听后，说：“那我们就可以得到这样一个公式。”“Speaking在纸上写了一个公式：总成本=CPU成本+IO成本+通信成本然后继续说：“不过我也通过EXPLAIN查看了PostgreSQL的执行计划，也从执行计划中看到有启动成本和总成本，这是怎么回事？”牛哥想了想，在纸上写了一个公式：总成本=启动成本+执行成本然后说：“这是从另一个角度来计算成本。第一个元组的开销（另一种说法是准备获取第一个元组的开销），总开销就是SQL语句从头到尾的所有开销。”“可是……为什么要区分启动成本和执行成本呢？”“嗯……”牛哥想了想，觉得说几句不好解释清楚，于是写了一个例子：SELECT*FROMTEST_AWHEREa>1ORDERBYaLIMIT1;“我们假设有一个B树在TEST_A(a)索引上，你知道吗，这条语句可能形成什么样的执行计划？”小明想了想，觉得做梦可能有点困难，就在纸上画了下来，最后画了两条执行路径：执行路径1：LIMIT1->SORT(a)->SeqScanWHEREA>1;ExecutionPath2:LIMIT1->IndexScanWHEREA>1;(小明注：B-tree索引是有序的，不用再排序)小明说：“我觉得这两个都可以，但是第二种更好，因为它节省了排序的时间。牛哥问：“如你所知，PostgreSQL使用动态规划实现路径搜索。这是一种自下而上的方法。然后去形成连接路径。所以我们在筛选扫描路径的时候，并不知道它的上层有没有LIMIT。这时候如果单看SeqScan+SORT和IndexScan，你觉得哪个更好？“嗯，我知道陷阱在哪里了，大明告诉我，如果A>1的选择性高，就会选择sequentialscan，如果A>1的选择性低，就会选择indexscan。这个是因为索引扫描会产生随机IO，也就是说，在高选择率的情况下，SeqScan+SORT可能会比IndexScan好。虽然SeqScan+SORT会排序，但是IndexScan的随机IO真的很厉害。”牛哥点头说：“是的，假设选择率比较高，此时选择SeqScan+SORT，因为它不知道上层是LIMIT1，如果上面是LIMIT1，会导致索引scan不需要完全扫描，只需要扫描即可。此时随机IO很小，但是SeqScan+SORT必须执行完整才能得到LIMIT1，也就是说SeqScan+SORT，或者SORT得到第一个元组的启动成本比较高。如果有上面LIMIT1这样的子句，那么启动成本高的路径可能就没有优势了，这就是启动成本的作用。”小明恍然大悟：“SORT全部做完才能得到第一个元组。它的启动成本很高，但总成本很小。至于索引扫描，因为是有序的，所以它的启动开销很小，但是因为是随机IO，所以它的总开销很高。如果我们只根据总成本进行过滤，是没有办法得到最优成本的。““什么？什么？启动成本...你们走得很快。这时候，大明跑过来说道：“我们想想晚饭吃什么？””小明：“吃点好东西是很有必要的。我的脑细胞快用完了。”关于最佳路线，小明、大明和牛二哥在外卖app里搜索附近的餐厅，大明突然感叹：“看，这就是蓝色的海洋。我们可以创业，可以创建人工智能评论，我们只能推荐最好的餐厅。准确找到吃货的痛点，蕴含着巨大的商机！牛哥看了他一眼，道：“AI推荐当然好，但一定要准确。”一人一味，你的需求太“聪明”了，我觉得不好办。”小明突然说道：“我最近在算法课上学了一些最优问题的解法，应该会有用。”牛哥叹了口气道：“可是这些方法都不一定够用在优化器上，更何况是更智能的项目呢？”“嗯？优化器中是否也使用了问题的最优解？我们学过动态规划，贪心算法……”小明像几宝一样说道。大明说：“用起来了，虽然物理路径看起来不多，但实际上枚举起来，它的搜索空间不小。例如在扫描路径中我们可以有顺序扫描、索引扫描和位图扫描。如果一张表有多个索引，可能会产生多次不同的索引扫描，那么到底哪种索引扫描路径更好呢？另外，哪个索引扫描比顺序扫描和位图扫描好？”大明看着小明疑惑的眼神，继续说道：“数据库路径的查找方式通常有三种：自下而上法、自上而下法和随机法，而PostgreSQL就使用了其中两种。”“用了哪两种方法？”牛哥明知故问。采用自下而上和随机方法，其中自下而上方法采用动态规划方法，而随机方法采用遗传算法。”“那谁用过自上而下的方法？”牛二哥继续“夸奖”。“嗯……嗯，Pivotal的开源优化器ORCA采用的是自上而下的方法，你可以请牛哥告诉你如何使用动态规划的方法来搜索最优的物理路径。”牛哥拿出论文，画了几个圈，又道：“这代表四张桌子，从下往上，所以从下往上叠放。这是最底层，我们称之为第一层。”动态规划方法首先考虑两个表的连接，优先考虑有连接关系的表的连接。两个表的连接可以创建一个新表。我们将这些新表称为第二层。“牛哥通过连接创建了一些新的‘表’。”第二层的表和第一层的表再连接起来，根据三张表的连接生成一个新的“表”，这样再往前一层，我们生成第三层“”，然后连接第三层的表与第一层的表，最终生成了整个问题的最优路径。”“可是，这还不算穷尽吗？”小明问道。牛二哥解释道：“动态编程有两个特点。一是重复使用子问题的解，可以减少计算量和复杂度；另一种是使用子问题的最优解。能够构造出最终的最优解就意味着需要具有最优子结构的性质，所以动态规划的复杂度不同于穷举。大明继续解释道：“还有，虽然你可以看到图中有很多联系，但在现实中，并不是所有的圈子都能联系起来，还有一个联系关系合法性的问题。”，所以复杂度是可以控制的。小明感觉好像有点明白了，又急忙问道：“那遗传算法呢？””大明说：“虽然动态规划的复杂度是可以控制的，但是如果表很多，它的搜索空间还是很大的，所以如果表很多，可以尝试用遗传算法。一定是全局最优解，也可能是局部最优解。“遗传算法是如何实现物理路径搜索的？””小明问道。牛哥从书柜里找到了一本算法书，里面正好有遗传算法的介绍，于是大声朗读：“遗传算法的实现步骤如下：种群初始化：对基因进行编码，以及通过对基因进行随机排列组合，产生多条染色体，形成新的种群。另外，在生成染色体的过程中同时计算染色体的适应度；染色体选择：通过随机选择（实际上是通过一种基于概率的随机数生成算法，倾向于选择优秀的染色体），选择用于交叉的染色体和变异染色体；交叉操作：染色体交叉产生新的染色体，加入到种群中；变异操作：对染色体进行变异操作，产生新的染色体，加入到种群中；适应度计算：剔除不良染色体。”大明笑道：“信书不如无书。先说遗传算法是怎么解决推销员问题的。我们可以将城市作为基因，通过每个城市的路径作为染色体，路径的总长度作为适应度。适应度函数负责过滤掉较长的路径并保留较短的路径。算法步骤如下：对城市进行编号，根据编号排列组合，生成多条新路径（染色体）。然后根据城市之间的距离计算总路径长度（适应度），多条新路径形成种群；选择两条路径进行交叉（注意交叉生成的新染色体中不能重复出现同一个城市），交叉操作生成计算新路径的路径长度；随机选择染色体进行变异（通常的方法是交换城市在路径中的位置），并为变异操作后的新路径计算路径长度；根据路径长度从小到大对种群中的所有路径进行排序，淘汰排名较低的路径。”大明一口气说完了整个过程，长长地舒了一口气，继续说道：“怎么样，是不是很容易啊？,"让我猜猜PostgreSQL是如何实现遗传算法的。PostgreSQL应该模拟推销员问题的解决方案。它使用表作为基因，最终的执行计划作为染色体，执??行计划的总成本作为适应度。适应度函数是根据路径的代价来筛选的吧？”牛哥赞叹道：“那很好，不过需要注意的是，PostgreSQL的遗传算法的实现与通常的遗传算法略有不同，它没有变异的过程，只是通过交叉产生新的染色体。那不是重点。”大明道：“喂喂喂，我们不是找饭馆吗？为什么要讨论最优路径？我们先点餐吧，晚饭就不用吃了。》于是三人热火朝天的找餐厅……综上所述，这个故事暂时告一段落。通过这两篇文章，我们基本了解了查询优化的大部分概念，但是篇幅有限，我们有没能把细节说清楚。特别到位，还请多多包涵。两篇文章大部分内容摘自我的新书《PostgreSQL技术内幕：查询优化深度探索》，然后以小明对话的形式呈现，大明和牛二哥，书中介绍的代码分析部分，以及比较深入的实现细节，由于不易展示，故事中不再涉及，欢迎有兴趣的同学从书中获取相关知识。
