如何找到代价最小的最优表join路径？如何处理？

我们知道mysql没有hash join或者merge join，所以连接的时候只有一个算法nest loop join，nl join使用驱动表的结果集作为outer table，查找inner table中的每条记录，如果有是索引，它会进行索引扫描，没有索引会进行全表扫描。

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

相比之下，postgresql 的优化器非常强大。支持hash join、nest loop、sort merge join，scan算法支持seq scan、index scan、index only scan，还支持in-heap tuple技术（HOT）。postgresql11版本也增加了并行扫描。我个人在两张大表（一张1.6亿和一张256万数据，都没有索引）上测试了超过300万的join结果集，并行打开pg花了大约20s。刚用完结果，比其他数据库强。

上面讨论了两表连接算法。下面我们来看看mysql和pg是如何处理多表join的。多表连接实际上涉及一个问题：如何找到成本最低的最优路径。为什么会出现这个问题？因为在多表连接中，两个表之间的每一个连接都有一个代价值，优化器会根据代价估计调整不同表的连接顺序，最终计算出一个最优或近似最优的代价，并用这个代价来计算生成执行计划。这涉及到图论中的最短路径问题。不同的连接顺序组合代表图的遍历。最优代价其实就是被动图的最短路径问题。我们知道两种主流的最短路径算法是 Dijkstra 算法和 Floyd 算法，

贪心算法用于计算mysql中的最优成本，而pg使用动态规划。

mysql：

Mysql连接使用贪心算法，下图展示了贪心算法的过程：

贪心算法的前提是确定源点。算法思想跟名字很像。它只找到当前步骤的最优解。这是一个深度优先的解决方案。直到到达终点。比如上图中从A到G，使用贪心算法的路径是A->B->D->G算法，代价是1+2+6=9。显然，这不是最优解。最佳解决方案是我们的肉眼。可以看出A->C->F->G，代价为2+3+1=6。所以我们看到贪心算法不是全局最优的，但是优点是算法复杂度低。MySQL 也可能基于此考虑使用贪心算法。，那么代价的计算成指数增长，所以虽然贪心算法不是最优解，

PostgreSQL：

我们来看看pg使用的动态规划。动态规划解决了被动最短路径问题。让我们想象一下mysql生成er图没有连线，多表连接本身是一个被动的最短路径问题，但是 MySQL 在连接时随机选择了一个作为起点。.

动态规划的思想是将问题分解为子问题，递归求解问题为子问题。以弗洛伊德算法为例。该算法使用邻接矩阵来表示每个点之间的距离，如果没有连接线，则使用无穷大。例如下图：

弗洛伊德算法使用矩阵来记录节点的直接距离。它的强大之处在于它通过多次计算得到任意两个节点之间的直接最短距离。是真正意义上的被动最短路径算法，但是它的算法复杂度也比较高，为O(n³)。该算法如下所述。该算法的核心思想是如果a[ij]>a[ik]+a[kj]，那么a[ij]=a[ik]+a[kj]，对于每两个节点ab如果有第三个中间节点 c 使 acb 的距离变短mysql生成er图没有连线，然后将 ab 的距离替换为 acb 并更新到矩阵中。在这个遍历过程中，我们大致了解到需要三层循环，两层循环一共是为了(n-1）*(n-1） options for ab,ac, ad…de）（你不知道）t需要自己计算距离。）计算每个中间节点（最外层循环）的距离是否更小。矩阵计算过程如下：

对于第一行，依次计算ab、ac、ad、ae的距离，看是否有第三个节点要替换，对于ab的计算，发现ab

综上所述，mysql使用贪心算法只能得到局部最优执行计划，但是计算最优解的代价很小，而pg可以使用动态规划得到最优执行计划，但是最优解算法的计算复杂越高，成本越高。不过总的来说mysql的优化器和pg相比还是有很大差距的。pg的优化器甚至引入了遗传算法，学术考量多多，无愧于学术数据库的称号。也希望mysql越来越好。酒吧。

接下来的活动

2019数据科技嘉年华来了！大咖云集现场，与你分享数据魅力。立即加入并享受早鸟票价：