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

共计 2006 个字符，预计需要花费 6 分钟才能阅读完成。

这篇文章主要介绍 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 和 PostgreSQL 在多表连接算法上的差异有哪些”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注丸趣 TV 行业资讯频道！