MySQL和PostgreSQL在多表连接算法上的差异

本文来源于数据库架构之美，作者数据库架构之美

我们知道MySQL没有hash join，也没有merge join，所以在连接的时候只有一种算法nest loop join，nl join使用驱动表的结果集作为外表到内表中查找每一条记录，如果有索引，就会走索引扫描，没有索引就会全表扫。

nl join并不能适用所有场景，例如两个表都是很大的表的等值连接，这种场景是hash join所擅长的，而且是生产环境中最常见的场景。mysql在这个时候就显得力不从心，所以在使用mysql时我们可能会制定如下规范：禁止使用大表连接。这也是mysql永远的痛。不过据说8.0版本已经将hash join作为一个需求纳入了，我们拭目以待吧。

相比起来，postgresql的优化器十分的强劲。支持了hash join、nest loop、sort merge join，扫描算法支持seq scan、index scan、index only scan，同时还支持堆内元组技术（HOT）。在postgresql11版本中还加入了并行扫描，亲测在两张大表（一张1.6亿一张256万数据，均无索引）做join结果集300多万，pg开启并行大概20s以内就跑出结果，强于其他数据库。

上面讨论了两表join的算法，下面看看多表join时mysql和pg是如何处理的。多表join其实涉及到一个问题：如何找到代价最小的最优路径。为什么会有这个问题呢？因为在多表连接时，每两个表之间连接具有一个代价值，优化器会根据代价估算调整不同表join的顺序，最后算出一个最优或者近似最优代价，使用这个代价生成执行计划，这样就涉及到图论中的最短路径问题，不同的连接顺序组合代表了图的遍历，最优代价其实就是求无源图的最短路径问题。我们知道两种主流的最短路径算法是迪杰斯特拉（Dijkstra）算法和弗洛伊德（floyd）算法，这两种算法也是动态规划中的经典算法。

在mysql中计算最优代价使用贪心算法，而pg使用的是动态规划。

Mysql：

Mysql连接使用贪心算法，下面这个图表明了贪心算法的过程：

贪心算法的前提是确定源点，算法思想也和名字很像，只找当前步骤的最优解，是一种深度优先的解法，算法复杂度是O（n²）找到后继续深入下一层，直至达到终点。比如上图从A到G，使用贪心算法的路径是A->B->D->G算法，代价是1+2+6=9，很明显这并不是最优解，最优解我们肉眼可以看出来是A->C->F->G，代价是2+3+1=6。所以我们看贪心算法并不是全局最优的，但是优点是算法复杂度低，mysql可能也是基于这种考虑而使用贪心算法，不想将时间都浪费在计算代价上了，因为如果关联的表特别多，那么代价的计算是指数级增长，所以贪心算法虽然不是最优解，但是在连接表的数量很大的情况下具有一定优势。

Postgresql：

再来看看pg使用的动态规划，动态规划解决的是无源最短路径问题，我们想象一下其实多表连接本身就是一个无源最短路径问题，只是mysql在进行连接的时候随机选了一个作为起点而已。

动态规划的思想是将问题分解为子问题，将问题递推为子问题进行解决。以floyd算法为例。算法使用邻接矩阵来表示每个点之间的距离，如果没有连线，则代表无穷大。比如下面这个图：

弗洛伊德算法使用矩阵记录节点直接距离，它的强大之处在于它经过若干次计算后得到任意两个节点直接的最短距离，是真正意义上的无源最短路径算法，但是它的算法复杂度也比较高，是O（n³）。下面介绍一下该算法，算法的核心思想是如果a[ij]>a[ik]+a[kj]，那么a[ij]=a[ik]+a[kj]，对于每两个节点ab之间的距离，如果存在第三个中间节点c使得acb的距离更短，那么ab的距离使用acb代替，并更新到矩阵。这样的遍历过程我们大致就理解了需要三层循环，里面的两层循环是对于ab、ac、ad...de总共（n-1）*（n-1）种选择（自己对自己的距离不用计算）计算每个中间节点（最外层循环）的距离是否更小。矩阵计算过程如下：

对于第一行，依次计算ab，ac，ad，ae的距离是否有第三个节点进行替换，对于ab计算发现，ab<ac+cb&&ab<ad+db&&ab<ae+eb，所以ab不用更新，同理ac也不用更新，对于ad，计算得到ab+bd=6，ac+cd=∞，ae+ed=∞，于是更新ad=6，同理计算更新ae=8；然后依次计算下面几行。全部遍历完，经历了三层循环，算法复杂度是O（n³）。pg使用该算法能够得到最优执行计划，但是在表的个数很多时计算代价所付出的代价也很大。

综上，mysql使用贪心算法只能得到局部最优执行计划，但是计算最优解所消耗的代价较小，而pg使用动态规划能够得到最优执行计划，但是计算最优解算法复杂度较高，代价较大。但是总体上mysql的优化器相比pg还是有很大差距，pg的优化器甚至引入了基因算法，有很多比较学术的考量，当得起学术派数据库的称号，也希望mysql能够越来越好吧。